Creating a Singly Linked List from Scratch in DSA Javascript - Algorithm Mechanics

Overview - Creating a Singly Linked List from Scratch

What is it?

A singly linked list is a simple chain of connected items called nodes. Each node holds some data and a link to the next node in the chain. This structure allows easy insertion and removal of items without shifting others. It is a basic way to organize data in a sequence.

Why it matters

Without linked lists, managing sequences of data would be harder and slower, especially when adding or removing items in the middle. Arrays need shifting elements, which wastes time. Linked lists solve this by linking nodes directly, making changes quick and efficient. This helps programs run faster and use memory better.

Where it fits

Before learning linked lists, you should understand basic programming concepts like variables and objects. After mastering linked lists, you can learn more complex structures like doubly linked lists, stacks, queues, and trees, which build on these ideas.

Mental Model

Core Idea

A singly linked list is a chain of nodes where each node points to the next, allowing flexible and efficient data organization.

Think of it like...

Imagine a treasure hunt where each clue leads you to the next one. Each clue is like a node holding information and a pointer to the next clue, forming a chain you follow step-by-step.

Head -> [Data | Next] -> [Data | Next] -> [Data | null]

Each box is a node with two parts: data and a pointer to the next node. The last node points to null, meaning the end of the list.

Build-Up - 7 Steps

1

Foundation

Understanding Node Structure Basics

Concept: Learn what a node is and how it stores data and a link to the next node.

In JavaScript, a node can be an object with two properties: 'data' to hold the value, and 'next' to hold the reference to the next node. For example: const node = { data: 5, next: null }; Here, 'data' is 5, and 'next' is null because it points to nothing yet.

Result

A single node object with data and a next pointer set to null.

Understanding the node structure is key because the entire linked list is built by connecting these nodes through their 'next' pointers.

2

Foundation

Creating the List Head and Adding Nodes

Concept: Learn how to start a linked list by creating the head node and adding more nodes by linking them.

The head is the first node in the list. To add nodes, create new node objects and set the 'next' of the last node to point to the new node. Example: let head = { data: 1, next: null }; let second = { data: 2, next: null }; head.next = second; Now, head points to second, forming a chain.

Result

A linked list with two nodes connected: 1 -> 2 -> null

Knowing how to link nodes by updating the 'next' pointer lets you build the list step-by-step.

3

Intermediate

Building a Linked List Class

🤔Before reading on: Do you think a linked list needs to track only the head, or both head and tail? Commit to your answer.

Concept: Introduce a class to manage the linked list, keeping track of the head and optionally the tail for easier additions.

A LinkedList class holds the head node and methods to add nodes. For example: class LinkedList { constructor() { this.head = null; this.tail = null; } append(data) { const newNode = { data, next: null }; if (!this.head) { this.head = newNode; this.tail = newNode; } else { this.tail.next = newNode; this.tail = newNode; } } } This class allows adding nodes easily at the end.

Result

A LinkedList instance where nodes can be appended efficiently, maintaining head and tail.

Tracking both head and tail avoids walking the whole list to add nodes, making appending fast.

4

Intermediate

Traversing and Printing the List

🤔Before reading on: Do you think you can print all nodes by following 'next' from head until null? Commit to your answer.

Concept: Learn how to visit each node in order by following the 'next' pointers, to read or print data.

To traverse, start at head and move to next nodes until you reach null: printList() { let current = this.head; while (current) { console.log(current.data); current = current.next; } } This prints all node data in order.

Result

Console output of all node data in sequence, e.g., 1 2 3

Traversal is fundamental to access or modify list data; it shows how the chain structure works in practice.

5

Intermediate

Inserting Nodes at the Beginning

🤔Before reading on: Do you think inserting at the start requires changing the head pointer? Commit to your answer.

Concept: Learn how to add a new node at the start by updating the head to point to the new node.

To insert at the beginning: insertAtStart(data) { const newNode = { data, next: this.head }; this.head = newNode; if (!this.tail) { this.tail = newNode; } } This makes the new node the head, linking it to the old head.

