القائمة المرتبطة هي بنية بيانات معقدة. تجعل العلاقة بين البيانات قائمة مرتبطة مقسمة إلى ثلاثة أنواع: القائمة المرتبطة الفردية ، والقائمة المرتبطة الدائرية ، والقائمة المرتبطة ثنائية الاتجاه . سيتم تقديم ما يلي واحد تلو الآخر. القوائم المرتبطة هي نقاط المعرفة الأساسية والمهمة في بنية البيانات. سنتحدث هنا عن تنفيذ القوائم المرتبطة في Java.
عمليات قائمة Java المرتبطة: قائمة متصلة واحدة وقائمة مزدوجة المرتبطة
بضع نقاط تتحدث بشكل أساسي عن:
1. مقدمة في القائمة المرتبطة
2. مبادئ وضروريات تنفيذ القوائم المرتبطة
3. مثال واحد تقطعت بهم السبل
4. مثال مزدوج المرتبطة
1. مقدمة في القائمة المرتبطة
القوائم المرتبطة هي بنية بيانات شائعة نسبيا. على الرغم من أن القوائم المرتبطة أكثر تعقيدًا للتخزين ، إلا أنها أكثر ملاءمة عند الاستعلام. يتم استخدامها بلغات الكمبيوتر المتعددة وفقًا لذلك. هناك العديد من فئات القوائم المرتبطة. يتم تحليل المقالات للحصول على قوائم متصلة واحدة وقوائم مرتبطة مزدوجة. تشبه البيانات الموجودة في القائمة المرتبطة معًا سلسلة ، مما يتيح الوصول بسهولة إلى البيانات.
2. مبادئ وضروريات تنفيذ القوائم المرتبطة
يتم تحليل فقط القوائم المرتبطة الفردية والقوائم المرتبطة المزدوجة هنا. عملية تنفيذ القوائم المرتبطة معقدة بعض الشيء ، لكنها ستجلب العديد من الفوائد. على سبيل المثال ، مع وصول التسوق عبر الإنترنت ، عادةً ما يحزم التجار البضائع في مربع واكتب معلومات العنوان على المربع. يمكن لشركة Express أن تجد المشتري من خلال المعلومات الواردة في المربع ، وتصل البضائع إلى سليمة. بدون حماية الصندوق ، قد يتلف المنتج على طول الطريق. القائمة المرتبطة تشبه المربع الذي يحتوي على معلومات العنوان المكتوبة ، والتي لا تحمي معلومات المنتج فحسب ، بل تكتب أيضًا المعلومات اللوجستية. هناك عقدة رأس في القائمة المرتبطة ، على غرار "القاطرة". طالما تم العثور على عقدة الرأس المقابلة ، يمكنك العمل على القائمة المرتبطة. في هذا التحليل ، تعمل عقدة الرأس فقط كرأس بيانات ولا تحفظ بيانات صالحة.
يظهر مبدأ التنفيذ للقائمة المرتبطة الفردية في الشكل:
مبدأ تنفيذ قائمة المرتبطة مزدوجة:
3. مثال واحد تقطعت بهم السبل
icommoperate <t> فئة تشغيل واجهة:
حزمة LinkListTest ؛ استيراد java.util.map ؛ واجهة عامة icommoperate <t> {public boolean insertnode (t node) ؛ insertposnode boolean public (int pos ، t node) ؛ DELETENODE العام المنطقي (int pos ، خريطة <سلسلة ، كائن> خريطة) ؛ printlink printlink public () ؛}عقدة قائمة واحدة مرتبطة:
حزمة LinkListTest ؛ // عقدة الجدول المربوطة أحادية الفئة Snode {Private String Data ؛ snode snode nextNode ؛ public snode () {} snode (بيانات السلسلة) {this.data = data ؛ this.nextNode = جديد snode () ؛ } السلسلة العامة getData () {return data ؛ } public void setData (string data) {this.data = data ؛ } snode snode getNextNode () {return nextNode ؛ } public void setNextNode (snode nextNode) {this.nextNode = nextNode ؛ } Override public string toString () {return "snode [data =" + data + "]" ؛ }}فئة تشغيل ارتباط واحد:
Package LinkListTest ؛ import java.util.hashmap ؛ import java.util.map ؛ public class singlelinklist تنفذ icommoperate <snode> {private snode head = new 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) {// freef linked list this.head.setNextNode (node) ؛ node.setNextNode (null) ؛ } آخر {// العقدة في القائمة المرتبطة بينما (current.getNextNode ()! = null) {current.getNextNode () ؛ } current.setNextNode (node) ؛ node.setNextNode (null) ؛ } this.size ++ ؛ العلم = صحيح ؛ العلم العودة } / * * أدخل الموضع المحدد لـ POS في القائمة المرتبطة ، بدءًا من 1 ، و POS أكبر من الحجم ، ثم أدخل نهاية القائمة المرتبطة * * / Override Boolean InsertPosnode (int pos ، عقدة snode) {flag boolean = true ؛ snode current = this.head.getNextNode () ؛ if (this.size == 0) {// القائمة الفارغة المرتبطة this.head.setNextNode (node) ؛ node.setNextNode (null) ؛ this.size ++ ؛ } آخر إذا (this.size <pos) {// يكون موضع POS أكبر من طول القائمة المرتبطة ، insertNode (node) ؛ } آخر إذا (pos> 0 && pos <= this.size) {// node في القائمة المرتبطة // 1. ابحث عن العقدة والعقدة الأمامية المراد إدراجها int find = 0 ؛ snode prenode = this.head ؛ // Front Node snode currentNode = current ؛ // Current Node بينما (Find <pos-1 && currentNode.getNextNode ()! = null) {prenode = current ؛ // Front Node تحرك CurrentNode للخلف = currentNode.getNextNode () ؛ // تتحرك العقدة الحالية للخلف العثور على ++ ؛ } // system.out.println (prenode) ؛ // system.out.println (currentNode) ؛ // 2. Insert Node prenode.setNextNode (Node) ؛ node.setNextNode (currentNode) ؛ this.size ++ ؛ System.out.println ("تم إدراج العقدة في القائمة المرتبطة") ؛ } آخر {system.out.println ("خطأ معلومات الموضع") ؛ العلم = خطأ ؛ } العلم الإرجاع ؛ } / * * حدد عقدة POS للقائمة المرتبطة وحذف العقدة المقابلة. الطريقة: ابحث عن العقد الأمامية والخلفية لحذف وحذف. بدءًا من 1 * */ Override Public Boolean Deletenode (int pos) {boolean flag = false ؛ snode current = this.head.getNextNode () ؛ if (pos <= 0 || pos> this.size || current == null) {system.out.println ("خطأ في معلومات الموضع أو عدم وجود معلومات في القائمة المرتبطة") ؛ } آخر {// 1. ابحث عن العقد الأمامية والخلفية لحذف int find = 0 ؛ snode prenode = this.head ؛ // Front Node snode nextNode = current.getNextNode () ؛ // Back Node بينما (Find <pos-1 && nextNode.getNextNode ()! = null) {prenode = current ؛ // يتم نقل العقدة الأمامية إلى الوراء nextNode = nextNode.getNextNode () ؛ // يتم نقل العقدة الخلفية إلى الوراء Find ++ ؛ } // system.out.println (prenode) ؛ // system.out.println (nextNode) ؛ // 2. حذف العقدة prenode.setNextNode (nextNode) ؛ System.gc () ؛ this.size-- ؛ العلم = صحيح ؛ } العلم الإرجاع ؛ } / * * حدد عقدة POS للقائمة المرتبطة وتعديل العقدة المقابلة. بدءًا من 1 * */ Override Public Boolean Updatenode (int pos ، خريطة <string ، كائن> خريطة) {boolean flag = false ؛ Snode Node = getNode (pos ، map) ؛ // احصل على العقدة في الموضع المقابل if (node! = null) {string data = (string) map.get ("data") ؛ Node.setData (البيانات) ؛ العلم = صحيح ؛ } العلم الإرجاع ؛ } / * * ابحث عن عقدة POS للقائمة المرتبطة المحددة ، بدءًا من 1 * * / Override public snode getNode (int pos ، خريطة <string ، كائن> خريطة) {snode current = this.head.getNextNode () ؛ if (pos <= 0 || pos> this.size || current == null) {system.out.println ("معلومات الموضع غير صحيحة أو أن القائمة المرتبطة غير موجودة") ؛ العودة لاغية. } int find = 0 ؛ بينما (البحث <pos-1 && current! = null) {current = current.getNextNode () ؛ البحث ++ ؛ } إرجاع التيار ؛ } / * * طباعة قائمة مرتبطة * * / Override public void printLink () {int length = this.size ؛ if (length == 0) {system.out.println ("القائمة المرتبطة فارغة!") ؛ يعود ؛ } snode current = this.head.getNextNode () ؛ int find = 0 ؛ System.out.println ("إجمالي عدد العقد:" + طول + "منها") ؛ بينما (current! = null) {system.out.println ("th" + (++ find) + "العقد:" + الحالية) ؛ current = current.getNextNode () ؛ }} public static void main (string [] args) {singlelinklist sll = new SingLelinkList () ؛ snode node1 = new snode ("node1") ؛ snode node2 = new snode ("node2") ؛ snode node3 = new snode ("node3") ؛ snode node4 = new snode ("node4") ؛ snode node5 = new 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 ("delete"+pos2+"العقد:") ؛ sll.deletenode (pos2) ؛ sll.printlink () ؛ system.out.println ("************************************* تعديل عقدة الموقع المحددة للقائمة المرتبطة *************************************** int pos3 = 2 ؛ System.out.println ("تعديل العقد"+pos3+":") ؛ الخريطة <string ، Object> map = new HashMap <> () ؛ map.put ("البيانات" ، "هذا اختبار") ؛ sll.updatenode (pos3 ، map) ؛ sll.printlink () ؛ }}4. مثال مزدوج المرتبطة
icommoperate <t> فئة تشغيل واجهة:
حزمة LinkListTest ؛ استيراد java.util.map ؛ واجهة عامة icommoperate <t> {public boolean insertnode (t node) ؛ insertposnode boolean public (int pos ، t node) ؛ DELETENODE العام المنطقي (int pos ، خريطة <سلسلة ، كائن> خريطة) ؛ printlink printlink public () ؛}عقدة قائمة مرتبطة مزدوجة:
حزمة LinkListTest ؛ // Dual-duontualuate Table Node Public Class Dnode {private dnode priornode ؛ بيانات السلسلة الخاصة ؛ dnode الخاص nextNode ؛ public dnode () {} public dnode (string data) {this.priornode = new dnode () ؛ this.data = البيانات ؛ this.nextNode = new dnode () ؛ } dnode public getPriOrnode () {return priornode ؛ } public void setPriOrnode (dnode priornode) {this.priornode = priornode ؛ } السلسلة العامة 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 + "]" ؛ }}فئة تنفيذ قائمة المرتبطة مزدوجة:
Package LinkListTest ؛ import java.util.hashmap ؛ import java.util.map ؛ public class doubleLinklist تنفذ icommoperate <dnode> {private dnode head = new dnode ("head") ؛ حجم int الخاص = 0 ؛ public int getSize () {return this.size ؛ } / * * أدخل القائمة المرتبطة ، أدخلها بالنهاية في كل مرة * * * / Override Boolean InsertNode (DNODE NODE) {boolean flag = false ؛ dnode current = this.head ؛ if (this.size == 0) {// freef linked list this.head.setNextNode (node) ؛ node.setPriOnde (this.head) ؛ node.setNextNode (null) ؛ } آخر {// العقدة في القائمة المرتبطة بينما (current.getNextNode ()! = null) {current.getNextNode () ؛ } current.setNextNode (node) ؛ node.setNextNode (null) ؛ Node.setPriOnde (الحالي) ؛ } this.size ++ ؛ العلم = صحيح ؛ العلم العودة } / * * أدخل الموضع المحدد لـ POS في القائمة المرتبطة ، بدءًا من 1 ، و POS أكبر من الحجم ، أدخل نهاية القائمة المرتبطة * * / Override Boolean Public InsertPosnode (int pos ، dnode node) {boolean flag = true ؛ dnode current = this.head.getNextNode () ؛ if (this.size == 0) {// القائمة المرتبطة فارغة this.head.setNextNode (node) ؛ node.setNextNode (null) ؛ node.setPriOnde (this.head) ؛ this.size ++ ؛ } آخر إذا (pos> this.size) {// pos هو أكبر من طول القائمة المرتبطة ، أدخل insertNode (العقدة) ؛ } آخر إذا (pos> 0 && pos <= this.size) {// node في القائمة المرتبطة // 1. ابحث عن عقدة pos ليتم إدراجها ، أدخل موقع POS الحالي int find = 0 ؛ بينما (البحث <pos-1 && current.getNextNode ()! = null) {current = current.getNextNode () ؛ البحث ++ ؛ } // 2. insert node if (current.getNextNode () == null) {// tail node.setpriornode (current) ؛ node.setNextNode (null) ؛ current.setNextNode (العقدة) ؛ } if if (current.getNextNode ()! = null) {// intermediate node node.setPriOrnode (current.getPriOrnode ()) ؛ node.setNextNode (الحالي) ؛ current.getPriOnd (). setNextNode (العقدة) ؛ current.setPriOnde (العقدة) ؛ } this.size ++ ؛ } آخر {system.out.println ("خطأ معلومات الموضع") ؛ العلم = خطأ ؛ } العلم الإرجاع ؛ } / * * حدد عقدة POS للقائمة المرتبطة ، حذف العقدة المقابلة ، بدءًا من 1 * * / Override Boolean Deletenode (int pos) {boolean flag = false ؛ dnode current = this.head.getNextNode () ؛ if (pos <= 0 || pos> this.size || current == null) {system.out.println ("معلومات الموضع غير صحيحة أو أن القائمة المرتبطة غير موجودة") ؛ } آخر {// 1. ابحث عن الموقع المراد حذفه عقدة pos int find = 0 ؛ بينما (البحث <pos-1 && current.getNextNode ()! = null) {current = current.getNextNode () ؛ البحث ++ ؛ } // 2. حذف العقدة if (current.getNextNode () == null) {// the tail node current.getPriOrnode (). setNextNode (null) ؛ } if if (current.getNextNode ()! = null) {// العقدة المتوسطة current.getPriOrnode (). setNextNode (current.getNextNode ()) ؛ current.getNextNode (). } system.gc () ؛ this.size-- ؛ العلم = صحيح ؛ } العلم الإرجاع ؛ } / * * حدد عقدة POS للقائمة المرتبطة وتعديل العقدة المقابلة. ابدأ في 1 * */ Override Public Boolean UpdatEnode (int pos ، Map <String ، Object> map) {boolean flag = false ؛ عقدة dnode = getNode (pos ، map) ؛ if (node! = null) {string data = (string) map.get ("data") ؛ Node.setData (البيانات) ؛ العلم = صحيح ؛ } العلم الإرجاع ؛ } / * * ابحث عن عقدة POS للقائمة المرتبطة المحددة ، ابدأ في 1 * * * / Override public dnode getNode (int pos ، map <string ، object> map) {dnode current = this.head.getNextNode () ؛ if (pos <= 0 || pos> this.size || current == null) {system.out.println ("معلومات الموضع غير صحيحة أو أن القائمة المرتبطة غير موجودة") ؛ العودة لاغية. } int find = 0 ؛ بينما (البحث <pos-1 && current! = null) {current = current.getNextNode () ؛ البحث ++ ؛ } إرجاع التيار ؛ } / * * طباعة قائمة مرتبطة * * / Override public void printLink () {int length = this.size ؛ if (length == 0) {system.out.println ("القائمة المرتبطة فارغة!") ؛ يعود ؛ } dnode current = this.head.getNextNode () ؛ int find = 0 ؛ System.out.println ("إجمالي عدد العقد:" + طول + "منها") ؛ بينما (current! = null) {system.out.println ("th" + (++ find) + "العقد:" + الحالية) ؛ current = current.getNextNode () ؛ }} public static void main (string [] args) {doubleLinkList dll = new 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 ("delete"+pos2+"العقد:") ؛ dll.deletenode (pos2) ؛ dll.printLink () ؛ system.out.println ("********************************** تعديل العقد المحددة في القائمة المرتبطة ***************************************") ؛ int pos3 = 2 ؛ System.out.println ("تعديل العقد"+pos3+":") ؛ الخريطة <string ، Object> map = new HashMap <> () ؛ map.put ("البيانات" ، "هذا اختبار") ؛ dll.updatenode (pos3 ، map) ؛ dll.printLink () ؛ }}شكرا لك على القراءة ، آمل أن تساعدك. شكرا لك على دعمك لهذا الموقع!