الـ LinkedList بديل الـ Array ؟

المقدمة

حسنًا وصلنا لثاني مقالة من سلسلة هياكل البيانات Data Structures
هذه المقالة قد تعد أهم مقالة والأساس لما هو قادم
سنتحدث عن الـ LinkedList وسنتطرق للحديث عن أخواتها وأعني بأخواتها الـ Doubly LinkedList والـ Circular LinkedList في مقالات أخرى
وكذلك مع الـ Stack والـ Queue سنتحدث عنها في مقالات أخرى أيضًا

قبل أن نبدأ أريدك أن تعرف أن هذه الهياكل أو الـ Data Structures سهلة وليس بها أي صعوبة كما تظن
وتعلمها سهل وبسيط لكن المعضلة التي يواجهها الكثيرون هي أنهم لا يعرفون متى وكيف يتم استخدامها
وهذا ما سنحاول توضيحه في هذه السلسلة إن شاء الله

وأهم شيء عليك أن تعرفه هي أن معظم الـ Data Structures تعتمد على الـ LinkedList
لذالك مجهودك في فهم الـ LinkedList سيسهل عليك فهم الـ Stack والـ Queue والـ Tree والـ Graph وغيرها

لذا سنبدأ اليوم بشرح الـ LinkedList وسأحاول أن أبسط الأمور قدر الإمكان

ما هي الـ LinkedList

الـ LinkedList تختلف عن الـ Array في أنها ليست متصلة بشكل متتالي في الذاكرة
بل هي عبارة عن مجموعة من العناصر التي تسمى عُقد Nodes التي تكون متنافرة في الذاكرة
وكل كل Node يحتوي على قيمة وعنوان الـ Node التالية

                                  LinkedList
                        Node 5
                    +------------+
                    | 50 |  NULL | ----> NULL
      Node 1        +------------+
  +------------+        0x114 <-----------------------------------------+
  | 10 | 0x108 | --+                  Node 3                            |
  +------------+   |              +------------+                        |
      0x100        |              | 30 | 0x104 | --+                    |
                   |              +------------+   |                    |
                   |                  0x110        |                    |
                   |       Node 2       ٨          |                    |
                   |   +------------+   |          |       Node 4       |
                   |   | 20 | 0x110 | --+          |   +------------+   |
                   |   +------------+              |   | 40 | 0x114 | --+
                   +-----> 0x108                   |   +------------+
                                                   +-----> 0x104

كما تلاحظ في الرسمة لدينا 5 قيم وهي 10, 20, 30, 40, 50
عندما نريد تخزينها داخل الـ LinkedList فإن كل قيمة تكون في Node خاص بها
وكل Node يحتوي على قيمة وعنوان الـ Node التالية كما تلاحظ

فالـ Node 1 يحتوي على القيمة 10 وعنوان الـ Node 2
والـ Node 2 يحتوي على القيمة 20 وعنوان الـ Node 3
وهكذا حتى نصل إلى الـ Node 5 الذي يحتوي على القيمة 50 وعنوان NULL أي لا يوجد Node بعدها

لاحظ أن كل Node متفرقة عن الأخرى ولا تحتاج إلى تخزينها بشكل متتالي في الذاكرة كما في الـ Array
لكن كل Node تحتوي على عنوان الـ Node التالية لها

وهذا ما يجعل الـ LinkedList يستغل مساحة الذاكرة بشكل أفضل من الـ Array
لأنها يستطيع تخزين العناصر في أي مكان في الذاكرة على عكس الـ Array الذي يحتاج إلى تخزين العناصر بشكل متتالي
فعندما تخزن 100 عنصر في الـ Array فإنه يحتاج إلى البحث عن 100 خانة متتالية فاغرة في الذاكرة لحجزها وتخزين العناصر فيها

وأيضًا من مميزات الـ LinkedList أن إضافة عنصر أو حذف عنصر منه سهل جدًا وسريع جدًا حيث أنه يستطيع إضافة أو حذف أي عنصر في أي مكان فيه في معدل ثابت O(1)

وسنرى هذا في الأمثلة التالية

أيضًا هناك أنواع من الـ LinkedList وهي:

1. Singly LinkedList
2. Doubly LinkedList
3. Circular LinkedList

نحن هنا سنتحدث عن الـ Singly LinkedList وهي الأكثر استخدامًا والأسهل
وقد نتطرق للأنواع الأخرى في مقالات أخرى أو نكتفي بإعطاء تعريف بسيط عنها

كيفية بناء الـ Node

كما لاحظنا فأن الـ LinkedList تتكون من مجموعة من الـ Node
لذا لكي نبني الـ LinkedList نحتاج إلى بناء الـ Node أولًا
ثم نستخدم هذه الـ Node لبناء الـ LinkedList

الـ Node هي في الأساس struct أو object أو حتى كلاس أو أي شيء نستطيع استخدامه مجموعة من البيانات
لأن الـ Node على شيئين أساسيين وهما:

1. القيمة التي نريد تخزينها سواء كانت int أو string أو object أو أي شيء آخر
2. عنوان الـ Node التالية

لذا سنبدأ ببناء الـ Node ثم نبني الـ LinkedList
سنستخدم لغة TypeScript للتوضيح ولكن يمكنك استخدام أي لغة برمجة تفضلها

class Node {
  public value: number;
  public next: Node | null;
}

هنا أنشأنا كلاس Node يحتوي على شيئين وهما value و next
طبعًا value هي القيمة التي نريد تخزينها سواء كانت int أو string أو object أو أي شيء آخر
و next هي عنوان الـ Node التالية وطبعًا يمكن أن تكون null في حالة لم يكن خنا أي Node بعدها

عندما ننشيء الـ Node هكذا

const node_1 = new Node();
node_1.value = 10;
node_1.next = null;

نكون قد أنشأنا Node بقيمة 10 ولا يوجد Node بعدها لذا next يساوي null

في الذكرة يمكنك تخيل الـ Node بشكل مشابه لهذا

      Node 1
  +------------+
  | 10 |  NULL | ----> NULL
  +------------+
      0x100

الآن لنحاول إنشاء Node آخر ونربطه بالـ Node الأول

const node_1 = new Node();
node_1.value = 10;
node_1.next = null;

const node_2 = new Node();
node_2.value = 20;
node_2.next = null;

node_1.next = node_2; // node_2 بالـ node_1 ربط الـ

هنا أنشأنا Node جديدة بقيمة 20 وقمنا بجعل الـ next الخاصة بالـ node_1 تشير إلى الـ node_2 الجديدة

              LinkedList
      Node 1                 Node 2
  +------------+         +------------+
  | 10 | 0x200 | ---+    | 20 |  NULL | ----> NULL
  +------------+    |    +------------+
      0x100         +------> 0x200

وهكذا يمكنك بناء الـ LinkedList بإضافة Node جديدة وربطها بالـ Node السابقة
ويمكننا تسهيل عملية إنشاء الـ Node بإضافة constructor لها

class Node {
  public value: number;
  public next: Node | null;

  constructor(value: number, next: Node | null = null) {
    this.value = value;
    this.next = next;
  }
}

