รายการที่เชื่อมโยงเป็นโครงสร้างข้อมูลที่ซับซ้อน ความสัมพันธ์ระหว่างข้อมูลทำให้รายการที่เชื่อมโยงแบ่งออกเป็นสามประเภท: รายการที่เชื่อมโยงเดียวรายการที่เชื่อมโยงวงกลมและรายการที่เชื่อมโยงแบบสองทิศทาง ต่อไปนี้จะมีการแนะนำทีละคน รายการที่เชื่อมโยงเป็นจุดความรู้พื้นฐานและสำคัญในโครงสร้างข้อมูล ที่นี่เราจะพูดคุยเกี่ยวกับการใช้งานรายการที่เชื่อมโยงใน Java
การดำเนินการรายการ Java Linked: รายการลิงค์เดียวและรายการเชื่อมโยงสองครั้ง
บางจุดส่วนใหญ่พูดถึง:
1. บทนำสู่รายการที่เชื่อมโยง
2. หลักการและสิ่งจำเป็นสำหรับการใช้งานรายการที่เชื่อมโยง
3. ตัวอย่างที่มีเกลียวเดี่ยว
4. ตัวอย่างเชื่อมโยงสองครั้ง
1. บทนำสู่รายการที่เชื่อมโยง
รายการที่เชื่อมโยงเป็นโครงสร้างข้อมูลที่ค่อนข้างทั่วไป แม้ว่ารายการที่เชื่อมโยงจะมีความซับซ้อนมากขึ้นในการจัดเก็บ แต่ก็สะดวกกว่าเมื่อสอบถาม พวกเขาจะใช้ในหลายภาษาคอมพิวเตอร์ตามลำดับ มีรายการที่เชื่อมโยงมากมาย บทความจะถูกวิเคราะห์สำหรับรายการที่เชื่อมโยงเดียวและรายการเชื่อมโยงสองครั้ง ข้อมูลในรายการที่เชื่อมโยงนั้นเป็นเหมือนการเชื่อมต่อเข้าด้วยกันด้วยโซ่ทำให้สามารถเข้าถึงข้อมูลได้ง่าย
2. หลักการและสิ่งจำเป็นสำหรับการใช้งานรายการที่เชื่อมโยง
มีการวิเคราะห์รายการที่เชื่อมโยงเดียวและรายการเชื่อมโยงสองรายการที่นี่ กระบวนการใช้งานของรายการที่เชื่อมโยงนั้นค่อนข้างซับซ้อน แต่จะนำมาซึ่งประโยชน์มากมาย ตัวอย่างเช่นเมื่อมาถึงการช็อปปิ้งออนไลน์พ่อค้ามักจะบรรจุสินค้าในกล่องและเขียนข้อมูลที่อยู่บนกล่อง บริษัท ด่วนสามารถค้นหาผู้ซื้อผ่านข้อมูลในกล่องและสินค้ามาถึงสภาพสมบูรณ์ หากไม่มีการป้องกันกล่องผลิตภัณฑ์อาจได้รับความเสียหายระหว่างทาง รายการที่เชื่อมโยงเป็นเหมือนกล่องที่มีข้อมูลที่อยู่ที่เขียนซึ่งไม่เพียง แต่ปกป้องข้อมูลผลิตภัณฑ์ แต่ยังเขียนข้อมูลโลจิสติกส์ มีโหนดหัวในรายการที่เชื่อมโยงคล้ายกับ "หัวรถจักร" ตราบใดที่พบโหนดหัวที่สอดคล้องกันคุณสามารถทำงานในรายการที่เชื่อมโยง ในการวิเคราะห์นี้โหนดหัวจะทำหน้าที่เป็นส่วนหัวของข้อมูลเท่านั้นและไม่ได้บันทึกข้อมูลที่ถูกต้อง
หลักการการนำไปใช้ของรายการที่เชื่อมโยงเดียวจะแสดงในรูป:
หลักการการใช้งานรายการเชื่อมโยงสองครั้ง:
3. ตัวอย่างที่มีเกลียวเดี่ยว
Icommoperate <t> คลาสการทำงานของอินเตอร์เฟส:
Package LinkListTest; Import Java.util.map; อินเตอร์เฟสสาธารณะ icommoperate <t> {public boolean insertNode (t node); Public Boolean InsertPosnode (int pos, t node); บูลีนสาธารณะ deleTenode (int pos, แผนที่ <สตริง, วัตถุ> แผนที่); โมฆะสาธารณะ printlink ();}โหนดรายการที่เชื่อมโยงเดียว:
Package LinkListTest; // ตารางที่เชื่อมต่อเดียวโหนดคลาสสาธารณะ Snode {ข้อมูลสตริงส่วนตัว; Snode ส่วนตัว NextNode; สาธารณะ snode () {} snode สาธารณะ (ข้อมูลสตริง) {this.data = data; this.nextNode = new Snode (); } สตริงสาธารณะ getData () {ส่งคืนข้อมูล; } โมฆะสาธารณะ setData (ข้อมูลสตริง) {this.data = ข้อมูล; } snode สาธารณะ getNextNode () {return nextNode; } โมฆะสาธารณะ setNextNode (snode nextNode) {this.nextNode = nextNode; } @Override สตริงสาธารณะ toString () {return "snode [data =" + data + "]"; -คลาส Operation Link Single:
Package LinkListTest; นำเข้า java.util.hashmap; นำเข้า java.util.map; SinglelinkList ระดับสาธารณะใช้ icommoperate <node> {snode private snode = snode ใหม่ ("head"); // ตัวชี้ส่วนหัวสาธารณะไม่เปลี่ยนแปลงหลังจากประกาศขนาด INT ส่วนตัว = 0; public int getsize () {return this.size; } / * * แทรกรายการที่เชื่อมโยงแทรกไปยังจุดสิ้นสุดในแต่ละครั้ง * / @Override public Boolean InsertNode (Snode Node) {Boolean Flag = False; snode current = this.head; if (this.size == 0) {// รายการที่เชื่อมโยงว่างเปล่า this.head.setNextNode (โหนด); node.setNextNode (NULL); } else {// node ในรายการที่เชื่อมโยงในขณะที่ (current.getNextNode ()! = null) {current = current.getNextNode (); } current.setNextNode (โหนด); node.setNextNode (NULL); } this.size ++; ธง = จริง; ธงกลับ; } / * * แทรกตำแหน่งที่ระบุของ POS ในรายการที่เชื่อมโยงเริ่มต้นจาก 1 และ POS มีขนาดมากกว่าขนาดจากนั้นแทรกส่วนท้ายของรายการที่เชื่อมโยง * * / @Override public boolean insertPosnode (int pos, snode node) {boolean flag = true; snode current = this.head.getNextNode (); if (this.size == 0) {// รายการที่เชื่อมโยงว่างเปล่า this.head.setNextNode (โหนด); node.setNextNode (NULL); this.size ++; } อื่นถ้า (this.size <pos) {// ตำแหน่ง POS มากกว่าความยาวของรายการที่เชื่อมโยง, InsertNode (โหนด); } อื่นถ้า (pos> 0 && pos <= this.size) {// โหนดในรายการที่เชื่อมโยง // 1 ค้นหาโหนดและโหนดด้านหน้าที่จะแทรก int find = 0; snode prenode = this.head; // โหนดด้านหน้า snode currentNode = ปัจจุบัน; // โหนดปัจจุบันในขณะที่ (ค้นหา <pos-1 && currentNode.getNextNode ()! = null) {prenode = ปัจจุบัน; // โหนดด้านหน้าเคลื่อนที่ย้อนหลัง currentNode = currentNode.getNextNode (); // โหนดปัจจุบันเคลื่อนที่ไปข้างหลังค้นหา ++; } // system.out.println (prenode); // system.out.println (currentNode); // 2. แทรกโหนด prenode.setNextNode (โหนด); node.setNextNode (currentNode); this.size ++; System.out.println ("โหนดได้รับการแทรกลงในรายการที่เชื่อมโยง"); } else {system.out.println ("ข้อผิดพลาดข้อมูลตำแหน่ง"); ธง = เท็จ; } return flag; } / * * ระบุโหนด POS ของรายการที่เชื่อมโยงและลบโหนดที่เกี่ยวข้อง วิธีการ: ค้นหาโหนดด้านหน้าและด้านหลังเพื่อลบและลบ เริ่มต้นจาก 1 * */ @Override บูลีนสาธารณะ deletenode (int pos) {boolean flag = false; snode current = this.head.getNextNode (); if (pos <= 0 || pos> this.size || current == null) {system.out.println ("ข้อผิดพลาดข้อมูลตำแหน่งหรือไม่มีข้อมูลในรายการที่เชื่อมโยง"); } else {// 1. ค้นหาโหนดด้านหน้าและด้านหลังเพื่อลบ int find = 0; snode prenode = this.head; // โหนดด้านหน้า snode nextNode = current.getNextNode (); // back node ในขณะที่ (ค้นหา <pos-1 && nextNode.getNextNode ()! = null) {prenode = ปัจจุบัน; // โหนดด้านหน้าจะถูกย้ายกลับ nextNode = nextNode.getNextNode (); // โหนดด้านหลังถูกย้ายกลับ find ++; } // system.out.println (prenode); // system.out.println (nextNode); // 2. ลบโหนด prenode.setNextNode (NextNode); System.gc (); สิ่งนี้ขนาด-; ธง = จริง; } return flag; } / * * ระบุโหนด POS ของรายการที่เชื่อมโยงและแก้ไขโหนดที่เกี่ยวข้อง เริ่มต้นจาก 1 * */ @Override Public Boolean UpdAtenode (int pos, แผนที่ <สตริง, วัตถุ> แผนที่) {boolean flag = false; snode node = getNode (pos, map); // รับโหนดที่ตำแหน่งที่สอดคล้องกันถ้า (node! = null) {string data = (string) map.get ("data"); node.setData (ข้อมูล); ธง = จริง; } return flag; } / * * ค้นหาโหนด POS ของรายการที่เชื่อมโยงที่ระบุเริ่มต้นจาก 1 * * / @Override สาธารณะ snode getNode (int pos, แผนที่ <สตริง, วัตถุ> แผนที่) {snode current = this.head.getNextNode (); if (pos <= 0 || pos> this.size || current == null) {system.out.println ("ข้อมูลตำแหน่งไม่ถูกต้องหรือรายการที่เชื่อมโยงไม่มีอยู่"); คืนค่า null; } int find = 0; ในขณะที่ (ค้นหา <pos-1 && current! = null) {current = current.getNextNode (); ค้นหา ++; } return current; } / * * พิมพ์รายการที่เชื่อมโยง * * / @Override โมฆะสาธารณะ printLink () {int length = this.size; if (length == 0) {system.out.println ("รายการที่เชื่อมโยงว่างเปล่า!"); กลับ ; } snode current = this.head.getNextNode (); int find = 0; System.out.println ("จำนวนทั้งหมดของโหนด:" + length + "one"); ในขณะที่ (ปัจจุบัน! = null) {system.out.println ("th" + (++ find) + "โหนด:" + ปัจจุบัน); current = current.getNextNode (); }} โมฆะคงที่สาธารณะหลัก (สตริง [] args) {singlelinklist sll = singlelinklist ใหม่ (); snode node1 = snode ใหม่ ("node1"); snode node2 = snode ใหม่ ("node2"); snode node3 = snode ใหม่ ("node3"); snode node4 = snode ใหม่ ("node4"); snode node5 = snode ใหม่ ("node5"); snode node6 = snode ใหม่ ("แทรกตำแหน่งที่ระบุ"); 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 ("รับข้อมูลตำแหน่ง"+pos+"ของรายการที่เชื่อมโยง:"+sll.getNode (pos, null)); System.out.println ("******************************** แทรกโหนดไปยังตำแหน่งที่ระบุของรายการที่เชื่อมโยง **********************************"); int pos1 = 2; System.out.println ("แทรกข้อมูลลงใน"+pos1+"โหนด:"); sll.insertposnode (pos1, node6); sll.printlink (); System.out.println ("********************************** การลบโหนดตำแหน่งที่ระบุของรายการที่เชื่อมโยง *******************************"); int pos2 = 2; System.out.println ("ลบ"+pos2+"โหนด:"); sll.deletenode (pos2); sll.printlink (); System.out.println ("*********************************** การแก้ไขโหนดตำแหน่งที่ระบุของรายการที่เชื่อมโยง *******************************"); int pos3 = 2; System.out.println ("แก้ไข"+pos3+"โหนด:"); แผนที่ <string, Object> map = new hashmap <> (); map.put ("data", "นี่คือการทดสอบ"); SLL.UPDATENODE (POS3, MAP); sll.printlink (); -4. ตัวอย่างเชื่อมโยงสองครั้ง
Icommoperate <t> คลาสการทำงานของอินเตอร์เฟส:
Package LinkListTest; Import Java.util.map; อินเตอร์เฟสสาธารณะ icommoperate <t> {public boolean insertNode (t node); Public Boolean InsertPosnode (int pos, t node); บูลีนสาธารณะ deleTenode (int pos, แผนที่ <สตริง, วัตถุ> แผนที่); โมฆะสาธารณะ printlink ();}โหนดรายการเชื่อมโยงสองครั้ง:
Package LinkListTest; // dual-contiguous โหนดโหนดสาธารณะคลาสสาธารณะ dnode {ส่วนตัว dnode priornode; ข้อมูลสตริงส่วนตัว Dnode ส่วนตัว NextNode; สาธารณะ dnode () {} dnode สาธารณะ (ข้อมูลสตริง) {this.priornode = new dnode (); this.data = ข้อมูล; this.nextNode = new dnode (); } สาธารณะ dnode getPriorNode () {return priornode; } โมฆะสาธารณะ setPriorNode (dnode priornode) {this.priornode = priornode; } สตริงสาธารณะ getData () {ส่งคืนข้อมูล; } โมฆะสาธารณะ setData (ข้อมูลสตริง) {this.data = ข้อมูล; } สาธารณะ dnode getNextNode () {return nextNode; } โมฆะสาธารณะ setNextNode (dnode nextNode) {this.nextNode = nextNode; } @Override สตริงสาธารณะ toString () {return "dnode [data =" + data + "]"; -คลาสการใช้งานรายการเชื่อมโยงสองครั้ง:
Package LinkListTest; นำเข้า java.util.hashmap; นำเข้า java.util.map; คลาสสาธารณะ doublelinklist ใช้ icommoperate <Dnode> {private dnode head = new dnode ("head"); ขนาด int ส่วนตัว = 0; public int getsize () {return this.size; } / * * แทรกรายการที่เชื่อมโยงแทรกไปยังจุดสิ้นสุดทุกครั้ง * * / @Override บูลีนสาธารณะ InsertNode (โหนด dnode) {flag บูลีน = false; dnode current = this.head; if (this.size == 0) {// รายการที่เชื่อมโยงว่างเปล่า this.head.setNextNode (โหนด); node.setPriornode (this.head); node.setNextNode (NULL); } else {// node ในรายการที่เชื่อมโยงในขณะที่ (current.getNextNode ()! = null) {current = current.getNextNode (); } current.setNextNode (โหนด); node.setNextNode (NULL); Node.SetPriornode (ปัจจุบัน); } this.size ++; ธง = จริง; ธงกลับ; } / * * แทรกตำแหน่งที่ระบุของ POS ในรายการที่เชื่อมโยงเริ่มต้นจาก 1 และ POS มีขนาดใหญ่กว่าขนาดให้ใส่จุดสิ้นสุดของรายการที่เชื่อมโยง * * / @Override public Boolean InsertPosNode (int pos, โหนด dnode) {boolean flag = true; dnode current = this.head.getNextNode (); if (this.size == 0) {// รายการที่เชื่อมโยงนั้นว่างเปล่า this.head.setNextNode (โหนด); node.setNextNode (NULL); node.setPriornode (this.head); this.size ++; } else ถ้า (pos> this.size) {// ตำแหน่ง POS มากกว่าความยาวของรายการที่เชื่อมโยง, แทรก end insertNode (โหนด); } อื่นถ้า (pos> 0 && pos <= this.size) {// โหนดในรายการที่เชื่อมโยง // 1 ค้นหาโหนด POS ที่จะแทรกใส่แทรกตำแหน่งปัจจุบันโหนด POS ปัจจุบัน int find = 0; ในขณะที่ (ค้นหา <pos-1 && current.getNextNode ()! = null) {current = current.getNextNode (); ค้นหา ++; } // 2. แทรกโหนดถ้า (current.getNextNode () == null) {// node node tail node.SetPriorNode (ปัจจุบัน); node.setNextNode (NULL); current.setNextNode (โหนด); } อื่นถ้า (current.getNextNode ()! = null) {// โหนดระดับกลาง node.setPriorNode (current.getPriorNode ()); node.setNextNode (ปัจจุบัน); current.getPriorNode (). setNextNode (โหนด); current.setPriornode (โหนด); } this.size ++; } else {system.out.println ("ข้อผิดพลาดข้อมูลตำแหน่ง"); ธง = เท็จ; } return flag; } / * * ระบุโหนด POS ของรายการที่เชื่อมโยงลบโหนดที่สอดคล้องกันเริ่มต้นจาก 1 * * / @Override บูลีนสาธารณะ deletenode (int pos) {boolean flag = false; dnode current = this.head.getNextNode (); if (pos <= 0 || pos> this.size || current == null) {system.out.println ("ข้อมูลตำแหน่งไม่ถูกต้องหรือรายการที่เชื่อมโยงไม่มีอยู่"); } else {// 1. ค้นหาตำแหน่งที่จะลบ pos node int find = 0; ในขณะที่ (ค้นหา <pos-1 && current.getNextNode ()! = null) {current = current.getNextNode (); ค้นหา ++; } // 2. ลบโหนดถ้า (current.getNextNode () == null) {// โหนดหาง current.getPriorNode (). setNextNode (null); } อื่นถ้า (current.getNextNode ()! = null) {// โหนดกลาง current.getPriorNode (). setNextNode (current.getNextNode ()); current.getNextNode (). setPriorNode (current.getPriorNode ()); } system.gc (); สิ่งนี้ขนาด-; ธง = จริง; } return flag; } / * * ระบุโหนด POS ของรายการที่เชื่อมโยงและแก้ไขโหนดที่เกี่ยวข้อง เริ่มต้นที่ 1 * */ @Override Public Boolean UpdAtenode (int pos, แผนที่ <string, Object> Map) {Boolean Flag = False; dnode node = getNode (pos, map); if (node! = null) {string data = (string) map.get ("data"); node.setData (ข้อมูล); ธง = จริง; } return flag; } / * * ค้นหาโหนด POS ของรายการที่เชื่อมโยงที่ระบุเริ่มต้นที่ 1 * * / @Override สาธารณะ dnode getNode (int pos, แผนที่ <สตริง, วัตถุ> แผนที่) {dnode current = this.head.getNextNode (); if (pos <= 0 || pos> this.size || current == null) {system.out.println ("ข้อมูลตำแหน่งไม่ถูกต้องหรือรายการที่เชื่อมโยงไม่มีอยู่"); คืนค่า null; } int find = 0; ในขณะที่ (ค้นหา <pos-1 && current! = null) {current = current.getNextNode (); ค้นหา ++; } return current; } / * * พิมพ์รายการที่เชื่อมโยง * * / @Override โมฆะสาธารณะ printLink () {int length = this.size; if (length == 0) {system.out.println ("รายการที่เชื่อมโยงว่างเปล่า!"); กลับ ; } dnode current = this.head.getNextNode (); int find = 0; System.out.println ("จำนวนทั้งหมดของโหนด:" + length + "one"); ในขณะที่ (ปัจจุบัน! = null) {system.out.println ("th" + (++ find) + "โหนด:" + ปัจจุบัน); current = current.getNextNode (); }} โมฆะคงที่สาธารณะหลัก (สตริง [] args) {doubleLinkList dll = ใหม่ doublelinkList (); dnode node1 = new dnode ("node1"); dnode node2 = new dnode ("node2"); dnode node3 = new dnode ("node3"); dnode node4 = new dnode ("node4"); dnode node5 = new dnode ("node5"); dnode node6 = new dnode ("แทรกตำแหน่งที่ระบุ"); 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); // dll.insertNode (node5); System.out.println ("********************************"); dll.printlink (); System.out.println ("**********************************"); int pos = 2; System.out.println ("รับข้อมูลตำแหน่ง"+pos+"ของรายการที่เชื่อมโยง:"+dll.getNode (pos, null)); System.out.println ("******************************** แทรกโหนดไปยังตำแหน่งที่ระบุของรายการที่เชื่อมโยง **********************************"); int pos1 = 2; System.out.println ("แทรกข้อมูลลงในโหนด"+pos1+":"); dll.insertposnode (pos1, node6); dll.printlink (); System.out.println ("*********************************** การลบโหนดที่ระบุไว้ในรายการที่เชื่อมโยง *******************************"); int pos2 = 7; System.out.println ("ลบ"+pos2+"โหนด:"); dll.deletenode (pos2); dll.printlink (); System.out.println ("********************************** การแก้ไขโหนดที่ระบุในรายการที่เชื่อมโยง *******************************"); int pos3 = 2; System.out.println ("แก้ไข"+pos3+"โหนด:"); แผนที่ <string, Object> map = new hashmap <> (); map.put ("data", "นี่คือการทดสอบ"); dll.updatenode (pos3, แผนที่); dll.printlink (); -ขอบคุณสำหรับการอ่านฉันหวังว่ามันจะช่วยคุณได้ ขอบคุณสำหรับการสนับสนุนเว็บไซต์นี้!