القائمة الثنائية المترابطة (doubly linked list )

القائمة الثنائية المترابطة (doubly linked list ):

لتتمكن من الفهم الجيد لهذه القوائم لابد أن يكون لديك فهم مسبق بالقائمة الأحادية المترابطة (single linked list ).

هي عبارة عن سلسة أشبه ماتكون بعربات قطار  ذات اتجاهين مترابطة مع بعضها البعض.

تتكون هذه القائمة  من :

1.العقدة (node):

هي المكون الأهم في هذه القائمة إذ أنها تحتوي على البيانات المخزنة في القائمة.

و كل عقدة يجب أن يكون لها مؤشرين (reference) أحدهما يشير إلى العقدة السابقة في القائمة و هو السابق (prev)  

و الآخر يشير إلى العقدة التالية في القائمة و هو التالي (next)  لنتمكن من خلالهما بربط كافة العقد في القائمة مع بعضها البعض   .

فبالتالي يمكننا أن نقول أن العقدة الواحدة يجب أن يكون لها  :

2.المؤشر التالي ( next reference):

هو سهم يخرج من الطرف الخلفي للعقدة ليُشير إلى العقدة التالية ((كما هو موضح بالرسمة)).

3.المؤشر السابق (previous reference):

هو سهم يخرج من الطرف الأمامي للعقدة ليُشير إلى العقدة السابقة ((كما هو موضح بالرسمة )).

4. الرأس (header):

و هو بداية القائمة و يكون بأولها و لا يحتوي على أي بيانات و يكون له مؤشر التالي  next  فقط , ليشير من خلاله على العقدة التالية,

بالتالي هو نوع خاص مختلف عن بقية العقد في القائمة إذ أنه لا يحفظ أية بيانات و له مؤشر واحد فقط .

5.الذيل (trailer):

وهو كما يتضح من اسمه إذ أنه سيكون بآخر القائمة و لا يحوي أي بيانات إنما يحتوي على مؤشر واحد فقط ليشير إلى العقدة السابقة في القائمة و هو السابق prev .

, و أيضاً حاله كحال الرأس إذ أنه لا يحفظ أية بيانات وله مؤشر واحد فقط أيضاً .

فلو أردنا تطبيق كل مافي السابق و إجراء بعض العمليات على القائمة باستخدام الجافا :

1.إنشاء القائمة   :class Node 

فسنقوم بداية بإنشاء العناصر الأساسية للقائمة 

package dllist;
public class Node {
  protected int storeD;
  protected Node next;
  protected Node prev;
  public Node(int SD){//constructor
    storeD = SD;
    next = null;
    prev =null;
  }
  public int getStoreD(){return storeD;}//to return the data 
  public Node getNext(){return next ;}
  public Node getPrev(){return prev;}
  
  public void setStoreD(int SD){ storeD=SD;}
  public void setNext(Node n){next=n;}
  public void setPrev(Node p){prev=p;}

}

public class Node {
  protected int storeD;
  protected Node next;
  protected Node prev;

هنا قمنا بإنشاء كلاس يحوي ثلاث متغيرات من نوع protected و هي المكونات الأساسية للقائمة  

و هي عبارة عن:

1. storeD هو متغير يحمل قيمة البيانات المحفوظة داخل القائمة و بما أنني أود حفظ أرقام فبالتالي و ضعتها من نوع int .

2. next  و هو المتغير الذي سيُعبر عن المؤشر التالي و هو من نوع Node  بالتالي هو object من الكلاس Node .

3. prev هو متغير الذي سيُعبر عن المؤشر السابق و هو  من نوع Node  بالتالي هو object من الكلاس Node أيضاً .

public Node(int SD){//constructor
    storeD = SD;
    next = null;
    prev =null;
  }

هذا هو الكونستركتور للكلاس Node يأخذ قيمة البيانات المراد وضعها في القائمة و يعطي بعدها قيم مبدأية لكل من (next ,prev,storeD).

storeD -->تم إسناد قيمة المتغير SD له و هي قيمة يتم إرسالها أثناء إنشاء العقد .

next = null ,prev =null--> هذه القيمة المبدأية لهما لايحملان أي قيمة لأنه لم يتم إنشاء القائمة حتى الآن .

public int getStoreD(){return storeD;}//to return the data 
  public Node getNext(){return next ;}
  public Node getPrev(){return prev;}

هذه الدوال لكل المتغيرات السابقة مهمتها فقط إرجاع قيم هذه المتغيرات . 

public void setStoreD(int SD){ storeD=SD;}
  public void setNext(Node n){next=n;}
  public void setPrev(Node p){prev=p;}

هذه الدوال لكل المتغيرات الثلاث السابقة و هي مهمتها إعطاء قيمة لتلك المتغيرات فقط و لاترجع أي قيمة .