بالتالي يمكننا إنشاء الـ Node بشكل أسهل وربطها مع الأخرى

const node_1 = new Node(10);
const node_2 = new Node(20);

node_1.next = node_2; // node_2 بالـ node_1 ربط الـ

// node_1 -> node_2

ويمكنك طبعًا استخدامات مميزات الكلاس لتبسيط الأمور أكثر

class Node {
  public value: number;
  public next: Node | null;

  constructor(value: number, next: Node | null = null) {
    this.value = value;
    this.next = null;
  }

  public setNext(node: Node | null) {
    this.next = node;
  }
}

هنا أضفنا دالة setNext لتسهيل عملية ربط أي Node بالأخرى
وتصبح مقروءة بشكل أفضل ومفهومة أكثر

const node_1 = new Node(10);
const node_2 = new Node(20);

node_1.setNext(node_2); // node_2 بالـ node_1 ربط الـ

// node_1 -> node_2

هكذا الـ node_1 القديمة أصبحت مربوطة بالـ node_2 الجديدة بغض النظر عن كيف تبدو عملية الربط من الداخل

لاحظ أن الـ constructor يأخذ قيمتين value و next والقيمة الافتراضية للـ next هي null
وهي مفيدة عندما تريد إنشاء Node جديدة وتربطها بالـ Node موجودة مسبقًا بشكل مباشر، عكس ما كنا نفعله سابقًا

const node_3 = new Node(30, node_1); // node_1 بالـ node_3 ربط الـ

// node_3 -> node_1 -> node_2

لاحظ هنا أننا أنشأنها Node جديدة بقيمة 30 وربطناها بالـ Node الأولى node_1 مباشرة أثناء الإنشاء
والترتيب أصبح node_3، node_1، node_2

بالطبع إذا كنت تريد ترتيبهم يمكنك استخدام الدالة setNext

const node_3 = new Node(3);

node_2.setNext(node_3);

// node_1 -> node_2 -> node_3

لاحظ أننا استخدمنا الدالة setNext لربط الـ node_2 بالـ node_3 وبالتالي ترتيبهم أصبح node_1، node_2، node_3
يمكنك أن تحدد طريقة الربط بنفسك

طبعًا في لغة مثل C++ يتم استخدام الـ pointer للتعامل مع الـ Heap مباشرة

class Node {
  public:
    int value;
    Node* next;

    Node(int value, Node* next = NULL) {
        this->value = value;
        this->next = next;
    }

    void setNext(Node* node) {
      this->next = node;
    }
};

كما ترى فالاختلافات تكاد تكون معدومة فقط طريقة الكتابة تختلف بشكل بسيط وطفيف

بناء الـ LinkedList

الآن بعد أن بنينا الـ Node نستطيع بناء الـ LinkedList

لكن علينا أن نفهم مما تتكون الـ LinkedList

الـ LinkedList تتكون من مجموعة من الـ Node
ويوجد متغيرين أساسيين في الـ LinkedList وهما من نوع Node وهما:

• head وهو مجرد Node لكنه دائمًا يشير إلى أول Node في الـ LinkedList
• tail وهو مجرد Node لكنه دائمًا يشير إلى آخر Node في الـ LinkedList

  +------------+         +------------+         +------------+
  | 10 | 0x200 | ---+    | 20 | 0x300 | ---+    | 30 |  NULL | ----> NULL
  +------------+    |    +------------+    |    +------------+
      0x100         +------> 0x200         +------> 0x300
       ٨                                             ٨
       |                                             |
      head                                          tail

كما تلاحظ هنا لدينا LinkedList تتكون من 3 عناصر كل عنصر هو Node
ولاحظ أن لدينا شيء يدعى head وهو يشير إلى الـ Node الأولى في الـ LinkedList
وشيء آخر يدعى tail وهو يشير إلى الـ Node الأخيرة في الـ LinkedList

وهذه الأشياء تسهل علينا العمليات التي نريد القيام بها في الـ LinkedList
مثل إضافة عنصر جديد في بداية الـ LinkedList أو في نهايتها وسنرى هذا

لنبدأ ببناء الـ LinkedList

class LinkedList {
  private head: Node | null;
  private tail: Node | null;
  private length: number;

  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  public isEmpty() {
    return this.length === 0;
  }
}

هنا أنشأنا الـ LinkedList وأضفنا لها متغيرين head و tail وجعلناهما يشيران إلى null
لأنه في البداية لا يوجد أي Node في الـ LinkedList
وبالطبع لدينا متغير length يحتوي على عدد العناصر في الـ LinkedList وفي البداية يكون 0

حاليًا عندما ننشيء Object من الـ LinkedList سيكون فارغًا

const linkedList = new LinkedList();

إضافة Node جديدة في نهاية الـ LinkedList

الآن لنضيف دالة تقوم بإضافة Node جديدة إلى الـ LinkedList من ناحية الـ tail أو نهاية الـ LinkedList لكن كيف نضيف Node جديدة إلى الـ LinkedList ؟

في البداية نحتاج إلى معرفة ما إذا كانت الـ LinkedList فارغة أم لا
إذا كانت فارغة فإن الـ Node الجديدة ستكون هي الـ head والـ tail لأنها الـ Node الوحيد فيها

const node = new Node(value); // جديدة Node إنشاء

// فارغة LinkedList هل الـ
// نعم !
// الجديدة Node يشيران إلى الـ head والـ tail إذًا اجعل الـ
this.head = node;
this.tail = node;

أظن لا يوجد شيء معقد هنا فقط نقوم بإنشاء Node جديدة ثم نجعل الـ head والـ tail يشيران إلى هذه الـ Node

  +------------+
  | 10 |  NULL | ----> NULL
  +------------+
      0x100
       ٨
       |
      head
      tail

وأما إذا كانت الـ LinkedList ليست فارغة أي بها عناصر فإن الـ Node الجديدة سيتم اضافتها من ناحية الـ tail
وسيتم تحديث الـ tail ليشير إلى الـ Node الجديدة

const node = new Node(value); // جديدة Node إنشاء

// فارغة LinkedList هل الـ
// لا !
// tail الحالية التي تشير عليها الـ Node إذا اربط الـ
// next الجديدة عن طريق الـ Node بالـ
this.tail.next = node;
// الجديدة Node تشير إلى الـ tail ثم اجعل الـ
this.tail = node;

قد يكون استيعاب هذا الأمر صعبًا لكن سأحاول اعادة الشرح مع الرسم التوضيحي
أولًا نحن نريد إضافة Node جديدة إلى الـ LinkedList لكن الـ LinkedList ليست فارغة أي نتخيل أن بها عنصرين

  +------------+         +------------+
  | 10 | 0x200 | ---+    | 20 |  NULL | ----> NULL
  +------------+    |    +------------+
      0x100         +------> 0x200
       ٨                      ٨
       |                      |
      head                   tail

الآن نريد إضافة Node جديدة بقيمة 30

أولًا نقوم بإنشاء Node جديدة

const node = new Node(30);

