Dalam artikel sebelumnya, kami menganalisis implementasi arrayList yang mendasari dan tahu bahwa implementasi arrayList yang mendasari didasarkan pada array, sehingga memiliki karakteristik pencarian dan modifikasi yang cepat sementara penyisipan dan penghapusan yang lambat. LinkedList yang diperkenalkan dalam artikel ini adalah implementasi lain dari antarmuka daftar. Lapisan yang mendasarinya didasarkan pada daftar ditautkan dua arah. Oleh karena itu, ia memiliki karakteristik penyisipan dan penghapusan cepat saat pencarian dan modifikasi yang lambat. Selain itu, fungsi antrian dan tumpukan dapat diwujudkan melalui pengoperasian daftar ditautkan dua arah. Struktur yang mendasari LinkedList ditunjukkan pada gambar di bawah ini.
F mewakili referensi simpul head, L mewakili referensi simpul ekor, dan setiap node dalam daftar tertaut memiliki tiga elemen, yaitu referensi node depan (p), nilai elemen simpul (E), dan referensi simpul berikutnya (n). Node diwakili oleh simpul kelas dalam, mari kita lihat struktur internalnya.
// Node Internal Class Private Static Class Node <E> {e Item; // Node Elemen <E> Berikutnya; // simpul node berikutnya <e> Sebelumnya; // simpul node sebelumnya (node <E> prev, elemen e, node <E> next) {this.item = elemen; this.next = next; this.prev = prev; }}Node kelas internal sebenarnya sangat sederhana, dengan hanya tiga variabel anggota dan konstruktor. Item ini mewakili nilai node, selanjutnya adalah referensi ke simpul berikutnya, dan prev adalah referensi ke node sebelumnya. Ketiga nilai ini dilewatkan melalui konstruktor. Selanjutnya, mari kita lihat variabel anggota dan konstruktor LinkedList.
//The number of set elements is translated int size = 0;//The header node references transient Node<E> first;//The tail node references transient Node<E> last;//The parameterless constructor public LinkedList() {}//The constructor passed into the external collection public LinkedList(Collection<? extends E> c) { this(); addall (c);}LinkedList memegang referensi ke node header dan referensi ke node ekor. Ini memiliki dua konstruktor, satu adalah konstruktor tanpa parameter, dan yang lainnya adalah konstruktor yang diteruskan ke koleksi eksternal. Tidak seperti ArrayList, LinkedList tidak menentukan konstruktor ukuran awal. Lihatlah metode penambahan, menghapus, memodifikasi, dan mencari.
// Tambah (tambahkan) public boolean add (e e) {// tambahkan linklast (e); return true;} // add (masukkan) public void add (index int, elemen e) {checkPositionIndex (index); if (index == size) {// Tambahkan linkLast (elemen); } else {// masukkan linkbefore (elemen, node (index)); }} // hapus (berikan indeks) public e hapus (indeks int) {// periksa apakah subscriptnya adalah checkelementIndex (indeks); kembalikan unlink (node (index));} // hapus (elemen yang diberikan) boolean publik hapus (objek o) {if (o == null) {for (node <e> x = first; x! = null; x = x.next) {if (x.item == null) {unlink (x); Kembali Benar; }}} else {// Daftar tautan ketenangan untuk (node <e> x = first; x! = null; x = x.next) {if (o.equals (x.item)) {// hapus unlink (x); Kembali Benar; }}} return false;} // ubah set publik e (indeks int, elemen e) {// periksa apakah subskripnya adalah chrips checkelementIndex (index); // Dapatkan referensi simpul dari simpul subskrip yang ditentukan <E> x = node (indeks); // Dapatkan nilai simpul subskrip yang ditentukan e oldval = x.item; // Atur elemen simpul ke nilai baru x.item = elemen; // kembalikan nilai sebelumnya pengembalian oldval;} // periksa public e get (index) {// periksa apakah subskripnya adalah checkelementIndex (indeks); // Kembalikan nilai node simpul pengembalian subskrip yang ditentukan (indeks) .item;}Metode menambahkan elemen di LinkedList terutama untuk memanggil dua metode LinkLast dan LinkBefore. Metode LinkLast adalah untuk menautkan elemen di belakang daftar tertaut, dan metode LinkBefore adalah untuk memasukkan elemen di tengah daftar yang ditautkan. Metode Hapus LinkedList menghapus elemen dari daftar yang ditautkan dengan memanggil metode untink. Mari kita lihat kode inti dari operasi penyisipan dan penghapusan daftar yang ditautkan.
// Sebelum menautkan ke node void linkBefore yang ditentukan (e e, node <e> succ) {// Dapatkan referensi simpul sebelumnya dari simpul node yang diberikan <e> pred = succ.prev; // Buat simpul baru, referensi simpul sebelumnya dari node baru poin ke simpul sebelumnya dari simpul yang diberikan // Referensi node berikutnya dari simpul baru poin ke simpul node yang diberikan <e> newNode = node baru <> (pred, e, succ); // Tunjuk referensi simpul sebelumnya dari simpul yang diberikan ke simpul baru succ.prev = newNode; // Jika simpul sebelumnya dari simpul yang diberikan kosong, itu berarti bahwa simpul yang diberikan adalah node header if (pred == null) {// Tunjuk referensi simpul header ke node baru First = newNode; } else {// sebaliknya, arahkan referensi simpul berikutnya ke simpul baru pred.next = newNode; } // Tambahkan jumlah elemen set satu ukuran ++; // Tambahkan jumlah modifikasi satu modcount ++; } // Bongkar node e unlink yang ditentukan (node <e> x) {// Dapatkan elemen dari node final e elemen = x.item; // Dapatkan referensi ke simpul berikutnya dari simpul Node Final yang diberikan <E> NEXT = X.NEXT; // Dapatkan referensi ke simpul sebelumnya dari simpul simpul yang diberikan <E> prev = x.prev; // Jika simpul sebelumnya dari simpul yang diberikan kosong, Penjelasan: Node yang diberikan adalah node header if (prev == null) {// Poin referensi simpul header ke simpul berikutnya dari simpul yang diberikan pertama = Next; } else {// referensi simpul penerus dari simpul sebelumnya yang menunjuk ke simpul berikutnya dari node prev.next = next; // referensi simpul sebelumnya dari simpul yang diberikan x.prev = null; } // Jika simpul berikutnya dari simpul yang diberikan kosong, itu berarti bahwa simpul yang diberikan adalah simpul ekor jika (NEXT == null) {// Tunjuk referensi simpul ekor ke simpul sebelumnya dari simpul yang diberikan terakhir = prev; } else {// referensi node depan dari simpul berikutnya yang menunjuk ke simpul sebelumnya dari simpul yang diberikan next.prev = prev; x.next = null; } // Kosongkan elemen dari simpul yang diberikan x.item = null; // Kurangi jumlah elemen yang ditetapkan berdasarkan ukuran--; // Tambahkan modcount ++; mengembalikan elemen;} LinkBefore dan Unlink adalah operasi representatif dari menghubungkan node dan menghapus node. Metode lain untuk menghubungkan dan menghapus node di kedua ujungnya serupa, jadi kami fokus pada metode LinkBefore dan untink.
Diagram proses Metode LinkBefore:
Diagram proses metode untink:
Melalui ilustrasi di atas, kompleksitas waktu dari operasi penyisipan dan penghapusan dari daftar yang ditautkan adalah O (1), dan operasi pencarian dan modifikasi dari daftar tertaut memerlukan melintasi daftar yang ditautkan untuk menemukan elemen. Kedua operasi disebut metode node (int index) untuk menemukan elemen untuk melihat bagaimana ia menempatkan elemen melalui subskrip.
// Dapatkan simpul simpul <e> node (indeks int) {// Jika indeks berada di paruh pertama daftar tertaut, periksa dari awal jika (indeks <(size >> 1)) {node <e> x = pertama; untuk (int i = 0; i <index; i ++) {x = x.next; } return x; } else {// Jika indeks berada di paruh kedua dari daftar yang ditautkan, periksa dari simpul akhir <E> x = terakhir; untuk (int i = ukuran-1; i> index; i--) {x = x.prev; } return x; }} Saat memposisikan subskrip, pertama -tama tentukan apakah itu di bagian atas atau bagian bawah daftar yang ditautkan. Jika berada di bagian atas, mulailah dari awal, dan jika itu adalah bagian bawah, mulailah dari akhir. Oleh karena itu, kompleksitas waktu pengoperasian pencarian dan memodifikasi subskrip adalah O (n/2). Melalui pengoperasian daftar yang ditautkan dua arah, fungsi antrian item tunggal, antrian dua arah dan tumpukan juga dapat direalisasikan.
Operasi antrian satu arah:
// Dapatkan header node public e peek () {node akhir <e> f = pertama; return (f == null)? null: f.item;} // Dapatkan header node public e elemen () {return getFirst ();} // Pop up node header node public e poll () {node akhir <e> f = pertama; return (f == null)? NULL: UNLINKFIRST (f);} // Hapus node header public e lepas () {return remeFIrFirst ();} // Tambahkan simpul di akhir penawaran boolean publik antrian (e e) {return add (e);}Operasi antrian dua arah:
// Tambahkan Public Boolean OpressFirst (E E) {addFirst (E); return true;} // tambahkan boolean publiclast publiclast (e e) {addlast (e); return true;} // Dapatkan node header public e peekfirst () {node akhir <e> f = pertama; return (f == null)? NULL: F.Item; } // Dapatkan node tail public e peeklast () {node akhir <e> l = terakhir; return (l == null)? null: l.item;}Operasi tumpukan:
// Menempatkan stack public void push (e e) {addFirst (e);} // menempatkan stack public e pop () {return remefirFirst ();} Apakah itu antrian satu arah, antrian dua arah atau tumpukan, mereka benar-benar beroperasi di node kepala dan ekor dari daftar yang ditautkan. Implementasinya didasarkan pada empat metode: addFirst (), addLast (), removeFirst (), dan removelast (). Operasi mereka mirip dengan LinkBefore () dan Unlink (), kecuali yang satu untuk beroperasi di kedua ujung daftar yang ditautkan, dan yang lainnya beroperasi di tengah daftar yang ditautkan. Dapat dikatakan bahwa keempat metode ini adalah kasus khusus metode LinkBefore () dan Unlink (), sehingga tidak sulit untuk memahami implementasi internal mereka, jadi saya tidak akan memperkenalkannya di sini. Pada titik ini, analisis LinkedList kami akan berakhir, dan kami akan meringkas poin -poin penting dalam seluruh teks:
1. LinkedList diimplementasikan berdasarkan daftar tertaut dua arah. Apakah itu penambahan, penghapusan, modifikasi, dan metode pencarian atau implementasi antrian dan tumpukan, itu dapat diimplementasikan melalui node operasi.
2. LinkedList tidak perlu menentukan kapasitas terlebih dahulu, karena berdasarkan operasi daftar tertaut, kapasitas pengumpulan akan secara otomatis meningkat dengan penambahan elemen.
3. Memori yang ditempati oleh koleksi setelah LinkedList dihapus secara otomatis dikurangi, dan tidak perlu memanggil metode trimtosize () seperti arraylist
4. Semua metode LinkedList tidak disinkronkan, sehingga tidak aman, dan harus dihindari di lingkungan multi-utas.
5. Analisis di atas didasarkan pada JDK1.7, dan versi lain akan memiliki beberapa perbedaan, sehingga tidak dapat digeneralisasi.
Di atas adalah semua konten artikel ini. Saya berharap ini akan membantu untuk pembelajaran semua orang dan saya harap semua orang akan lebih mendukung wulin.com.