تخيل قطار - كل عربية فيها:
آخر عربية (last node) بتشاور على null - مفيش حاجة بعدها!
في الـ Array، العناصر ورا بعض في الذاكرة (contiguous).
في الـ Linked List، العناصر متفرقة في
الذاكرة!
بس كل واحد عارف مكان اللي بعده.
Data: القيمة المخزنة
Next: مؤشر (pointer) للـ node التالي
كل node بتشاور على اللي بعدها، وآخر واحدة بتشاور على null
| المقارنة | Array | Linked List |
|---|---|---|
| الذاكرة | متتالية (Contiguous) | متفرقة (Scattered) |
| Access بالـ Index | O(1) ✓ | O(n) ✗ |
| Insert في الأول | O(n) | O(1) ✓ |
| Delete من الأول | O(n) | O(1) ✓ |
| استهلاك الذاكرة | أقل | أكتر (pointer لكل node) |
| الحجم | ثابت (في بعض اللغات) | متغير (Dynamic) |
💡 ليه O(1)؟
مش محتاجين نعدي على أي node تانية - بنتعامل مع الـ head مباشرة!
مثال: إضافة 5 في الأول
Before:
After:
مثال: حذف أول عنصر
Before:
After:
عشان توصل لعنصر معين، لازم تبدأ من الـ head وتمشي node بـ node لحد ما توصل!
⚠️ مفيش random access زي الـ Array - ده العيب الكبير!
Enter a value and click an operation.
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
}
// O(1) - Add to head
prepend(value) {
const node = new Node(value);
node.next = this.head;
this.head = node;
}
// O(n) - Add to tail
append(value) {
const node = new Node(value);
if (!this.head) {
this.head = node;
return;
}
let curr = this.head;
while (curr.next) curr = curr.next;
curr.next = node;
}
// O(1) - Remove from head
removeHead() {
if (this.head) this.head = this.head.next;
}
}