الآن شكل الـ LinkedList سيكون كالتالي

                                                          new Node(30)
  +------------+         +------------+                  +------------+
  | 10 | 0x200 | ---+    | 20 |  NULL | ----> NULL       | 30 |  NULL | ----> NULL
  +------------+    |    +------------+                  +------------+
      0x100         +------> 0x200                           0x300
       ٨                      ٨
       |                      |
      head                   tail

لاحظ أن الـ Node الجديدة في مكان عشوائي في الذاكرة
نحتاج الآن إلى ربط الـ Node الجديدة بالـ Node الأخيرة في الـ LinkedList
والـ Node الأخيرة هي التي تشير إليها الـ tail
لذا نقوم بربطها عن طريق الـ next أو باستخدام الـ الدالة التي أنشأناها سابقًا التي تدعى setNext التي انشأناها في كلاس الـ Node

this.tail.setNext(node); // this.tail.next = node;

الآن سيكون شكل الـ LinkedList كالتالي

                                                 new Node(30)
  +------------+         +------------+         +------------+
  | 10 | 0x200 | ---+    | 20 | 0x300 | ---+    | 30 |  NULL | ----> NULL
  +------------+    |    +------------+    |    +------------+
      0x100         +------> 0x200         +------> 0x300
       ٨                      ٨
       |                      |
      head                   tail

الخطوة الأخيرة هي تحديث الـ tail ليشير إلى الـ Node الجديدة

this.tail = node;

وبهذا نكون قد أضفنا Node جديدة إلى الـ LinkedList بنجاح

                                                 new Node(30)
  +------------+         +------------+         +------------+
  | 10 | 0x200 | ---+    | 20 | 0x300 | ---+    | 30 |  NULL | ----> NULL
  +------------+    |    +------------+    |    +------------+
      0x100         +------> 0x200         +------> 0x300
       ٨                                             ٨
       |                                             |
      head                                          tail

لاحظ أن الـ tail دائمًا سيشير إلى الـ Node الأخيرة في الـ LinkedList
هذا سيسهل علينا إضافة عنصر جديد في نهاية الـ LinkedList بسرعة

الآن بعد أن تعرفنا على كيفية إضافة Node جديدة إلى الـ LinkedList بشكل توضيحي لنبدأ بإنشاء الدالة التي تقوم بإضافة Node جديدة إلى الـ LinkedList بشكل عملي

class LinkedList {
  private head: Node | null;
  private tail: Node | null;
  private length: number;

  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  public isEmpty() {
    return this.length === 0;
  }

  public push(value: number) {
    const node = new Node(value);

    if (this.isEmpty()) {
      this.head = node;
      this.tail = node;
    } else {
      this.tail.setNext(node);
      this.tail = node;
    }

    this.length++;
    return this;
  }
}

لقد أنشأنا دالة push تقوم بإضافة Node جديدة إلى الـ LinkedList
وتطبق ما شرحناه سابقًا وهو إذا كانت الـ LinkedList فارغة فسيتم إضافة الـ Node جديدة
وجعل الـ head والـ tail يشيران إلى هذه الـ Node مباشرةً
وإذا كانت الـ LinkedList بها عناصر فسيتم إضافة الـ Node الجديدة
ثم جعل الـ Node الأخيرة تشير إلى الـ Node الجديدة عن طريق الـ tail
ثم تحديث الـ tail ليشير إلى الـ Node الجديدة

ثم بالطبع تحديث الـ length ونزيد قيمته بـ 1 ثم ستلاحظ أننا نقوم بإرجاع الـ this أي نرجع Object الـ LinkedList نفسه وهذا سيساعدنا في شيء ما سنراه لاحقًا

الآن يمكننا إنشاء Object من الـ LinkedList وإضافة Node جديدة إليها

const linkedList = new LinkedList();

linkedList.push(10);
linkedList.push(20);
linkedList.push(30);

على أي حال تتذكر عندما قلت أننا نرجع this في الدالة push ؟
هذا الأمر يسمح لنا بعمل سلسلة من الدوال مثل هذا

linkedList.push(10).push(20).push(30);

لأنه طالما أن دالة push تقوم بإرجاع this أي Object الـ LinkedList نفسه فإننا نستطيع استدعاء الدوال بشكل متتالي عن طريق الـ Object نفسه الذي يتم إرجاعه وعمل سلسلة من الدوال

وهذا يسمح لنا بتسلسل العمليات بشكل أفضل وأسهل

لاحظ هنا شيء دالة push تقوم بإضافة Node جديدة بشكل فوري وسريع جدًا لأنها فقط تضيف Node جديدة فقط
وهذا يجعلها سريعة جدًا بمعدل ثابت O(1)

تتذكر دالة push الخاصة بالـ Dynamic Array ؟
قلنا أنها سريعة جدًا وتضيف عنصر جديد في نهاية الـ Array بمعدل ثابت O(1)
لكن أحيانا تضطر لإعادة بناء الـ Array بحجم أكبر ونقل العناصر القديمة إلى الـ Array الجديد

لكن الـ LinkedList لا تحتاج إلى هذا فلن تقوم بإعادة بناء الـ LinkedList ونقل العناصر القديمة كما في الـ Dynamic Array بل فورًا تضيف Node دون أن تستهلك شيء يذكر

إضافة Node جديدة من بداية الـ LinkedList

الآن بعد أن تعرفنا على كيفية إضافة Node جديدة في نهاية الـ LinkedList من ناحية الـ tail
لنرى كيف يمكننا إضافة Node جديدة في بداية الـ LinkedList من ناحية الـ head

الأمر يكاد يكون مشابهًا لإضافة Node جديدة في نهاية الـ LinkedList
ويكاد يكون أبسط وأسهل منها

في البداية بالطبع نحتاج إلى معرفة ما إذا كانت الـ LinkedList فارغة أم لا
إذا كانت فارغة فإن الـ Node الجديدة ستكون هي الـ head والـ tail لأنها الـ Node الوحيدة فيها

const node = new Node(value); // جديدة Node إنشاء

// فارغة LinkedList هل الـ
// نعم !
// الجديدة Node يشيران إلى الـ head والـ tail إذًا اجعل الـ
this.head = node;
this.tail = node;

أما إذا كانت الـ LinkedList بها عناصر فإن الـ Node الجديدة نحتاج أولًا إلى ربطها بالـ head الحالية
ثم تحديث الـ head لتشير إلى الـ Node الجديدة

// فارغة LinkedList هل الـ
// لا !

// جديدة Node إذًا ننشيء
// الحالية head ونربطها بالـ
const node = new Node(value, this.head);
// الجديدة Node يشير إلى الـ head ثم اجعل الـ
this.head = node;

وبهذا نكون قد أضفنا Node جديدة في بداية الـ LinkedList بنجاح
بالطبع سأريك كيف يتم إضافة Node جديدة في بداية الـ LinkedList بشكل توضيحي
ثم سنقوم بإنشاء الدالة التي تقوم بإضافة Node جديدة في بداية الـ LinkedList

أولًا نفترض أن الـ LinkedList بها عنصرين

  +------------+         +------------+
  | 10 | 0x200 | ---+    | 20 |  NULL | ----> NULL
  +------------+    |    +------------+
      0x100         +------> 0x200
       ٨                      ٨
       |                      |
      head                   tail