Result

The list starts with the new node, followed by the previous nodes.

Changing the head pointer is the key to inserting at the start without walking the list.

6

Advanced

Removing Nodes by Value

🤔Before reading on: Do you think removing a node requires updating the previous node's 'next' pointer? Commit to your answer.

Concept: Learn how to find and remove a node by changing the 'next' pointer of the node before it.

To remove a node with a specific value: remove(data) { if (!this.head) return; if (this.head.data === data) { this.head = this.head.next; if (!this.head) this.tail = null; return; } let current = this.head; while (current.next && current.next.data !== data) { current = current.next; } if (current.next) { current.next = current.next.next; if (!current.next) this.tail = current; } } This skips over the node to remove it.

Result

The node with the given data is removed; list links adjust accordingly.

Updating the previous node's 'next' pointer is essential to remove nodes without breaking the chain.

7

Expert

Handling Edge Cases and Memory

🤔Before reading on: Do you think forgetting to update tail after removals can cause bugs? Commit to your answer.

Concept: Understand the importance of updating head and tail pointers correctly and how JavaScript's garbage collection frees removed nodes.

When removing nodes, if the removed node is head or tail, update those pointers to avoid broken lists. For example, if the last node is removed, tail must point to the new last node or null. JavaScript automatically frees memory of nodes no longer referenced, so no manual cleanup is needed. Example: if (!this.head) this.tail = null; // after removing last node This keeps the list consistent and prevents errors.

Result

A robust linked list that handles empty states and avoids dangling pointers.

Proper pointer updates prevent subtle bugs and ensure the list stays valid; understanding memory helps trust automatic cleanup.

Under the Hood

Each node is a small object stored in memory with two parts: data and a pointer to the next node's memory address. The list itself holds a reference to the first node (head). Traversing means following these pointers from one node to the next until reaching null, which marks the end. JavaScript's memory manager tracks these objects and frees nodes no longer referenced, preventing memory leaks.

Why designed this way?

Linked lists were designed to allow efficient insertion and deletion without shifting elements, unlike arrays. The singly linked design is simple and uses minimal memory per node. Alternatives like doubly linked lists add backward links but use more memory. This design balances simplicity, speed, and memory use.

LinkedList
┌─────────┐
│  head   │
└───┬─────┘
    │
    ▼
┌───────────────┐     ┌───────────────┐     ┌───────────────┐
│ data | next ├───▶ │ data | next ├───▶ │ data | next │ null
└───────────────┘     └───────────────┘     └───────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Does a singly linked list allow you to go backwards easily? Commit to yes or no.

Common Belief: You can easily move backward in a singly linked list by following pointers.

Reality: Singly linked lists only have pointers forward; going backward requires starting from the head and moving forward until the desired node.

Why it matters: Assuming backward traversal is easy can lead to inefficient code that tries to move backward without rebuilding the list or using a different structure.

Quick: Is it safe to assume the tail pointer always exists in a singly linked list? Commit to yes or no.

Common Belief: Every singly linked list must have a tail pointer to work properly.

Reality: Tail pointers are optional; some implementations only track the head, but this makes adding nodes at the end slower because you must traverse the whole list.

Why it matters: Not knowing this can cause performance issues when appending nodes, as the list must be walked each time.

Quick: Does removing a node automatically free its memory immediately? Commit to yes or no.

Common Belief: Removing a node manually frees its memory instantly.

Reality: In JavaScript, memory is freed automatically by garbage collection when no references remain; you don't manually free memory.

Why it matters: Expecting manual memory management can cause confusion and errors in languages with automatic garbage collection.

Quick: Can you insert a node in the middle without changing any pointers? Commit to yes or no.

Common Belief: You can insert a node anywhere without updating pointers.

Reality: Inserting requires changing the 'next' pointer of the previous node to point to the new node, and the new node's 'next' to point to the next node.

Why it matters: Ignoring pointer updates breaks the chain, causing lost nodes and corrupted lists.

Expert Zone

1

