Simulasi tabel single-linked
Tabel linier:
Tabel linier (juga disebut tabel berurutan) adalah struktur data yang paling mendasar, paling sederhana dan paling umum digunakan.
Hubungan antara elemen data dalam tabel linier adalah hubungan satu-ke-satu, yaitu, kecuali untuk elemen data pertama dan terakhir, elemen data lainnya terhubung ke akhir.
Struktur logis tabel linier sederhana, yang mudah diimplementasikan dan dioperasikan.
Dalam aplikasi praktis, tabel linier digunakan dalam bentuk tabel linier khusus seperti tumpukan, antrian, dan string.
Karakteristik dasar struktur linier adalah:
1. Harus ada "elemen pertama" yang unik dalam koleksi;
2. Harus ada "elemen terakhir" yang unik dalam koleksi;
3. Kecuali untuk elemen terakhir, ada penerus unik (item terbaru);
4. Kecuali untuk elemen pertama, ada drive depan yang unik (bagian depan).
Daftar Tertaut: Daftar Tertaut
Daftar tertaut adalah struktur penyimpanan yang tidak kontinu dan non-sekuensial pada unit penyimpanan fisik. Urutan logis elemen data adalah bahwa setiap item data yang diimplementasikan melalui urutan tautan pointer dalam daftar tertaut terkandung dalam "titik tautan".
Tautan adalah objek kelas, dan jenis ini dapat disebut tautan. Ada banyak tautan serupa dalam daftar tertaut, dan setiap tautan berisi bidang berikutnya yang dirujuk ke tautan berikutnya.
Objek Daftar Tertaut itu sendiri memiliki referensi ke node tautan pertama. (Jika tidak ada terlebih dahulu, itu tidak dapat ditemukan)
Daftar yang ditautkan tidak dapat secara langsung mengakses item data seperti array (menggunakan subskrip), tetapi perlu diposisikan dengan hubungan antara data, yaitu, mengakses tautan berikutnya yang dirujuk oleh node tautan, dan kemudian yang berikutnya, sampai data yang diperlukan diakses dan kompleksitas waktu untuk menyisipkan dan menghapus data yang diperlukan pada kepala adalah O (1), karena hanya poin referensi yang diperlukan. Operasi ini memerlukan rata -rata pencarian setengah dari node dalam daftar tertaut, dengan efisiensi O (n).
Daftar Tertaut Tunggal:
Tabel linier diwakili oleh "urutan node" dan disebut daftar tertaut linier (daftar tertaut tunggal)
Ini adalah struktur data akses rantai, menggunakan satu set unit penyimpanan dengan alamat sewenang -wenang untuk menyimpan elemen data dalam tabel linier. (Set sel memori ini bisa kontinu atau terputus)
Struktur node tautan:
Data bidang data yang menyimpan nilai simpul; bidang pointer (bidang rantai) yang menyimpan referensi simpul selanjutnya
Daftar tertaut menautkan node N dari tabel linier bersama -sama dalam urutan logisnya melalui domain tautan dari setiap node.
Daftar tertaut dengan hanya satu bidang tautan per node disebut daftar tautan tunggal. Dalam satu arah, hanya ada referensi untuk nodul berikutnya.
/*** Daftar Tertaut Tunggal: Metode Penyisipan Header dan Keluar Pertama* Sisi kiri dari daftar tertaut disebut kepala rantai dan sisi kanan disebut ekor rantai. * Metode Sisipkan Header untuk Membangun Daftar Tertaut Tunggal diperoleh dengan melihat ujung kanan daftar tertaut sebagai tetap, dan daftar tertaut terus meluas ke kiri. * Hal pertama yang berasal dari metode penyisipan header adalah simpul ekor * @author stone */ kelas publik singleLinkedlist <T> {tautan pribadi <T> pertama; // Node pertama public singleLinkedList () {} public boolean isEmpty () {return first == null; } public void InsertFirst (data T) {// Masukkan ke kepala tautan rantai <T> newLink = tautan baru <T> (data); newLink.next = pertama; // Node terdekat menunjuk ke simpul sebelumnya First = newLink; } 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) {// Mendaftar ke ujung rantai tetapi tidak ditemukan kembali null; } else {q = p; p = p.next; }} q.next = p.next; mengembalikan P; } public void displayList () {// TransIP 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 kepala 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 inversi, 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) {singleLinkedList <Integer> list = new SingLelinkedList <Integer> (); list.insertFirst (33); list.insertFirst (78); list.insertFirst (24); list.insertFirst (22); list.insertFirst (56); list.displaylist (); list.deleteFirst (); list.displaylist (); System.out.println ("Find:" + list.find (56)); System.out.println ("Find:" + list.find (33)); System.out.println ("Hapus Find:" + List.Delete (99)); System.out.println ("Hapus Find:" + List.Delete (24)); list.displaylist (); System.out.println ("--- Reverse ----"); list.displayListreverse (); }}Mencetak
List (first-->last): the data is 56 the data is 22 the data is 24 the data is 78 the data is 33 List (first-->last): the data is 22 the data is 24 the data is 78 the data is 33 find:null find:linked_list.SingleLinkedList$Link@4b71bbc9 delete find:null delete Temukan: linked_list.singLelinkedlist$link@17dfafd1 Daftar (pertama-> terakhir): Data adalah 22 data adalah 78 data adalah 33 --- Reverse --- Daftar (pertama-> terakhir): Data adalah 33 data adalah 78 data adalah 22
Daftar Tertaut Tunggal: Metode penyisipan ekor, kembali ke luar - jika ujung kiri dari daftar tertaut diperbaiki, daftar tertaut terus meluas ke kanan, metode untuk membuat daftar tertaut ini disebut metode penyisipan ekor.
Saat membuat daftar tertaut dengan metode penyisipan ekor, pointer kepala diperbaiki, sehingga penunjuk ekor harus diatur untuk memperluas ke kanan daftar yang ditautkan.
Hal pertama yang berasal dari metode penyisipan ekor adalah simpul kepala.
kelas publik singleLinkedList2 <T> {private link <t> head; // simpul pertama singleLinkedList2 () {} public boolean isEmpty () {return head == null; } public void insertLast (data t) {// masukkan tautan <T> newLink = tautan baru <T> (data); if (head! = null) {link <t> nextp = head.next; if (nextp == null) {head.next = newLink; } else {link <t> belakang = null; while (nextp! = null) {belakang = nextp; nextp = nextp.next; } REAR.NEXT = newLink; }} else {head = newLink; }} tautan publik <T> deleteLast () {// hapus ekor tautan rantai <T> p = head; Tautan <T> q = head; while (p.next! = null) {// simpul p berikutnya tidak kosong, q sama dengan p saat ini (yaitu, q adalah yang sebelumnya dan p adalah yang berikutnya). Ketika loop berakhir, Q sama dengan ujung kedua dari rantai q = p; p = p.next; } // hapus q.next = null; mengembalikan P; } tautan publik <T> temukan (t t) {link <t> find = head; 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 (head.data.equals (t)) {link <t> temp = head; head = head.next; // Ubah simpul pertama untuk mengembalikan suhu; }} Tautan <T> p = head; Tautan <T> q = head; while (! p.data.equals (t)) {if (p.next == null) {// berarti bahwa pengembalian null belum ditemukan di akhir rantai; } else {q = p; p = p.next; }} q.next = p.next; mengembalikan P; } public void displayList () {// travel system.out.println ("list (head-> last):"); Tautan <T> saat ini = head; while (current! = null) {current.displaylink (); current = current.next; }} public void displayListreverse () {// tautan traversal terbalik <T> p = head, q = head.next, t; while (q! = null) {// pointer terbalik, dan urutan data yang dilalui adalah mundur t = q.next; // no3 if (p == head) {// Ketika itu adalah header asli, .next kepala 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, head.next kosong, ketika q nol dan tidak menjalankan loop, p adalah item data terbanyak asli. Setelah inversi, P ditugaskan untuk kepala kepala = p; DisplayList (); } tautan kelas <t> {// data titik t link; // Tautan Domain Data <T> Berikutnya; // penunjuk berturut -turut, tautan domain rantai simpul (data t) {this.data = data; } void displayLink () {System.out.println ("Data adalah" + data.toString ()); }} public static void main (string [] args) {singleLinkedList2 <Integer> list = new SingLelinkedList2 <Integer> (); list.insertLast (33); list.insertlast (78); list.insertLast (24); list.insertLast (22); list.insertLast (56); list.displaylist (); list.deleteLast (); list.displaylist (); System.out.println ("Find:" + list.find (56)); System.out.println ("Find:" + list.find (33)); System.out.println ("Hapus Find:" + List.Delete (99)); System.out.println ("Hapus Find:" + List.Delete (78)); list.displaylist (); System.out.println ("---- Reverse -----"); list.displayListreverse (); }}Mencetak
List (head-->last): the data is 33 the data is 78 the data is 24 the data is 22 the data is 56 List (head-->last): the data is 33 the data is 78 the data is 24 the data is 22 find:null find:linked_list.SingleLinkedList2$Link@4b71bbc9 delete find:null delete Temukan: linked_list.singLelinkedlist2$link@17dfafd1 Daftar (head-> last): Data adalah 33 Data 24 Data adalah 22 --- Reverse --- Daftar (head-> Last): Data 22 data adalah 24 Data adalah 33
Simulasikan daftar tertaut berkaitan ganda untuk mengimplementasikan tumpukan dan antrian dengan daftar tertaut
Daftar Tertaut Berlaku Ganda:
Daftar tertaut double-end sangat mirip dengan daftar tertaut tradisional. Ini hanya memiliki atribut baru yang ditambahkan - yaitu, referensi ke tautan terakhir adalah belakang.
Dengan cara ini, memasukkan di ujung rantai akan menjadi sangat mudah. Cukup ubah bagian belakang berikutnya ke simpul yang baru ditambahkan, tanpa melingkar untuk mencari node terakhir, jadi ada InsertFirst dan InsertLast
Saat menghapus header rantai, Anda hanya perlu mengubah titik referensi; Saat menghapus ekor rantai, Anda harus mengosongkan simpul simpul kedua dari kedua.
Tidak ada poin referensi untuk itu, jadi diperlukan loop untuk membaca operasi
/ *** Daftar Tertaut Berlaku Ganda* @Author Stone*/ Public Class TwoEndPointList <T> {Private Link <T> head; // tautan pribadi simpul pertama <T> belakang; // tail pointer publik TwoEndPointList () {} public t peekhead () {if (head! = null) {return head.data; } return null; } public boolean isEmpty () {return head == null; } public void InsertFirst (data T) {// Masukkan ke kepala rantai tautan <T> newLink = tautan baru <T> (data); newLink.next = head; // Node terdekat menunjuk ke node head sebelumnya = newLink; } public void insertLast (data t) {// masukkan tautan <T> newLink = tautan baru <T> (data); if (head == null) {belakang = null; } if (belakang! = NULL) {recre.next = newLink; } else {head = newLink; head.next = belakang; } belakang = newLink; // Lain kali Anda menyisipkan, masukkan dari belakang} public t deleteHead () {// hapus header rantai if (isEmpty ()) return null; Tautan <T> temp = head; head = head.next; // Ubah simpul pertama menjadi simpul berikutnya if (head == null) {<span style = "white-space: pre"> </span> belakang = head; } return temp.data; } public t find (t t) {if (isEmpty ()) {return null; } Tautan <T> find = head; while (find! = null) {if (! find.data.equals (t)) {find = find.next; } else {break; }} if (find == null) {return null; } return find.data; } public t delete (t t) {if (isEmpty ()) {return null; } else {if (head.data.equals (t)) {link <t> temp = head; head = head.next; // Ubah simpul pertama ke simpul berikutnya pengembalian temp.data; }} Tautan <T> p = head; Tautan <T> q = head; 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.data; } public void displayList () {// travel system.out.println ("list (head-> last):"); Tautan <T> saat ini = head; while (current! = null) {current.displaylink (); current = current.next; }} public void displayListreverse () {// Inverse Traversal if (iSempty ()) {return; } Tautan <T> p = head, q = head.next, t; while (q! = null) {// pointer terbalik, dan urutan data yang dilalui adalah mundur t = q.next; // no3 if (p == head) {// Ketika itu adalah kepala asli, .next kepala harus kosong p.next = null; } q.next = p; // no3 -> no1 pointer reverse p = q; // Mulai adalah terbalik q = t; // NO3 MULAI} // Dalam IF di loop di atas, head.next kosong, dan ketika q nol dan tidak menjalankan loop, p adalah item data terbanyak asli. Setelah inversi, P ditugaskan untuk kepala kepala = p; DisplayList (); } tautan kelas <t> {// link node t data; // Tautan Domain Data <T> Berikutnya; // penunjuk berturut -turut, tautan domain rantai simpul (data t) {this.data = data; } void displayLink () {System.out.println ("Data adalah" + data.toString ()); }} public static void main (string [] args) {TwoEndPointList <Integer> list = new TwoEndPointList <Integer> (); list.insertLast (1); list.insertFirst (2); list.insertLast (3); list.insertFirst (4); list.insertLast (5); list.displaylist (); list.deletehead (); list.displaylist (); System.out.println ("Find:" + list.find (6)); System.out.println ("Find:" + list.find (3)); System.out.println ("Hapus Find:" + List.Delete (6)); System.out.println ("Hapus Find:" + List.Delete (5)); list.displaylist (); System.out.println ("--- Reverse ----"); list.displayListreverse (); }}Mencetak
Daftar (head-> last): Data adalah 4 data adalah 2 data adalah 1 data adalah 3 data adalah 5 daftar (head-> last): data adalah 2 data adalah 1 data adalah 3 data adalah 5 temukan: nol temukan: 3 hapus temukan: null delete find: 5 list (head-> last): data adalah 2 data adalah 1 data adalah 3--Reverse-head-head-last): Data adalah 2 data adalah 1 data adalah 3--Reversers-head-head-The Last): data adalah 2 data adalah 1 data adalah 3--Reversers-head-head-The Last): data adalah 2 data adalah 1 Data adalah 3--Reversers-head-head-
Gunakan daftar tertaut untuk mengimplementasikan tumpukan, dan gunakan daftar tunggal yang ditautkan sebelum memasukkannya.
Kelas ini menggunakan daftar tertaut ujung ganda untuk diimplementasikan:
LinkStack kelas publik <T> {private TwoendPointList <T> data; tautan publik () {datas = TwoEnendPointList baru <T> (); } // dimasukkan ke dalam stack public void push (data t) {datas.insertFirst (data); } // Keluarkan stack public t pop () {return datas.deletehead (); } // periksa bagian atas tumpukan publik t peek () {return datas.peekhead (); } // apakah tumpukannya kosong boolean public isempty () {return datas.isempty (); } public static void main (string [] args) {LinkStack <Integer> stack = new LinkStack <Integer> (); untuk (int i = 0; i <5; i ++) {stack.push (i); } untuk (int i = 0; i <5; i ++) {integer peek = stack.peek (); System.out.println ("Peek:" + Peek); } untuk (int i = 0; i <6; i ++) {integer pop = stack.pop (); System.out.println ("Pop:" + Pop); } System.out.println ("----"); untuk (int i = 5; i> 0; i--) {stack.push (i); } untuk (int i = 5; i> 0; i--) {integer peek = stack.peek (); System.out.println ("Peek:" + Peek); } untuk (int i = 5; i> 0; i--) {integer pop = stack.pop (); System.out.println ("Pop:" + Pop); }}}Mencetak
Peek: 4 Peek: 4 Peek: 4 Peek: 4 Peek: 4 Peek: 4 POP: 4 POP: 3 POP: 2 POP: 1 POP: 1 POP: 0 POP: NULL --- PEK: 1 PEK: 1 PEK: 1 PEEK: 1 POP: 1 POP: 1 POP: 2 POP: 4 POP: POP: 5
Antrian Implementasi Daftar Tertaut diimplementasikan menggunakan daftar tertaut berkurang:
linkqueue kelas publik <T> {private TwoendPointList <T> Daftar; tautan publik () {list = TwoEndPointList baru <T> (); } // Masukkan ekor antrian public void insert (data t) {list.insertLast (data); } // hapus kepala tim publik t lepaskan () {return list.deletead (); } // Lihat Kepala Tim Publik T Peek () {return list.peekhead (); } public boolean isEmpty () {return list.isempty (); } public static void main (string [] args) {linkqueue <integer> queue = new LinkQueue <Integer> (); untuk (int i = 1; i <5; i ++) {queue.insert (i); } untuk (int i = 1; i <5; i ++) {integer peek = queue.peek (); System.out.println ("Peek:" + Peek); } untuk (int i = 1; i <5; i ++) {integer reme = queue.remove (); System.out.println ("Hapus:" + Hapus); } System.out.println ("----"); untuk (int i = 5; i> 0; i--) {queue.insert (i); } untuk (int i = 5; i> 0; i--) {integer peek = queue.peek (); System.out.println ("Peek2:" + Peek); } for (int i = 5; i> 0; i--) {integer reme = queue.remove (); System.out.println ("Hapus:" + Hapus); }}}Mencetak
Peek: 1 Peek: 1 Peek: 1 Peek: 1 Peek: 1 Lepas: 1 Lepas: 2 Lepas: 3 Lepas: 4 --- Peek2: 5 Peek2: 5 Peek2: 5 Peek2: 5 Peek2: 5 Lepas: 5 Lepas: 4 Lepaskan: Lepaskan: 2 Lepas: 1