الآن نريد إضافة Node جديدة بقيمة 5 في بداية الـ LinkedList على سبيل المثال

أولًا نقوم بإنشاء Node جديدة
ونجعل الـ next الخاصة بها تشير إلى الـ head الحالية

const node = new Node(5, this.head);

بالطبع تذكر أن الـ constructor للـ Node يأخذ قيمتين value و next
وهنا نحدد الـ next بشكل مباشر لتشير إلى الـ head الحالية لحظة إنشاء الـ Node الجديدة

ولو كنت تريد القيام بها بدون الـ constructor يمكنك القيام بها بشكل منفصل هكذا

const node = new Node(5);
node.next = this.head;

لكن السطر الزائد كنا نختصر داخل الـ constructor الخاص بالـ Node حيث يأخذ الـ next مباشرة ويربط الـ Node الجديدة به

الآن سنقوم بربط الـ Node الجديدة بالـ head الحالية

   new Node(5, this.head)
      +------------+         +------------+         +------------+
      | 5  | 0x100 | ---+    | 10 | 0x200 | ---+    | 30 |  NULL | ----> NULL
      +------------+    |    +------------+    |    +------------+
          0x010         +------> 0x100         +------> 0x200
                                  ٨                      ٨
                                  |                      |
                                head                   tail

الآن سنقوم بتحديث الـ head ليشير إلى الـ Node الجديدة

this.head = node;

وبهذا نكون قد أضفنا Node جديدة في بداية الـ LinkedList بنجاح

   new Node(5, this.head)
      +------------+         +------------+         +------------+
      | 5  | 0x100 | ---+    | 10 | 0x200 | ---+    | 30 |  NULL | ----> NULL
      +------------+    |    +------------+    |    +------------+
          0x010         +------> 0x100         +------> 0x200
           ٨                                             ٨
           |                                             |
          head                                          tail

الآن بعد أن تعرفنا على كيفية إضافة Node جديدة في بداية الـ LinkedList بشكل توضيحي
لنقم بإنشاء الدالة التي تقوم بإضافة Node جديدة في بداية الـ LinkedList

class LinkedList {
  // ...
  public unshift(value: number) {
    let node: Node;

    if (this.isEmpty()) {
      node = new Node(value);
      this.head = node;
      this.tail = node;
    } else {
      node = new Node(value, this.head);
      this.head = node;
    }

    this.length++;
    return this;
  }
}

لقد أنشأنا دالة unshift ومعناها إضافة من الأمام وهي تقوم بإضافة Node جديدة في بداية الـ LinkedList
وكما تلاحظ وهي تقوم بنفس العمليات التي شرحناها سابقًا
إذا كانت الـ LinkedList فارغة فسيتم إنشاء الـ Node الجديدة وجعل الـ head والـ tail يشيران إليها كما كنا نفعل مع دالة push

وإذا كانت الـ LinkedList بها عناصر فإن فننشئ الـ Node الجديدة ونربطها بالـ head بشكل مباشر لحظة إنشاءها عن طريق الـ constructor
ثم نحدث الـ head ليشير إلى الـ Node الجديدة

بالطبع نحدث الـ length ونرجع الـ Object نفسه كما فعلنا مع دالة push

الآن يمكننا إنشاء Object من الـ LinkedList وإضافة Node جديدة في بداية الـ LinkedList

const linkedList = new LinkedList();

linkedList.unshift(5);
// 5
linkedList.unshift(2);
// 2 -> 5
linkedList.unshift(1);
// 1 -> 2 -> 5

وهكذا يمكنك إضافة Node جديدة في بداية الـ LinkedList بسهولة
وبالطبع مثل دالة push يمكنك استدعاء الدوال بشكل متتالي

linkedList.unshift(5).unshift(2).unshift(1);
// 1 -> 2 -> 5

وأيضًا السرعة هنا ثابتة O(1)

إحضار Node من الـ LinkedList عن طريق الـ Index

حسنًا وصلنا إلى أحد عيوب الـ LinkedList وهو أنه لا يمكنك الوصول إلى الـ Node مباشرة عن طريق الـ index
لأنه بكل بساطة لا يوجد index في الـ LinkedList
لأن الأراي أو الـ Dynamic Array كانت تعتمد على أن عناصر الأراي مترتبة بشكل متتالي في الذاكرة وكان يمكنك بسهولة معرفة مكان كل عنصر بالـ index لأنهم مترتبين بشكل متتالي

فالأمر يشبه الرسمة التالية

        +--------+--------+--------+--------+--------+
        |   12   |   16   |   24   |   25   |   28   |
        +--------+--------+--------+--------+--------+
  arr -->  0x100    0x104    0x108    0x10C    0x110
          arr + 0  arr + 1  arr + 2  arr + 3  arr + 4

لاحظ أنه طالمة أن العناصر متتالية ونحن عن طريق معرفة عنوان أول عنصر في الأراي وحجم العنصر نستطيع معرفة عنوان العناصر الأخرى بسهولة

arr[0] = *(arr + 0)
arr[1] = *(arr + 1)
arr[2] = *(arr + 2)
arr[3] = *(arr + 3)
arr[4] = *(arr + 4)
...

ولكن في الـ LinkedList لا يوجد شيء يشبه الـ index لأن العناصر ليست متتالية بشكل متتالي في الذاكرة
بل كل Node يملك عنوانه الخاص ويكون في مكان وعنوان عشوائي في الذاكرة
لذا لا يمكنك الوصول إلى الـ Node مباشرة عن طريق الـ index لأنه لا يوجد نمط أو ترتيب معين للعناصر

لذا للآسف فأحد عيوب الـ LinkedList أن لكي تصل إلى أي Node في الـ LinkedList عليك البدء من الـ head والتقدم خطوة بخطوة حتى تصل إلى الـ Node المطلوب
وهذا يعني أن الوصول إلى الـ Node المطلوب يكون بشكل خطي O(n) وليس ثابت O(1) كما في الـ Dynamic Array

كيف يمكننا الوصول إلى الـ Node المطلوب ؟

كالعادة سنشرح الأمور بشكل توضيحي أولًا ثم نقوم بإنشاء الدالة التي تقوم بإحضار الـ Node المطلوب

فلنفترض أن لدينا LinkedList بها 5 عناصر

  +------------+         +------------+         +------------+         +------------+         +------------+
  | 10 | 0x200 | ---+    | 20 | 0x300 | ---+    | 30 | 0x400 | ---+    | 40 | 0x500 | ---+    | 50 |  NULL | ----> NULL
  +------------+    |    +------------+    |    +------------+    |    +------------+    |    +------------+
      0x100         +------> 0x200         +------> 0x300         +------> 0x400         +------> 0x500
       ٨                                                                                           ٨
       |                                                                                           |
      head                                                                                        tail

الآن نريد الوصول إلى الـ Node الثالثة في الـ LinkedList أي كأنك تقول أريد الـ Node الذي يكون الـ index الخاص بها 2