Maintaining both head and tail pointers is a subtle optimization that drastically improves append operations from O(n) to O(1).

2

Edge cases like empty lists, single-node lists, and removing the last node require careful pointer updates to avoid bugs.

3

JavaScript's automatic garbage collection means you don't manually free nodes, but lingering references can cause memory leaks if not cleared.

When NOT to use

Singly linked lists are not ideal when frequent backward traversal or random access is needed; arrays or doubly linked lists are better. For very large data, balanced trees or hash tables may be more efficient.

Production Patterns

In real systems, singly linked lists are used for simple queues, stacks, or adjacency lists in graphs. They often appear in low-level memory management, event handling, or as building blocks for more complex structures.

Connections

Arrays

Alternative data structure for sequences

Understanding arrays helps appreciate linked lists' advantage in insertion and deletion without shifting elements.

Garbage Collection

Memory management mechanism

Knowing how JavaScript frees unused nodes clarifies why manual memory freeing is unnecessary in linked lists.

Supply Chain Logistics

Sequential process flow

Like a linked list, supply chains move goods step-by-step through connected stages, showing how sequential links organize flow efficiently.

Common Pitfalls

#1 Forgetting to update the tail pointer when adding a new node at the end.

Wrong approach:

append(data) {
const newNode = { data, next: null };
if (!this.head) {
this.head = newNode;
} else {
this.tail.next = newNode;
}
// Missing this.tail = newNode;
}

Correct approach:

append(data) {
const newNode = { data, next: null };
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
}

Root cause:

Not realizing the tail pointer must move to the new last node to keep the list consistent.

#2 Removing a node without updating the previous node's 'next' pointer.

Wrong approach:

remove(data) {
let current = this.head;
while (current) {
if (current.data === data) {
current = current.next; // This only moves current, does not remove node
return;
}
current = current.next;
}
}

Correct approach:

remove(data) {
if (!this.head) return;
if (this.head.data === data) {
this.head = this.head.next;
return;
}
let current = this.head;
while (current.next && current.next.data !== data) {
current = current.next;
}
if (current.next) {
current.next = current.next.next;
}
}

Root cause:

Misunderstanding that removing requires changing the link from the previous node, not just skipping the current pointer.

#3 Trying to traverse the list backward using 'next' pointers.

Wrong approach:

let current = tail;
while (current) {
console.log(current.data);
current = current.next; // This will not work backward
}

Correct approach:

let current = head;
while (current) {
console.log(current.data);
current = current.next;
}

Root cause:

Assuming 'next' pointers work both ways, ignoring that singly linked lists only point forward.

Key Takeaways

A singly linked list is a chain of nodes where each node points only to the next, enabling flexible data organization.

Building a linked list requires managing node connections carefully, especially updating head and tail pointers.

Traversing the list means following 'next' pointers from head until null, allowing access to all nodes in order.

Properly updating pointers when inserting or removing nodes is crucial to keep the list intact and avoid bugs.

Understanding linked lists lays the foundation for more complex data structures and efficient memory use in programming.

Practice

1. What is the main purpose of a Singly Linked List in data structures?

easy

A. To store elements with random access by index

B. To store elements in a tree-like hierarchy

C. To store elements in a linear order where each element points to the next one

D. To store elements in a fixed-size array

Solution

1. Step 1: Understand the structure of a singly linked list

   A singly linked list stores elements in nodes where each node points to the next node, forming a chain.

2. Step 2: Compare with other data structures

   Unlike arrays or trees, singly linked lists do not support random access or hierarchical storage.

3. Final Answer:

   To store elements in a linear order where each element points to the next one -> Option C

4. Quick Check:

   Singly linked list = linear chain of nodes [OK]

Hint: Remember: singly linked list is a chain of nodes [OK]

Common Mistakes:

• Confusing linked list with arrays
• Thinking linked list supports random access
• Mixing linked list with tree structures

2. Which of the following is the correct way to define a Node class for a singly linked list in JavaScript?

easy

A. class Node { constructor(value) { this.next = value; this.value = null; } }

