Daftar tertaut adalah struktur data yang kompleks. Hubungan antara data membuat daftar tertaut dibagi menjadi tiga jenis: daftar tertaut tunggal, daftar tertaut melingkar, dan daftar ditautkan dua arah . Berikut ini akan diperkenalkan satu per satu. Daftar yang ditautkan adalah titik pengetahuan dasar dan penting dalam struktur data. Di sini kita akan berbicara tentang implementasi daftar tertaut di Java.
Java Linked Listed Operations: Daftar Single-Linked dan Linked Linked List
Beberapa poin terutama dibicarakan:
1. Pengantar ke daftar tertaut
2. Prinsip dan Kebutuhan untuk Implementasi Daftar Tertaut
3. Contoh beruntai tunggal
4. Contoh terkait ganda
1. Pengantar ke daftar tertaut
Daftar tertaut adalah struktur data yang relatif umum. Meskipun daftar tertaut lebih rumit untuk disimpan, mereka lebih nyaman saat meminta. Mereka digunakan dalam beberapa bahasa komputer yang sesuai. Ada banyak kategori daftar tertaut. Artikel dianalisis untuk daftar tunggal dan daftar double-linked. Data dalam daftar tertaut adalah seperti dihubungkan bersama dengan rantai, memungkinkan akses mudah ke data.
2. Prinsip dan Kebutuhan untuk Implementasi Daftar Tertaut
Hanya daftar tunggal dan daftar double-link yang dianalisis di sini. Proses implementasi daftar tertaut agak rumit, tetapi akan membawa banyak manfaat. Misalnya, dengan kedatangan belanja online, pedagang biasanya mengemas barang dalam sebuah kotak dan tulis informasi alamat di kotak. Perusahaan ekspres dapat menemukan pembeli melalui informasi di kotak, dan barang tiba utuh. Tanpa perlindungan kotak, produk mungkin rusak di sepanjang jalan. Daftar yang ditautkan seperti kotak dengan informasi alamat yang ditulis, yang tidak hanya melindungi informasi produk, tetapi juga menulis informasi logistik. Ada simpul kepala dalam daftar tertaut, mirip dengan "lokomotif". Selama node kepala yang sesuai ditemukan, Anda dapat beroperasi pada daftar yang ditautkan. Dalam analisis ini, simpul kepala hanya bertindak sebagai header data dan tidak menyimpan data yang valid.
Prinsip implementasi daftar tertaut tunggal ditunjukkan pada gambar:
Prinsip Implementasi Daftar Double-Linked:
3. Contoh beruntai tunggal
ICMOMPERATASI <T> Kelas Operasi Antarmuka:
Paket LinkListTest; import java.util.map; antarmuka publik Icommoperate <t> {public boolean insertNode (t node); Public Boolean InsertPosNode (int pos, T node); deletenode boolean publik (int pos, peta <string, objek> peta); public void printlink ();}Node daftar linked tunggal:
Paket LinkListTest; // Tabel Single-Connected Node Public Class Snode {Private String Data; Private Snode NextNode; public snode () {} public snode (string data) {this.data = data; this.nextNode = snode baru (); } public String getData () {return data; } public void setData (string data) {this.data = data; } public snode getNextNode () {return nextNode; } public void setNextNode (snode nextNode) {this.nextNode = nextNode; } @Override public string toString () {return "snode [data =" + data + "]"; }}Kelas Operasi Tautan Tunggal:
Paket LinkListTest; import java.util.hashmap; import java.util.map; kelas publik SingLelinkList mengimplementasikan ICIMMOPERASI <Snode> {private snode head = snode baru ("head"); // pointer header publik, tidak berubah setelah deklarasi ukuran int pribadi = 0; int int getsize () {return this.size; } / * * Masukkan daftar yang ditautkan, masukkan ke ujung setiap kali * / @Override public boolean insertNode (snode node) {boolean flag = false; Snode arus = this.head; if (this.size == 0) {// Daftar linked kosong this.head.setNextNode (node); node.setNextNode (null); } else {// node dalam daftar tertaut while (current.getNextNode ()! = null) {current = current.getNextNode (); } current.setNextNode (node); node.setNextNode (null); } this.size ++; bendera = true; pengembalian bendera; } / * * Masukkan posisi POS yang ditentukan dalam daftar tertaut, mulai dari 1, dan POS lebih besar dari ukuran, kemudian masukkan ujung daftar yang ditautkan * * / @Override Public Boolean InsertPoSnode (int POS, Node Snode) {boolean flag = true; Snode arus = this.head.getNextNode (); if (this.size == 0) {// daftar ditautkan kosong this.head.setNextNode (node); node.setNextNode (null); this.size ++; } lain jika (this.size <pos) {// posisi pos lebih besar dari panjang daftar yang ditautkan, insertNode (node); } else if (pos> 0 && pos <= this.size) {// node dalam daftar tertaut // 1. Temukan simpul dan simpul depan yang akan dimasukkan int find = 0; Snode prenode = this.head; // simpul depan snode currentNode = arus; // Node saat ini while (temukan <pos-1 && currentNode.getNextNode ()! = Null) {prenode = current; // simpul depan bergerak mundur letrentNode = currentNode.getNextNode (); // Node saat ini bergerak ke belakang menemukan ++; } // System.out.println (prenode); // System.out.println (currentNode); // 2. Masukkan node prenode.setNextNode (node); node.setNextNode (currentNode); this.size ++; System.out.println ("Node telah dimasukkan ke dalam daftar tertaut"); } else {System.out.println ("Kesalahan informasi posisi"); bendera = false; } mengembalikan bendera; } / * * Tentukan node pos dari daftar tertaut dan hapus simpul yang sesuai. Metode: Temukan node depan dan belakang untuk dihapus dan dihapus. Mulai dari 1 * */ @Override public boolean deletenode (int pos) {boolean flag = false; Snode arus = this.head.getNextNode (); if (pos <= 0 || pos> this.size || arus == null) {System.out.println ("Kesalahan informasi posisi atau tidak ada informasi dalam daftar tertaut"); } else {// 1. Temukan node depan dan belakang untuk menghapus int find = 0; Snode prenode = this.head; // node depan snode nextNode = current.getNextNode (); // Back node while (temukan <pos-1 && nextNode.getNextNode ()! = Null) {prenode = current; // simpul depan dipindahkan kembali nextNode = nextNode.getNextNode (); // simpul belakang dipindahkan kembali Find ++; } // System.out.println (prenode); // system.out.println (nextNode); // 2. Hapus node prenode.setNextNode (nextNode); System.gc (); this.size--; bendera = true; } mengembalikan bendera; } / * * Tentukan node pos dari daftar tertaut dan ubah node yang sesuai. Mulai dari 1 * */ @Override public boolean updateNode (int pos, peta <string, objek> peta) {boolean flag = false; Snode node = getNode (pos, peta); // Dapatkan node pada posisi yang sesuai if (node! = Null) {string data = (string) map.get ("data"); node.setData (data); bendera = true; } mengembalikan bendera; } / * * Temukan node pos dari daftar tertaut yang ditentukan, mulai dari 1 * * / @Override public snode getNode (int pos, peta <string, objek> peta) {snode arus = this.head.getNextNode (); if (pos <= 0 || pos> this.size || arus == null) {System.out.println ("Informasi posisi salah atau daftar yang ditautkan tidak ada"); kembali nol; } int find = 0; while (temukan <pos-1 && current! = null) {current = current.getNextNode (); Temukan ++; } return arus; } / * * Cetak Daftar Tertaut * * / @Override public void printlink () {int length = this.size; if (length == 0) {System.out.println ("Daftar tertaut kosong!"); kembali ; } Snode arus = this.head.getNextNode (); int find = 0; System.out.println ("Jumlah total node:" + panjang + "yang"); while (saat ini! = null) {System.out.println ("th" + (++ find) + "node:" + arus); current = current.getNextNode (); }} public static void main (string [] args) {singleLinkList sll = new singleLinkList (); Snode node1 = snode baru ("node1"); Snode node2 = snode baru ("node2"); Snode node3 = snode baru ("node3"); Snode node4 = snode baru ("node4"); Snode node5 = snode baru ("node5"); Snode node6 = snode baru ("masukkan posisi yang ditentukan"); sll.insertposnode (sll.getsize ()+1, node1); sll.insertposnode (sll.getsize ()+1, node2); sll.insertposnode (sll.getsize ()+1, node3); sll.insertposnode (sll.getsize ()+1, node4); sll.insertposnode (sll.getsize ()+1, node5); // sll.insertnode (node1); // sll.insertnode (node2); // sll.insertnode (node3); // sll.insertnode (node4); // sll.insertnode (node5); System.out.println ("**************************"); sll.printlink (); System.out.println ("*****************************"); int pos = 2; System.out.println ("Dapatkan data posisi"+pos+"dari daftar tertaut:"+sll.getnode (POS, null)); System.out.println ("************************** Sisipkan node ke posisi yang ditentukan dari daftar tertaut ******************************"); int pos1 = 2; System.out.println("Insert data into "+pos1+"" nodes: "); sll.insertPosNode(pos1, node6); sll.printLink(); System.out.println("************************************Delete the specified location node of the linked list*************************************"); int pos2 = 2; POS3;4. Contoh terkait ganda
ICMOMPERATASI <T> Kelas Operasi Antarmuka:
Paket LinkListTest; import java.util.map; antarmuka publik Icommoperate <t> {public boolean insertNode (t node); Public Boolean InsertPosNode (int pos, T node); deletenode boolean publik (int pos, peta <string, objek> peta); public void printlink ();}Node daftar double-linked:
Paket LinkListTest; // Dual-Contiguous Table Node Public Class DNode {Private DNode Priornode; data string pribadi; private dnode nextNode; dnode publik () {} dnode publik (data string) {this.priornode = dnode baru (); this.data = data; this.nextNode = dnode baru (); } public dnode getPriornode () {return priornode; } public void setPriornode (dnode priornode) {this.priornode = priornode; } public String getData () {return data; } public void setData (string data) {this.data = data; } public dnode getNextNode () {return nextNode; } public void setNextNode (dnode nextNode) {this.nextNode = nextNode; } @Override public string toString () {return "dnode [data =" + data + "]"; }}Kelas Implementasi Daftar Double-Linked:
Paket LinkListTest; import java.util.hashmap; import java.util.map; kelas publik DoublelinkList mengimplementasikan ICommoperate <Dnode> {private dnode head = dnode baru ("head"); Ukuran int pribadi = 0; int int getsize () {return this.size; } / * * Masukkan daftar yang ditautkan, masukkan ke ujung setiap kali * * / @Override public boolean insertNode (node dnode) {boolean flag = false; Dnode arus = this.head; if (this.size == 0) {// Daftar linked kosong this.head.setNextNode (node); node.setPriornode (this.head); node.setNextNode (null); } else {// node dalam daftar tertaut while (current.getNextNode ()! = null) {current = current.getNextNode (); } current.setNextNode (node); node.setNextNode (null); node.setPriornode (saat ini); } this.size ++; bendera = true; pengembalian bendera; } / * * Masukkan posisi POS yang ditentukan dalam daftar tertaut, mulai dari 1, dan POS lebih besar dari ukuran, masukkan ujung daftar yang ditautkan * * / @Override Public Boolean InsertPosNode (int POS, node DNode) {boolean flag = true; Dnode arus = this.head.getNextNode (); if (this.size == 0) {// Daftar yang ditautkan kosongkan this.head.setNextNode (node); node.setNextNode (null); node.setPriornode (this.head); this.size ++; } lain jika (pos> this.size) {// Posisi POS lebih besar dari panjang daftar yang ditautkan, masukkan ujungnya insertNode (node); } else if (pos> 0 && pos <= this.size) {// node dalam daftar tertaut // 1. Temukan node POS yang akan dimasukkan, masukkan node POS Node saat ini menemukan = 0; while (temukan <pos-1 && current.getNextNode ()! = null) {current = current.getNextNode (); Temukan ++; } // 2. Masukkan node if (current.getNextNode () == null) {// node tail node.setPriornode (saat ini); node.setNextNode (null); current.setNextNode (node); } else if (current.getNextNode ()! = null) {// node node intermediate.setPriornode (current.getPriornode ()); node.setNextNode (saat ini); current.getPriornode (). setnextNode (node); current.setPriornode (node); } this.size ++; } else {System.out.println ("Kesalahan informasi posisi"); bendera = false; } mengembalikan bendera; } / * * Tentukan node pos dari daftar tertaut, hapus simpul yang sesuai, mulai dari 1 * * / @override public boolean deletenode (int pos) {boolean flag = false; Dnode arus = this.head.getNextNode (); if (pos <= 0 || pos> this.size || arus == null) {System.out.println ("Informasi posisi salah atau daftar yang ditautkan tidak ada"); } else {// 1. Temukan lokasi yang akan dihapus POS node int find = 0; while (temukan <pos-1 && current.getNextNode ()! = null) {current = current.getNextNode (); Temukan ++; } // 2. Hapus node if (current.getNextNode () == null) {// node tail current.getPriornode (). SetnextNode (null); } else if (current.getNextNode ()! = null) {// node intermediate current.getPriornode (). setnextNode (current.getNextNode ()); current.getNextNode (). setPrioNnode (current.getPriornode ()); } System.gc (); this.size--; bendera = true; } mengembalikan bendera; } / * * Tentukan node pos dari daftar tertaut dan ubah node yang sesuai. Mulai dari 1 * */ @Override public boolean updateNode (int pos, peta <string, objek> peta) {boolean flag = false; Node dnode = getNode (pos, peta); if (node! = null) {string data = (string) map.get ("data"); node.setData (data); bendera = true; } mengembalikan bendera; } / * * Temukan node pos dari daftar tertaut yang ditentukan, mulai dari 1 * * / @Override public dnode getNode (int pos, peta <string, objek> peta) {dnode arus = this.head.getNextNode (); if (pos <= 0 || pos> this.size || arus == null) {System.out.println ("Informasi posisi salah atau daftar yang ditautkan tidak ada"); kembali nol; } int find = 0; while (temukan <pos-1 && current! = null) {current = current.getNextNode (); Temukan ++; } return arus; } / * * Cetak Daftar Tertaut * * / @Override public void printlink () {int length = this.size; if (length == 0) {System.out.println ("Daftar tertaut kosong!"); kembali ; } Dnode arus = this.head.getNextNode (); int find = 0; System.out.println ("Jumlah total node:" + panjang + "yang"); while (saat ini! = null) {System.out.println ("th" + (++ find) + "node:" + arus); current = current.getNextNode (); }} public static void main (string [] args) {doublelinkList Dll = new doublelinkList (); Dnode node1 = dnode baru ("node1"); Dnode node2 = dnode baru ("node2"); Dnode node3 = dnode baru ("node3"); Dnode node4 = dnode baru ("node4"); Dnode node5 = dnode baru ("node5"); Dnode node6 = dnode baru ("masukkan posisi yang ditentukan"); dll.insertposnode (10, node1); dll.insertposnode (10, node2); dll.insertposnode (10, node3); dll.insertposnode (10, node4); dll.insertposnode (10, node5); // dll.insertnode (node1); // dll.insertnode (node2); // dll.insertnode (node3); // dll.insertNode (node4); // dlll.insertNode (node5); System.out.println ("**************************"); dll.printlink (); System.out.println ("********************************"); int pos = 2; System.out.println ("Dapatkan data posisi"+pos+"dari daftar yang ditautkan:"+dll.getNode (pos, null)); System.out.println ("************************** Sisipkan node ke posisi yang ditentukan dari daftar tertaut ******************************"); int pos1 = 2; System.out.println ("Masukkan data ke dalam node"+pos1+":"); dll.insertposnode (pos1, node6); dll.printlink (); System.out.println ("***************************** Hapus node yang ditentukan dalam daftar tertaut ***********************************"); int pos2 = 7; System.out.println ("Delete"+Pos2+"node:"); dllel.deletenode (pos2); dll.printlink (); System.out.println ("******************************** Modifikasi node yang ditentukan dalam daftar tertaut ***********************************"); int pos3 = 2; System.out.println ("Ubah node"+pos3+":"); Peta <String, Object> MAP = HashMap baru <> (); peta.put ("data", "Ini adalah tes"); dll.updatenode (POS3, peta); dll.printlink (); }}Terima kasih telah membaca, saya harap ini dapat membantu Anda. Terima kasih atas dukungan Anda untuk situs ini!