هنا سنقوم بعمل خطوتين أساسيتين للوصول إلى الـ Node المطلوب

• الخطوة الأولى نبدأ من الـ head
• نستخدم الـ next للتقدم خطوة بخطوة حتى نصل إلى الـ Node المطلوب

الآن نحن نريد البحث أو التحرك داخل الـ LinkedList حتى نصل إلى الـ Node الثالثة
لنفعل هذا علينا البدء من مكان ما وهو غالبًا يكون الـ head
لكن هنا نحن لا نريد تحريك الـ head نحن نريد فقط الوصول إلى الـ Node الثالثة
لذا سنستخدم متغير مؤقت يشير إلى الـ head ونقوم بالتحريك هذا المتغير فقط

ولنسمي هذا المتغير temp وهو يشير إلى الـ head في البداية

  +------------+         +------------+         +------------+         +------------+         +------------+
  | 10 | 0x200 | ---+    | 20 | 0x300 | ---+    | 30 | 0x400 | ---+    | 40 | 0x500 | ---+    | 50 |  NULL | ----> NULL
  +------------+    |    +------------+    |    +------------+    |    +------------+    |    +------------+
      0x100         +------> 0x200         +------> 0x300         +------> 0x400         +------> 0x500
       ٨                                                                                           ٨
       |                                                                                           |
      head                                                                                        tail
      temp

الآن لدينا المتغير temp الذي يشير إلى الـ head
وهدفنا الآن هو الوصول إلى الـ Node الثالثة وهي صاحبة الـ index رقم 2

لنبدأ بالتحرك !

أولًا هل الـ temp يشير إلى الـ Node الثالثة ؟
الإجابة طبعًا لا لأنه يشير إلى الـ Node الأولى حاليًا

لذا تحريك temp إلى الـ Node الثانية
عن طريق الـ next بهذا الشكل

temp = temp.next;

هنا نحن نقول للـ temp أن يشير إلى الـ Node الموجودة في الـ next الخاصة به بالتالي سيتحرك إلى الـ Node التالية

  +------------+         +------------+         +------------+         +------------+         +------------+
  | 10 | 0x200 | ---+    | 20 | 0x300 | ---+    | 30 | 0x400 | ---+    | 40 | 0x500 | ---+    | 50 |  NULL | ----> NULL
  +------------+    |    +------------+    |    +------------+    |    +------------+    |    +------------+
      0x100         +------> 0x200         +------> 0x300         +------> 0x400         +------> 0x500
       ٨                                                                    ٨                      ٨
       |                      |                                                                    |
      head                   temp                                                              tail

لنعيد العملية مرة أخرى
هل الـ temp يشير إلى الـ Node الثالثة ؟
الإجابة طبعًا لا

لذا نقوم بتحريك temp مرة أخرى إلى الـ Node التالية

temp = temp.next;

وهكذا حتى نصل إلى الـ Node الثالثة

  +------------+         +------------+         +------------+         +------------+         +------------+
  | 10 | 0x200 | ---+    | 20 | 0x300 | ---+    | 30 | 0x400 | ---+    | 40 | 0x500 | ---+    | 50 |  NULL | ----> NULL
  +------------+    |    +------------+    |    +------------+    |    +------------+    |    +------------+
      0x100         +------> 0x200         +------> 0x300         +------> 0x400         +------> 0x500
       ٨                                             ٨                                             ٨
       |                                             |                                             |
      head                                          temp                                       tail

الآن هل الـ temp يشير إلى الـ Node الثالثة ؟
الإجابة نعم
الآن temp يشير إلى الـ Node الثالثة

هل عرفت كيف تصل إلى موقع أي Node في الـ LinkedList ؟
الآن لنقم بإنشاء الدالة التي تقوم بإحضار الـ Node المطلوب عن طريق الـ index

class LinkedList {
  // ...
  public get(index: number): Node | null {
    if (index < 0 || index >= this.length) {
      throw new Error('Invalid index');
    }

    let temp = this.head;
    for (let i = 0; i < index; i++) {
      temp = temp.next;
    }

    return temp;
  }
}

لنشرح هذه الدالة:

• أولًا نقوم بالتحقق من الـ index إذا كان أقل من 0 أو أكبر من الـ length فسنقوم برمي Exception
• ثم نقوم بإنشاء متغير مؤقت وهو الـ temp بالطبع يمكنك أن تسميه بأي اسم تريده
• نجعل الـ temp يشير إلى الـ head للبدء من البداية
• ثم نقوم بالتحرك الـ temp بعدد الخطوات التي تساوي الـ index لكي نصل إلى الـ Node المطلوب

الآن يمكنك الوصول إلى أي Node في الـ LinkedList عن طريق الـ index كما في المثال التالي

const linkedList = new LinkedList();
linkedList.push(10).push(20).push(30).push(40).push(50);

console.log(linkedList.get(0).value); // 10
console.log(linkedList.get(2).value); // 30
console.log(linkedList.get(4).value); // 50

كما قلنا فإن الوصول إلى الـ Node المطلوب يكون بشكل خطي O(n) وليس ثابت O(1) كما في الـ Dynamic Array
وهذا للآسف أحد عيوب الـ LinkedList ولكنها تأتي بميزات أخرى كما ذكرنا سابقًا وكما سترى لاحقًا وكيف سيبنى عليها العديد من الهياكل البيانية الأخرى مثل الـ Stack والـ Queue والـ Tree والـ Graph وحتى الـ HashTable

أريدك أن تنظر إلى نفس الدالة لكن بلغة C++

Node* get(int index) {
  if (index < 0 || index >= length) {
    throw "Invalid index";
  }

  Node* temp = head;
  for (int i = 0; i < index; i++) {
    temp = temp->next;
  }

  return temp;
}

هل تلاحظ الفرق بين اللغتين ؟ لا شيء يذكر

إحضار Node من الـ LinkedList عن طريق القيمة

الآن بعد أن تعرفنا على كيفية الوصول إلى الـ Node المطلوب عن طريق الـ index
يمكنك إنشاء دالة مثل الدالة السابقة وتقوم بعمل تعديل بسيط عليها لتقوم بإحضار الـ Node المطلوب عن طريق الـ value بدلاً من الـ index
الأمر لا يحتاج مني لشرحها بشكل توضيحي لأنها تكاد تكون مشابهة للدالة السابقة
بمجرد ما سترى الكود ستفهمها بسهولة

class LinkedList {
  // ...
  public search(value: number): Node | null {
    let temp = this.head;

    for (let i = 0; i < this.length; i++) {
      if (temp.value === value) {
        return temp;
      }
      temp = temp.next;
    }

    return null;
  }
}

لاحظ هنا شيئين وهما أن الـ loop تتحرك من الـ head حتى الـ tail أي من 0 حتى length
وهذا لأننا نقوم بعملية بحث عن قيمة معينة
فنحن الآن نجعل الـ temp يتحرك في كامل الـ LinkedList حتى يصل إلى الـ Node التي تحتوي على القيمة المطلوبة
وإذا وجدنا القيمة المطلوبة نقوم بإرجاع الـ Node الذي تحتوي عليه
وإذا لم نجد القيمة المطلوبة فسنقوم بإرجاع null عند الانتهاء من الـ loop

const linkedList = new LinkedList();
linkedList.push(10).push(20).push(30).push(40).push(50);

if (linkedList.search(25)) {
  console.log('Found');
} else {
  console.log('Not Found');
}

بالتأكيد، سأكمل الشرح والعناوين الناقصة بنفس أسلوب الشرح. دعنا نبدأ من حيث توقفنا.

إزالة Node من الـ LinkedList من البداية

الآن بعد أن تعرفنا على كيفية إضافة Node جديدة في بداية الـ LinkedList
لنفكر في كيفية إزالة Node من بداية الـ LinkedList

الأمر عندما تفكر فيه هو بسيط جدًا
هو أنك لكي تزيل Node من بداية الـ LinkedList عليك فقط تحريك الـ head ليشير إلى الـ Node التالية له
ثم تحذف الـ Node القديمة االتي كان يشير إليها الـ head سابقًا

لنبسط في شكل توضيحي كالعادة

  +------------+         +------------+         +------------+         +------------+
  | 10 | 0x200 | ---+    | 20 | 0x300 | ---+    | 30 | 0x400 | ---+    | 40 | NULL  | ----> NULL
  +------------+    |    +------------+    |    +------------+    |    +------------+
      0x100         +------> 0x200         +------> 0x300         +------> 0x400
       ٨                                                                    ٨
       |                                                                    |
      head                                                                 tail

الآن نريد إزالة الـ Node الأولى من الـ LinkedList
سنقوم بإنشاء متغير مؤقت يشير إلى الـ head

  +------------+         +------------+         +------------+         +------------+
  | 10 | 0x200 | ---+    | 20 | 0x300 | ---+    | 30 | 0x400 | ---+    | 40 | NULL  | ----> NULL
  +------------+    |    +------------+    |    +------------+    |    +------------+
      0x100         +------> 0x200         +------> 0x300         +------> 0x400
       ٨                                                                    ٨
       |                                                                    |
      head                                                                 tail
      temp

ثم نقوم بتحريك الـ head لتشير إلى الـ Node التالية لها

this.head = this.head.next;

  +------------+         +------------+         +------------+         +------------+
  | 10 | 0x200 | ---+    | 20 | 0x300 | ---+    | 30 | 0x400 | ---+    | 40 | NULL  | ----> NULL
  +------------+    |    +------------+    |    +------------+    |    +------------+
      0x100         +------> 0x200         +------> 0x300         +------> 0x400
       ٨                                            ٨                      ٨
       |                      |                                            |
      temp                   head                                         tail

لاحظ أننا بعد ما حركنا الـ head للـ Node التالية لها
أصبح بإمكاننا حذف الـ Node القديمة التي كان يشير إليها الـ head سابقًا دون أي مشاكل

لكن بسبب أننا نستخدم لغة تدعم الـ Garbage Collection فلن نقوم بحذف الـ Node القديمة يدويًا
لأن الـ Garbage Collection ستقوم بحذف الـ Node القديمة تلقائيًا بمجرد أن لا يكون هناك أي شيء يشير إليها
لكن لو كنت تستخدم لغة لا تدعم الـ Garbage Collection مثل C++ فعليك أن تقوم بحذف الـ Node القديمة يدويًا

temp->next = NULL;
delete temp;

كهذا في لغة C++ حذفنا الـ Node القديمة يدويًا

    temp.next = null
    delete temp
  +------------+         +------------+         +------------+         +------------+
  | 10 | Null  |         | 20 | 0x300 | ---+    | 30 | 0x400 | ---+    | 40 | NULL  | ----> NULL
  +------------+         +------------+    |    +------------+    |    +------------+
      0x100                  0x200         +------> 0x300         +------> 0x400
                              ٨                                             ٨
                              |                                             |
                             head                                          tail

الآن بعد أن تعرفنا على كيفية إزالة Node من بداية الـ LinkedList بشكل توضيحي
لنرى كيف يمكننا تنفيذ ذلك في الكود

class LinkedList {
  // ...
  public shift(): number | null {
    if (this.isEmpty()) {
      throw new Error('The LinkedList is empty');
    }

    if (this.length === 1) {
      this.head = null;
      this.tail = null;
    } else {
      let temp = this.head;

      this.head = this.head.next;

      temp.setNext(null);
    }

    this.length--;
    return this;
  }
}

الدالة عندما تحذف من الأمام تسمى shift

هنا لاحظ عدة أمور:

• أولًا نقوم بالتحقق إذا كانت الـ LinkedList فارغة فسنقوم برمي Exception
• وإذا كانت الـ LinkedList بها عنصر واحد فقط فسنقوم بجعل الـ head والـ tail بـ null
• وأما إذا كانت الـ LinkedList بها عناصر أكثر من عنصر واحد فسنقوم بتحريك الـ head لتشير إلى الـ Node التالية لها
• ثم نقوم بانقاص قيمة الـ length بمقدار 1

لاحظ أننا قمنا بعمل متغير temp المؤقت التي تحدثنا عنه لأننا وقمنا فقط بجعل الـ next تشير إلى null وفي لغات أخرى يمكنك أن تحذه يدويًا كما شرحنا سابقًا مع لغة C++ باستخدام delete
لكننا لا نحتاج لفعلها ولا نحتاج لـ temp لأننا نستخدم لغة تدعم الـ Garbage Collection بالفعل لكنني أردت أن أوضح لك الفكرة العامة فقط
لأنك في اللغات التي لا تدعم الـ Garbage Collection يجب عليك حذف الـ Node القديمة يدويًا
لذا ستحتاج إلى إنشاء متغير مؤقت مثل temp لتحريك الـ Node القديمة وحذفها يدويًا

أهم شيء هنا أن يكون عندك علم عندما تستخدم لغة لا تدعم الـ Garbage Collection فستعرف أنك يجب عليك حذف الـ Node القديمة يدويًا

فمثلًا في لغة C++ ستقوم بحذف الـ Node القديمة يدويًا كالتالي

class LinkedList {
  // ...
  LinkedList* shift() {
    if (isEmpty()) {
      throw "The LinkedList is empty";
    }

    if (length == 1) {
      delete head;
      delete tail;
      head = NULL;
      tail = NULL;
    } else {
      Node* temp = head;
      head = head->next;

      temp->next = NULL;
      delete temp;
    }

    length--;
    return this;
  }
};

لاحظ اننا نستخدم delete لحذف الـ Node القديمة يدويًا
ولاحظ أننا أحيانًا نقوم بإنشاء متغير مؤقت لحفظ الـ Node القديمة لكي نقوم بحذفها يدويًا لاحقًا مثل متغير الـ temp

الآن كالعادة يمكنك استخدام هذه الدالة كالتالي:

const linkedList = new LinkedList();
linkedList.push(10).push(20).push(30);
// 10 -> 20 -> 30

linkedList.shift();
// 20 -> 30

linkedList.shift();
// 30

linkedList.shift();
// null

linkedList.shift();
// Exception: The LinkedList is empty

وأيضًا لا يخفى عليك بالطبع أن هذه العملية تتم بسرعة ثابتة O(1) لأننا لا نحتاج إلى المرور على كل العناصر في الـ LinkedList
نحن فقط نحرك الـ head خطوة واحدة للأمام

إزالة Node من الـ LinkedList من النهاية

الآن لنجرب إزالة Node من نهاية الـ LinkedList
هنا ستظهر أحد عيوب الـ Singly LinkedList وهو أنك لا تستطيع أن تحذف Node من نهاية الـ LinkedList بسرعة ثابتة O(1) كما كنا نفعل في الـ Dynamic Array أو في الدالة السابقة الـ shift

بسبب أن كل Node يحتوي على next يشير إلى الـ Node التالية له ولا يستطيع أن يشير إلى الـ Node السابقة له
لذا لا يمكنك أن تحذف Node من نهاية الـ LinkedList بسرعة ثابتة O(1)
هنا نحن نضطر إلى المرور على كل العناصر في الـ LinkedList حتى نصل إلى الـ Node قبل الأخير ثم نقوم بحذف الـ Node الأخير
ولاحظ أنني هنا أقول Singly LinkedList لأنه في الـ Doubly LinkedList يمكنك أن تحذف Node من نهاية الـ LinkedList بسرعة ثابتة O(1)
لأن كل Node في الـ Doubly LinkedList يحتوي على prev يشير إلى الـ Node السابقة له
وبالتالي هذا سيساعدنا كثيرًا في عملية حذف الـ Node من نهاية الـ LinkedList
ولكن هذا ليس موضوعنا الآن، هنا سنشرح حذف الـ Node من نهاية الـ Singly LinkedList

لا داعي للشرح الأمر بشكل توضيحي أريدك أن تأخذ ورقة وقلم وتقوم برسم الـ LinkedList وتحاول إزالة الـ Node الأخيرة منها
وأريدك أن تقوم بهذا قبل أي عملية تريد القيام بها مع أي Data Structure لأن هذا سيساعدك كثيرًا

لنرى الكود بشكل مباشر ونشرحه

class LinkedList {
  // ...
  public pop() {
    if (this.isEmpty()) {
      throw new Error('The LinkedList is empty');
    }

    let temp = this.head;

    while (temp.next !== this.tail) {
      temp = temp.next;
    }

    temp.setNext(null); // temp.next = null
    this.tail = temp;

    this.length--;
    return this;
  }
}

الدالة عندما تحذف من النهاية تسمى pop
على أي حال لنشرح الدالة:

• أولًا نقوم بالتحقق إذا كانت الـ LinkedList فارغة فسنقوم برمي Exception
• ثم نقوم بإنشاء متغير مؤقت يشير إلى الـ head وهذا المتغير سيساعدنا في الوصول إلى الـ Node قبل الأخير
• ثم نقوم بالمرور على الـ LinkedList حتى نصل إلى الـ Node قبل الأخير
  ولاحظ أننا نستخدم while ونكتب شرط temp.next !== this.tail لأننا نريد الوصول إلى الـ Node قبل الأخير
  والـ Node قبل الأخير هو الـ Node الي يكون الـ next الخاص به يشير إلى الـ tail
• بعد ما جعلنا المتغير temp يشير إلى الـ Node
  قبل الأخير نقوم بجعل الـ next الخاص به يشير إلى null
  ثم نقوم بتحديث الـ tail ليشير إلى الـ temp
• ثم نقوم بانقاص قيمة الـ length بمقدار 1

لاحظ أننا نستخدم loop للمرور على كل العناصر في الـ LinkedList حتى نصل إلى الـ Node قبل الأخير
وهذه عملية مكلفة بالطبع لأنها تتم بسرعة خطية O(n)

وبالطبع لا أريد أن اعيد عليك فكرة الـ Garbage Collection وكيف أننا لا نقوم بحذف الـ Node القديمة يدويًا
لكنني أريد أن أريك نفس الكود في لغة C++ وكيف يتم حذف الـ Node يدويًا

LinkedList* pop() {
  if (isEmpty()) {
    throw "The LinkedList is empty";
  }

  Node* temp = head;

  while (temp->next != tail) {
    temp = temp->next;
  }

  delete tail;
  temp->next = NULL;
  tail = temp;

  length--;
  return this;
}

لاحظ أن الفرق الوحيد هو delete tail حيث نقوم بحذف الـ Node القديمة يدويًا
الباقي كما هو نحدث الـ next الخاصة بالـ temp لتشير إلى NULL
ثم نقوم بتحديث الـ tail ليشير إلى الـ temp

الآن يمكنك استخدام هذه الدالة كالتالي:

const linkedList = new LinkedList();
linkedList.push(10).push(20).push(30);
// 10 -> 20 -> 30

linkedList.pop();
// 10 -> 20

linkedList.pop();
// 10

linkedList.pop();
// null

linkedList.pop();
// Exception: The LinkedList is empty

فكرة الـ Doubly LinkedList

لنأخذ خطوة إضافية في الـ LinkedList ونتعرف على الـ Doubly LinkedList
في الحقيقة كنت أريد أن أنهي المقالة هنا وأدعك تستكشف الـ Doubly LinkedList بنفسك
لأننا مع شرحي السابق للـ Singly LinkedList وكيفية إضافة وحذف الـ Node من البداية والنهاية أعطيتك فكرة عامة عن كيفية عمل الـ LinkedList
بالتالي أفترض أنك الآن تستطيع تخيل الـ LinkedList وتنفذ العديد من العمليات عليها

لكن قلت لا ضرر في الحديث عن الـ Doubly LinkedList وأن أعطيك فكرة عامة عنها
الـ Doubly LinkedList هي نوع آخر من الـ LinkedList ويمكنك تخيلها على أنها توسعة للـ Singly LinkedList

وأهم مميزاتها هي أن كل Node يحتوي على مؤشرين next و prev
حيث أن الـ next يشير إلى الـ Node التالية له
والـ prev يشير إلى الـ Node السابقة له

وهذا يساعدك كثيرة على التنقل في الـ LinkedList بشكل سلس
ويساعدك عن القيام بعمليات معينة بشكل أسرع وأسهل كما في حالة حذف الـ Node من نهاية الـ LinkedList
حيث أن الـ Doubly LinkedList يمكنها القيام بذلك بسرعة ثابتة O(1) بينما الـ Singly LinkedList تحتاج إلى سرعة خطية O(n)

لكن بالطبع من العيوب هو أن كل Node يحتوي على مؤشرين بدلاً من مؤشر واحد فقط
بالتالي ستحتاج إلى مساحة أكبر في الذاكرة لتخزين الـ Doubly LinkedList
وأيضًا عليك التركيز أكثر عند إضافة وحذف الـ Node لأنك ستحتاج إلى تحديث next و prev في كل عملية وتتأكد أن كل شيء تم ربطه بشكل صحيح مع بعضه البعض

لنرى شكل الـ Node في الـ Doubly LinkedList

class Node {
  public value: number;
  public next: Node | null;
  public prev: Node | null;

  constructor(
    value: number,
    next: Node | null = null,
    prev: Node | null = null
  ) {
    this.value = value;
    this.next = next;
    this.prev = prev;
  }

  public setNext(next: Node | null) {
    this.next = next;
  }

  public setPrev(prev: Node | null) {
    this.prev = prev;
  }
}

لاحظ فقط أننا أضفنا متغير جديد يسمى prev وهو يشير إلى الـ Node السابقة له
وأيضًا أضفنا دالة جديدة تسمى setPrev تقوم بتحديث الـ prev الخاص بالـ Node، مجرد تفاصيل صغيرة قد لا تحتاج إليها

الآن لنقم بإنشاء كلاس الـ Doubly LinkedList ونرى كيف يمكننا إضافة وحذف الـ Node منها

class DoublyLinkedList {
  private head: Node | null;
  private tail: Node | null;
  private length: number;

  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  public isEmpty(): boolean {
    return this.length === 0;
  }
}

كلاس بسيط يحتوي على الـ head والـ tail والـ length ودالة بسيطة تقوم بالتحقق إذا كانت الـ LinkedList فارغة أم لا
والآن لنقم بإضافة الدالة التي تقوم بإضافة Node جديدة في نهاية الـ Doubly LinkedList

class DoublyLinkedList {
  // ...
  public push(value: number) {
    const node = new Node(value);

    if (this.isEmpty()) {
      this.head = node;
      this.tail = node;
    } else {
      this.tail.setNext(node);
      node.setPrev(this.tail);
      this.tail = node;
    }

    this.length++;
    return this;
  }
}

لاحظ أن دالة push مشابهة لدالة push في الـ Singly LinkedList ولكن هنا نقوم بتحديث الـ prev أيضًا
لاحظ أنه في حالة كانت الـ LinkedList فارغة فسنقوم بجعل الـ head والـ tail يشيران إلى الـ Node الجديدة

أما إذا كانت الـ LinkedList بها عناصر فلاحظ الآتي:

• نقوم بجعل الـ next الخاص بالـ tail يشير إلى الـ Node الجديدة، مثل ما فعلنا في الـ Singly LinkedList
• ثم نقوم بجعل الـ prev الخاص بالـ Node الجديدة يشير إلى الـ tail القديمة لأن الـ Node ستكون الـ tail الجديدة
  فمنطقي أن الـ prev الخاص بها سيشير إلى الـ tail القديمة
• ثم نقوم بتحديث الـ tail ليشير إلى الـ Node الجديدة

يمكننا كتابة الدالة بشكل أبسط بسبب الـ constructor الذي أضفناه في الـ Node والذي يقوم بتحديد الـ next والـ prev بشكل تلقائي

class DoublyLinkedList {
  // ...
  public push(value: number) {
    const node = new Node(value, null, this.tail); // this.tail is the prev

    if (this.isEmpty()) {
      this.head = node;
      this.tail = node;
    } else {
      this.tail.setNext(node);
      this.tail = node;
    }

    this.length++;
    return this;
  }
}

هنا لاحظ أننا عندما أنشأنا الـ Node الجديدة قمنا بتحديد الـ next بـ null
ثم قمنا بتحديد الـ prev بالـ tail القديمة
فعلنا هذا في سطر واحد فقط بفضل الـ constructor الذي أضفناه في الـ Node

الآن لنقم بإنشاء الدالة التي تقوم بحذف Node من نهاية الـ Doubly LinkedList

class DoublyLinkedList {
  // ...
  public pop() {
    if (this.isEmpty()) {
      throw new Error('The LinkedList is empty');
    }

    if (this.length === 1) {
      this.head = null;
      this.tail = null;
    } else {
      let temp = this.tail;

      this.tail = this.tail.prev;
      this.tail.setNext(null);

      temp.setPrev(null);
    }

    this.length--;
    return this;
  }
}

أنظر إلى جمال الـ Doubly LinkedList وكيف أننا نستطيع حذف الـ Node من نهاية الـ LinkedList بسرعة ثابتة O(1)
تذكر أننا في الـ Singly LinkedList كنا نقوم بعمل loop حتى نصل إلى الـ Node قبل الأخير ثم نقوم بحذف الـ Node الأخير وإلخ...
وكنا نحتاج إلى سرعة خطية O(n) حتى نصل إلى الـ Node قبل الأخير

أما هنا نحن نستطيع الوصول إلى الـ Node قبل الأخير في خطوة واحدة فقط this.tail.prev
بالتالي نستطيع جعل الـ tail يشير إلى الـ Node قبل الأخيرة في خطوة واحدة فقط this.tail = this.tail.prev

ثم نقوم بجعل الـ next الخاص بالـ tail الجديدة يشير إلى null لأنها ستكون الـ tail الجديدة
بالطبع قمنا بعمل متغير مؤقت يشير إلى الـ tail القديمة لأننا كنا نحتاج إلى تحديث الـ prev لتشير إلى null
لكن هذا ليس بالمشكلة لأننا نستخدم لغة تدعم الـ Garbage Collection ولن نقوم بحذف الـ Node القديمة يدويًا
لذا خطوة الـ temp قد لا تكون ضرورية لكنني أحببت القيام بها للتعميم وبالطبع هنا خطوة اضافية اننا نحذف الـ temp يدويًا

أريد أن أعرض على كلا الدالتين الخاصين بالـ Singly LinkedList والـ Doubly LinkedList لكي ترى الفرق بينهما

// Singly LinkedList
public pop() {
  if (this.isEmpty()) {
    throw new Error('The LinkedList is empty');
  }

  while (temp.next !== this.tail) {
    temp = temp.next;
  }

  temp.setNext(null);
  this.tail = temp;

  this.length--;
  return this;
}

// Doubly LinkedList
public pop() {
  if (this.isEmpty()) {
    throw new Error('The LinkedList is empty');
  }

  if (this.length === 1) {
    this.head = null;
    this.tail = null;
  } else {
    this.tail = this.tail.prev;
    this.tail.setNext(null);
  }

  this.length--;
  return this;
}

فقط تأمل !

الختام

أعتقد أنني قد قدمت لك فكرة عامة عن الـ LinkedList وكيفية عمل معظم العمليات عليها
بالطبع أي شيء ناقص يمكنك مع القيل من التفكي ر والرسم على ورقة وقلم أن تكتشفه بنفسك كيف يمكنك تنفيذه

مهمتي هنا تكمن في فتح باب لديك إلى عالم الـ LinkedList وكيفية عملها
وبالطبع يمكنك أن تفكر في عمل دوال أخرى مثل insert أو delete من وسط الـ LinkedList أو reverse الـ LinkedList وإلخ...
ونفس الأمر ينطبق على الـ Doubly LinkedList يمكنك أن تفكر في العديد من الدوال التي تريد تنفيذها عليها
وبالطبع يمكنك أن تنظر إلى الـ Circular LinkedList وتفكر في كيفية تنفيذها وكيف تعمل

الطريق ما زال طويلًا وهناك العديد من الأشياء التي يمكنك تعلمها وتكتشفها
والتي سأتطرق لها في المقالات القادمة إن شاء الله