B. class Node { constructor(value) { this.value = value; this.next = null; } }

C. class Node { constructor() { this.value = null; this.next = null; } }

D. class Node { constructor(value) { this.value = null; this.next = value; } }

Solution

1. Step 1: Identify the correct property assignments for a node

   A node should store the given value and have a pointer to the next node, initially null.

2. Step 2: Check each option's constructor

   class Node { constructor(value) { this.value = value; this.next = null; } } correctly assigns value and sets next to null. Others assign incorrectly or swap properties.

3. Final Answer:

   class Node { constructor(value) { this.value = value; this.next = null; } } -> Option B

4. Quick Check:

   Node stores value and next pointer [OK]

Hint: Node must store value and next=null initially [OK]

Common Mistakes:

• Swapping value and next assignments
• Not initializing next to null
• Leaving value or next undefined

3. What will be the output after running this code?

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
  }
  add(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = newNode;
    }
  }
  print() {
    let current = this.head;
    let result = '';
    while (current) {
      result += current.value + ' -> ';
      current = current.next;
    }
    result += 'null';
    console.log(result);
  }
}

const list = new LinkedList();
list.add(10);
list.add(20);
list.add(30);
list.print();

medium

A. 10 -> 20 -> 30 -> null

B. 30 -> 20 -> 10 -> null

C. 10 -> 20 -> null

D. null

Solution

1. Step 1: Trace the add method calls

   Adding 10 sets head to node with value 10. Adding 20 and 30 appends nodes at the end.

2. Step 2: Trace the print method

   Print traverses from head: 10, then 20, then 30, then null.

3. Final Answer:

   10 -> 20 -> 30 -> null -> Option A

4. Quick Check:

   Nodes added in order, printed in order [OK]

Hint: Add appends at end; print shows nodes in insertion order [OK]

Common Mistakes:

• Assuming add inserts at head
• Printing nodes in reverse order
• Missing last node in print

4. Identify the error in this linked list add method and select the fix:

add(value) {
  const newNode = new Node(value);
  if (this.head === null) {
    this.head = newNode;
  } else {
    let current = this.head;
    while (current.next !== null) {
      current = current.next;
    }
    current = newNode;
  }
}

medium

A. Replace current = newNode; with current.next = newNode;

B. Replace this.head = newNode; with this.head.next = newNode;

C. Remove the while loop entirely

D. Change if (this.head === null) to if (!this.head.next)

Solution

1. Step 1: Understand the purpose of the while loop

   The loop finds the last node where current.next is null.

2. Step 2: Identify the mistake in assignment

   Assigning current = newNode; only changes the local variable, not the list. It should link the last node's next to newNode.

3. Final Answer:

   Replace current = newNode; with current.next = newNode; -> Option A

4. Quick Check:

   Link last node's next to new node [OK]

Hint: Assign newNode to current.next, not current [OK]

Common Mistakes:

• Assigning newNode to current variable instead of current.next
• Changing head incorrectly
• Removing necessary traversal loop

5. You want to create a method remove(value) in your singly linked list that deletes the first node with the given value. Which approach correctly handles removing the head node and other nodes?

hard

A. Remove node by setting head = null if value matches, else do nothing

B. Always traverse from head and remove node by setting current = current.next without checking head separately

C. Traverse list and remove node by setting current.next = null when value matches

D. Check if head has the value, update head to head.next; else traverse and update previous.next to current.next when found

Solution

1. Step 1: Handle removal of head node

   If the head node contains the value, update head to head.next to remove it.

2. Step 2: Traverse and remove non-head nodes

   Traverse nodes keeping track of previous; when node with value found, set previous.next to current.next to unlink it.

3. Final Answer:

   Check if head has the value, update head to head.next; else traverse and update previous.next to current.next when found -> Option D

4. Quick Check:

   Remove head or unlink node by adjusting pointers [OK]

Hint: Handle head removal separately, then unlink nodes [OK]

Common Mistakes:

• Not updating head when removing first node
• Breaking links incorrectly causing list loss
• Setting current.next = null removes too much