 class DLL  و هو الذي سنضع فيه كافة الدوال التي ستعمل على القائمة :

من إضافة و حذف و طباعة ...

public class DLL {
 protected Node head;
protected Node tail;
protected int size;

بداية سنقوم بتعريف المتغيرات و هي هنا ستكون head , tail,size :

head+tail -->تمثلان رأس و ذيل القائمة .

size -->يمثل عدد العقد في القائمة .

public DLL(){
    head=new Node(0);
    tail=new Node(0);
    tail.setNext(null);//no Node after tail 
    head.setPrev(null);//no node before head 
    tail.setPrev(head);//tail refer to head 
    head.setNext(tail);//head refer to tail 
    }

head +tail --> يحملان قيمة المتغير storeD بصفر لأنها لايحملان أي بيانات و لايتم تخزين البيانات فيهما   .

tail.setNext(null);
head.setPrev(null);

وضعنا tail.setNext -->null لأنه لاتوجد أي عقدة بعده بالتالي كما ذكرت سابقاً بأن له فقط مؤشر واحد  و هو السابق .

وضعنا head.setPrev -->null لأنه لاتوجد أي عقدة قبله بالتالي كما ذكرت سابقاً بأن له فقط مؤشر واحد و هو التالي .

tail.setPrev(head);//tail refer to head 
head.setNext(tail);//head refer to tail 

هنا يشير head إلى  tail و يشير tail إلى head بهذا الشكل :

لأنه لا توجد عقد حتى الأن في القائمة فسيكون بشكل مبدأي كل منهما يشير إلى الآخر .

public boolean isEmpty(){//to check if the list is empty or not 
    return (head.getNext()==tail&&tail.getPrev()==head);
}

isEmpty:

هي دالة تستخدم فقط للتأكد إذا ما كانت القائمة خالية أو لا .

//1.add nodes to the list (in first ) 
public void addF(Node n){
    Node w = head.getNext();
    n.setNext(w);
    n.setPrev(head);
    head.setNext(n);
    w.setPrev(n);
    size ++ ;
}

إضافة عقدة addF :

هي دالة تقوم بإضافة العقد في بداية القائمة و ذلك يعني أن أي عقدة جديدة سيتم إضافتها في أول القائمة و يتم إزاحة العقدة التي كانت بأول القائمة لتكون الثانية و هكذا .

فهي تأخذ متغير من نوع Node أي يمرر لها  ليمثل العقدة الجديدة المراد إضافتها .

كما في التالي :

المطلوب إضافة العقدة v إلى القائمة باستخدام هذه الدالة سيكون شكل القائمة كالتالي :

و سيكون هكذا شكل القائمة عند إضافة أي عقدة باستخدام هذه الدالة .

//2.for print the list 
public void display (){
    Node C = head.getNext();
    while (C.getNext()!=null){
        System.out.println(C.getStoreD());
        C = C.getNext();}
    System.out.println("");
    }

display طباعة :

هذه الدالة تم إنشاؤها لطباعة عناصر القائمة بعد إضافتها .

//3.for delete last node in the list .
public Node delLast(){
    if(isEmpty()){
        System.out.println("ERROR:the list is empty !");
    return null;}
    else {
        Node v=tail.getPrev();
    Node u=v.getPrev();
    tail.setPrev(u);
    u.setNext(tail);
    v.setNext(null);
    v.setPrev(null);
    size--;
    return v;}
}

حذف آخر عقدة delLast :

هذه الدالة لحذف آخر عقدة من القائمة 

بدايةً قبل الحذف يتم التأكد من أن القائمة ليست خالية بوضع دالة
()isEmpty  في شرط فلو كانت هذه القائمة خالية سيقوم بطباعة رسالة خطأ و يقوم بإرجاع قيمة null.

أما في حالة كانت القائمة تحتوي على عقد سيتم حذف العقدة الأخيرة من القائمة و بعدها يقوم بإرجاع العقدة المحذوفة .

فلو كان هذا شكل القائمة قبل الحذف :

فسيتم حذف العقدة V  سيبدو شكل القائمة هكذا : 

 و الان بعدما تعرفنا لبعض أنواع الدوال التي نستطيع استخدامها للتعديل على القوائم الثنائية المترابطة سنقوم باستخدامها .

public class DLList {
    public static void main(String[] args) {
       DLL Linked = new DLL();
       Linked.addF(new Node (10));
       Linked.addF(new Node (20));
       Linked.addF(new Node (30));
       System.out.println(" after add  :");
       Linked.display();
       Linked.delLast();
       System.out.println(" after delete last node:");
       Linked.display();
    }
    

هذا هو main class :

بداية قمنا بعمل object  من كلاس DLL لنستطيع من خلاله استخدام الدوال السابقة .

بالتالي بعد تطبيق كل ما في السابق هكذا سيكون شكل شاشة الإخراج :

output screen :

كلمات دليلية: