Node and Linked List Structure
Linked lists are fundamental linear data structures that consist of nodes connected by pointers. Unlike arrays, linked lists do not store elements contiguously in memory; each element (node) contains a value and a reference (pointer) to the next node. This makes certain operations—like inserting or removing at the ends—very efficient, while others—like random access—inefficient. In the following lessons, we’ll use N to denote the number of nodes in the list when discussing time complexity.
Node Definition: class Node
Each element of a linked list is represented by a node.
-
Syntax (JavaScript):
class Node { constructor(value) { this.value = value; // The data payload this.next = null; // Pointer to the next node } } -
Time Complexity:
O(1)– Creating a single node is a constant-time operation. -
Space Complexity:
O(1)– One node instance holds exactly two properties.
let node = new Node(42);
console.log(node.value); // 42
console.log(node.next); // null
Singly Linked List Class
A singly linked list maintains a reference to its head (first node), and optionally its tail (last node) and a length counter.
-
Syntax (JavaScript):
class LinkedList { constructor() { this.head = null; // First node this.tail = null; // Last node (for O(1) tail operations) this.length = 0; // Number of nodes } } -
Initialization:
- Time Complexity:
O(1) - Space Complexity:
O(1)
- Time Complexity:
let list = new LinkedList();
console.log(list.head, list.tail, list.length); // null, null, 0
Insertion Operations
1. Add at Head: .prepend(value)
Inserts a new node at the beginning of the list.
-
Syntax:
prepend(value) { const newNode = new Node(value); newNode.next = this.head; this.head = newNode; if (!this.tail) this.tail = newNode; this.length++; } -
Time Complexity:
O(1)– Only pointer reassignments. -
Space Complexity:
O(1)– One new node.
list.prepend(10); // [10]
list.prepend(20); // [20 → 10]
2. Add at Tail: .append(value)
Inserts a new node at the end of the list.
-
Syntax:
append(value) { const newNode = new Node(value); if (!this.head) { this.head = newNode; this.tail = newNode; } else { this.tail.next = newNode; this.tail = newNode; } this.length++; } -
Time Complexity:
O(1)– Direct access via storedtail. -
Space Complexity:
O(1)– One new node.
list.append(30); // [20 → 10 → 30]
3. Insert at Index: .insertAt(index, value)
Inserts at a specified position (0-based).
-
Syntax:
insertAt(index, value) { if (index < 0 || index > this.length) return false; if (index === 0) return this.prepend(value); if (index === this.length) return this.append(value); const newNode = new Node(value); let prev = this.head; for (let i = 1; i < index; i++) { prev = prev.next; } newNode.next = prev.next; prev.next = newNode; this.length++; return true; } -
Time Complexity:
O(N)– Need to traverse up toindex. -
Space Complexity:
O(1)– One new node.
list.insertAt(1, 15); // [20 → 15 → 10 → 30]
Deletion Operations
1. Remove Head: .removeHead()
Removes the first node.
-
Syntax:
removeHead() { if (!this.head) return null; const removed = this.head; this.head = this.head.next; if (!this.head) this.tail = null; this.length--; return removed.value; } -
Time Complexity:
O(1)– Direct pointer update. -
Space Complexity:
O(1).
list.removeHead(); // returns 20, list is now [15 → 10 → 30]
2. Remove Tail: .removeTail()
Removes the last node.
-
Syntax:
removeTail() { if (!this.head) return null; if (this.head === this.tail) { const value = this.head.value; this.head = null; this.tail = null; this.length--; return value; } let current = this.head; while (current.next !== this.tail) { current = current.next; } const value = this.tail.value; current.next = null; this.tail = current; this.length--; return value; } -
Time Complexity:
O(N)– Must traverse to the node before the tail. -
Space Complexity:
O(1).
list.removeTail(); // returns 30, list is now [15 → 10]
3. Remove at Index: .removeAt(index)
Removes a node at a specific position.
-
Syntax:
removeAt(index) { if (index < 0 || index >= this.length) return null; if (index === 0) return this.removeHead(); if (index === this.length - 1) return this.removeTail(); let prev = this.head; for (let i = 1; i < index; i++) { prev = prev.next; } const removed = prev.next; prev.next = removed.next; this.length--; return removed.value; } -
Time Complexity:
O(N)– Traverse toindex - 1. -
Space Complexity:
O(1).
list.removeAt(1); // returns 10, list is now [15]
Traversal & Search
Traversal
Visiting each node, e.g., to print values.
-
Syntax:
traverse() { let current = this.head; while (current) { console.log(current.value); current = current.next; } } -
Time Complexity:
O(N)– Visits every node once. -
Space Complexity:
O(1).
Search: .find(value)
Locate the first node containing the given value.
-
Syntax:
find(value) { let current = this.head; while (current) { if (current.value === value) return current; current = current.next; } return null; } -
Time Complexity:
O(N)– May check every node. -
Space Complexity:
O(1).
console.log(list.find(15)); // Node { value: 15, next: null }
Practical Application: Reversing a Singly Linked List
Reversing a list in-place is a classic exercise.
Method 1: Iterative
- Concept: Walk through the list and reverse pointers one by one.
- Time Complexity:
O(N)– Single pass. - Space Complexity:
O(1)– Three pointers only.
reverse() {
let prev = null;
let curr = this.head;
this.tail = curr;
while (curr) {
let nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
this.head = prev;
}
Method 2: Recursive
- Concept: Recursively reverse the rest of the list, then fix the current node’s pointer.
- Time Complexity:
O(N)– Each node processed once. - Space Complexity:
O(N)– Call stack frames.
reverseRecursive(node = this.head) {
if (!node || !node.next) {
this.head = node;
return node;
}
const newHead = this.reverseRecursive(node.next);
node.next.next = node;
node.next = null;
return newHead;
}
Note: Iterative reversal is generally preferred in production due to its constant space usage and no risk of call-stack overflow.
التالي · الدرس 22 من 92
Types of Linked Lists (Singly, Doubly, Circular)
قراءة 4 دقيقة
أنهيت 21 من 92 درسًا

اسأل Byte عن هذا الدرس
محادثة خاصة حول هذا الدرس. قرأ Byte الدرس كاملًا، ويجيب خلال ثوانٍ، ويُظهر القسم الذي تأتي منه كل إجابة. يمكنك السؤال بأي لغة.
الأسئلة والأجوبة
أسئلة عامة حول هذا الدرس. يجيب AI Tutor فورًا بلغتك، ويراجع فريق FreeAcademy الإجابات، ويمكن لكل المتعلمين قراءتها.

