الـ LinkedList بديل الـ Array ؟
السلام عليكم ورحمة الله وبركاته
الفهرس
- المقدمة
- ما هي الـ LinkedList
- كيفية بناء الـ Node
- بناء الـ LinkedList
- إضافة Node جديدة في نهاية الـ LinkedList
- إضافة Node جديدة من بداية الـ LinkedList
- إحضار Node من الـ LinkedList عن طريق الـ Index
- إحضار Node من الـ LinkedList عن طريق القيمة
- إزالة Node من الـ LinkedList من البداية
- إزالة Node من الـ LinkedList من النهاية
- فكرة الـ Doubly LinkedList
- الختام
المقدمة
حسنًا وصلنا لثاني مقالة من سلسلة هياكل البيانات 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
وهي:
Singly LinkedList
Doubly LinkedList
Circular LinkedList
نحن هنا سنتحدث عن الـ Singly LinkedList
وهي الأكثر استخدامًا والأسهل
وقد نتطرق للأنواع الأخرى في مقالات أخرى أو نكتفي بإعطاء تعريف بسيط عنها
كيفية بناء الـ Node
كما لاحظنا فأن الـ LinkedList
تتكون من مجموعة من الـ Node
لذا لكي نبني الـ LinkedList
نحتاج إلى بناء الـ Node
أولًا
ثم نستخدم هذه الـ Node
لبناء الـ LinkedList
الـ Node
هي في الأساس struct
أو object
أو حتى كلاس أو أي شيء نستطيع استخدامه مجموعة من البيانات
لأن الـ Node
على شيئين أساسيين وهما:
- القيمة التي نريد تخزينها سواء كانت
int
أوstring
أوobject
أو أي شيء آخر - عنوان الـ
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
وتفكر في كيفية تنفيذها وكيف تعمل
الطريق ما زال طويلًا وهناك العديد من الأشياء التي يمكنك تعلمها وتكتشفها
والتي سأتطرق لها في المقالات القادمة إن شاء الله