Daftar tautan yang dipesan:
Urutkan berdasarkan nilai kunci. Saat menghapus header rantai, nilai minimum (/maksimum) dihapus. Saat memasukkan, cari posisi penyisipan.
Saat memasukkan, Anda perlu membandingkan O (n), rata -rata O (n/2), dan saat menghapus data minimum (/maksimum) pada kepala rantai, efisiensinya adalah O (1),
Jika suatu aplikasi membutuhkan akses yang sering (masukkan/temukan/hapus) ke item data terkecil (/maksimum), maka daftar tertaut yang dipesan adalah pilihan yang baik. Antrian prioritas dapat menggunakan daftar tertaut yang dipesan untuk mengimplementasikan penyisipan penyisipan daftar tertaut yang dipesan:
Untuk array yang tidak tertib, urutkan dengan daftar tertaut yang dipesan, dan tingkat waktu perbandingan adalah O (n^2)
Tingkat waktu salin adalah O (2*n). Karena jumlah salinannya kecil, data dalam daftar tertaut dipindahkan n kali untuk pertama kalinya, dan kemudian disalin dari daftar yang ditautkan ke array. N kali, setiap kali tautan baru dimasukkan, tidak perlu menyalin data yang bergerak, hanya satu atau dua tautan yang perlu mengubah domain tautan.
impor java.util.arrays; impor java.util.random; / *** Sisipan penyisipan dalam daftar tertaut yang dipesan* @Author Stone*/ kelas publik LinkedListIntSort <t memperluas yang sebanding <T>> {Private Link <T> pertama; // node pertama linkedlistInsertSort () {} public boolean isEmpty () {return first == null; } public void sortList (t [] ary) {if (ary == null) {return; } // Masukkan elemen array ke dalam daftar tertaut dan urutkan dalam daftar tertaut yang dipesan untuk (data t: ary) {masukkan (data); } //} public void Insert (t data) {// Masukkan ke header rantai, urutkan dari tautan kecil ke besar <t> newLink = tautan baru <T> (data); Link <T> saat ini = pertama, sebelumnya = null; while (current! = null && data.compareto (current.data)> 0) {sebelumnya = saat ini; current = current.next; } if (sebelumnya == null) {first = newLink; } else {sebelumnya.next = newLink; } newLink.next = saat ini; } tautan publik <T> deleteFirst () {// hapus tautan header rantai <T> temp = pertama; First = first.next; // Ubah simpul pertama untuk mengembalikan suhu; } tautan publik <T> temukan (t t) {link <t> find = first; while (find! = null) {if (! find.data.equals (t)) {find = find.next; } else {break; }} return find; } tautan publik <T> hapus (tt) {if (isEmpty ()) {return null; } else {if (first.data.equals (t)) {link <t> temp = pertama; First = first.next; // Ubah simpul pertama ke node berikutnya pengembalian suhu; }} Tautan <T> p = pertama; Tautan <T> q = pertama; while (! p.data.equals (t)) {if (p.next == null) {// menunjukkan bahwa pengembalian null belum ditemukan pada akhir rantai; } else {q = p; p = p.next; }} q.next = p.next; mengembalikan P; } public void displayList () {// travel System.out.println ("Daftar (pertama-> terakhir):"); Tautan <T> saat ini = pertama; while (current! = null) {current.displaylink (); current = current.next; }} public void displayListreverse () {// tautan traversal terbalik <T> p = pertama, q = first.next, t; while (q! = null) {// pointer dibalik, urutan data yang dilintasi adalah mundur t = q.next; // no3 if (p == pertama) {// Ketika itu adalah header asli, .next header harus kosong p.next = null; } q.next = p; // no3 -> no1 pointer reverse p = q; // Mulai adalah terbalik q = t; // NO3 MULAI} // Di IF di loop di atas, First.Next kosong, dan ketika Q nol dan tidak menjalankan loop, p adalah item data terbanyak asli. Setelah membalik, P ditugaskan ke First First = P; DisplayList (); } tautan kelas <t> {// data titik t link; // Tautan Bidang Data <T> Berikutnya; // penunjuk selanjutnya, tautan domain rantai simpul (data t) {this.data = data; } void displayLink () {System.out.println ("Data adalah" + data.toString ()); }} public static void main (string [] args) {LinkedListInSertSort <Integer> list = new LinkedListInsertSort <Integer> (); Acak acak = acak baru (); int len = 5; Integer [] ary = bilangan bulat baru [len]; untuk (int i = 0; i <len; i ++) {ary [i] = random.nextInt (1000); } System.out.println ("--------------"); System.out.println (arrays.tostring (ARY)); System.out.println ("-------------------------------------------------------); List.SortList (ARY); List.DisplayList ();}}
Mencetak
--- Sebelum menyortir ---- [595, 725, 310, 702, 444] --- Setelah penyortiran daftar tertaut ---- daftar (pertama-> terakhir): Data adalah 310 data adalah 444 data adalah 595 data adalah 702 data adalah 725
Inversi Daftar Tertaut Tunggal:
kelas publik singleLinkedlistreverse {public static void main (string [] args) {node head = new node (0); Node temp = null; Node cur = null; untuk (int i = 1; i <= 10; i ++) {temp = node baru (i); if (i == 1) {head.setNext (temp); } else {cur.setNext (temp); } cur = temp; } // 10.next = null; Node h = head; while (h! = null) {System.out.print (h.getData () + "/t"); h = h.getNext (); } System.out.println (); // invert 1 // h = node.reverse1 (head); // while (h! = null) {// system.out.print (h.getData () + "/t"); // h = h.getNext (); //} // invert 2 h = node.reverse1 (head); while (h! = null) {System.out.print (h.getData () + "/t"); h = h.getNext (); }}}/** Setiap node dari daftar yang ditautkan berisi atribut yang menunjuk ke simpul*/kelas node berikutnya {data objek; // data objek node selanjutnya; // node node berikutnya (objek d) {this.data = d; } Node (objek d, node n) {this.data = d; this.next = n; } objek publik getData () {return data; } public void setData (data objek) {this.data = data; } node publik getNext () {return next; } public void setNext (node next) {this.next = next; } // Metode 1 kepala adalah reset simpul statis reverse1 (head simpul) {node p = null; // Kepala baru setelah simpul inversi q = head; // Hasil Rotasi: 012,123,234, ...... 10 NULL NULL sementara (head.next! = Null) {p = head.next; // Yang pertama digantikan oleh yang kedua, dan kemudian P mewakili head.next = p.next; // Yang kedua digantikan oleh yang ketiga, dan yang berikutnya yang telah mencapai posisi pertama akan menjadi yang pertama, dan yang pertama akan menjadi yang pertama; // yang baru digantikan oleh yang pertama} return p; } // Metode 2 head tidak mengatur ulang node statis reverse2 (kepala simpul) {// titik pointer simpul menengah ke simpul sebelumnya, Anda masih dapat terus melintasi daftar linked mundur simpul p1 = head, p2 = head.next, p3; // hasil depan, tengah dan belakang/rotasi: 012, 123, 234, 345, 456 .... 9 10 null while (p2! = Null) {p3 = p2.next; p2.next = p1; // point mundur dan poin ke depan p1 = p2; // 2, 3 bergerak maju P2 = p3; } head.next = null; // head belum berubah. Ketika output mencapai 0, minta 0.Next to 1 Return p1; }}