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

Overview - Creating a Singly Linked List from Scratch

What is it?

A singly linked list is a simple chain of elements where each element points to the next one. It starts with a head element and ends when there is no next element. This structure allows easy insertion and removal of elements without shifting others. It is a basic building block for many other data structures.

Why it matters

Without singly linked lists, managing collections of items would be less flexible and efficient. Arrays require shifting elements when adding or removing items, which can be slow. Linked lists let us add or remove items quickly by changing pointers, making programs faster and more memory-friendly in many cases.

Where it fits

Before learning singly 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.

Mental Model

Core Idea

A singly linked list is a chain of nodes where each node holds data and a link to the next node, forming a simple one-way path.

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, guiding you along the path.

Head -> [Data | Next] -> [Data | Next] -> [Data | null]
Each box is a node with data and a pointer to the next node. The last node points to null, meaning the end.

Build-Up - 7 Steps

1

Foundation

Understanding Node Structure

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

In TypeScript, a node can be a class with two properties: one for the data it holds and one for the reference to the next node. For example: class Node { data: T; next: Node | null; constructor(data: T) { this.data = data; this.next = null; } } This creates a single node that can hold any type of data and points to nothing initially.

Result

You can create a node like new Node(5) which holds the number 5 and points to null.

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

2

Foundation

Creating the Linked List Class

Concept: Build a class to manage the linked list, starting with a head pointer.

The linked list class keeps track of the first node, called head. Initially, the list is empty, so head is null. class LinkedList { head: Node | null; constructor() { this.head = null; } } This class will hold methods to add, remove, and display nodes.

Result

You have a linked list object with no nodes yet (head is null).

The head pointer is the entry point to the list; without it, you cannot access any nodes.

3

Intermediate

Adding Nodes at the Beginning

🤔Before reading on: do you think adding a node at the start requires changing the head pointer or just the new node's next pointer? Commit to your answer.

Concept: Learn how to insert a new node at the start of the list by updating pointers.

To add a node at the beginning: 1. Create a new node. 2. Set its next pointer to the current head. 3. Update head to this new node. Example method: addFirst(data: T) { const newNode = new Node(data); newNode.next = this.head; this.head = newNode; } This keeps the list connected and updates the entry point.

Result

After adding 10, then 20, the list looks like: 20 -> 10 -> null

Knowing that the head pointer must move to the new node is crucial to keep the list intact and accessible.

4

Intermediate

Traversing the List to Display

🤔Before reading on: do you think you can access all nodes by starting at head and following next pointers until null? Commit to your answer.

Concept: Learn how to visit each node in order to read or display data.

To see all elements: 1. Start at head. 2. While the current node is not null, print its data. 3. Move to the next node. Example method: printList() { let current = this.head; let result = ''; while (current) { result += current.data + ' -> '; current = current.next; } result += 'null'; console.log(result); } This shows the list from start to end.

Result

Output: 20 -> 10 -> null

Understanding traversal is essential because it lets you access all nodes, which is the basis for many list operations.

5

Intermediate

Adding Nodes at the End

🤔Before reading on: do you think adding at the end requires traversing the whole list or just changing the last node? Commit to your answer.

Concept: Learn how to insert a new node at the end by finding the last node and updating its pointer.

To add at the end: 1. Create a new node. 2. If the list is empty, set head to new node. 3. Otherwise, traverse to the last node (where next is null). 4. Set last node's next to new node. Example method: addLast(data: T) { const newNode = new Node(data); if (!this.head) { this.head = newNode; return; } let current = this.head; while (current.next) { current = current.next; } current.next = newNode; } This keeps the list connected with the new node at the end.

Result

After adding 30 at end: 20 -> 10 -> 30 -> null

Knowing that you must find the last node to add at the end helps avoid breaking the list or losing nodes.

6

Advanced

Removing Nodes by Value

🤔Before reading on: do you think removing a node requires changing the previous node's next pointer or the node itself? Commit to your answer.

Concept: Learn how to find and remove a node by changing pointers to skip it.

To remove a node with specific data: 1. Check if head is the node to remove; if yes, update head. 2. Otherwise, traverse the list keeping track of previous node. 3. When found, set previous node's next to current node's next. Example method: remove(data: T) { if (!this.head) return; if (this.head.data === data) { this.head = this.head.next; return; } let current = this.head.next; let prev = this.head; while (current) { if (current.data === data) { prev.next = current.next; return; } prev = current; current = current.next; } } This removes the node without breaking the chain.

Result

Removing 10 from 20 -> 10 -> 30 -> null results in 20 -> 30 -> null

Understanding pointer updates during removal prevents losing parts of the list or creating loops.

7

Expert

Handling Edge Cases and Memory

🤔Before reading on: do you think forgetting to update pointers can cause memory leaks or inaccessible nodes? Commit to your answer.

Concept: Learn about special cases like empty list, single node list, and how memory is managed.

Edge cases include: - Removing from an empty list (do nothing). - Removing the only node (head becomes null). - Adding to empty list (head points to new node). In TypeScript, garbage collection frees memory of unreferenced nodes automatically. But if pointers are not updated correctly, nodes can become unreachable but still in memory (memory leak). Careful pointer management ensures list integrity and efficient memory use.

Result

Robust linked list handles all cases without errors or leaks.

Knowing edge cases and memory behavior helps build reliable and efficient linked lists in real applications.

Under the Hood

Each node is an object stored in memory with two parts: data and a reference (pointer) to the next node. The list itself holds a reference to the first node (head). Operations like adding or removing nodes work by changing these references, not by moving data around. This pointer manipulation is what makes linked lists flexible and efficient for certain tasks.

Why designed this way?

Linked lists were designed to overcome the limitations of arrays, especially fixed size and costly insertions/deletions. By using pointers, linked lists allow dynamic memory use and fast updates without shifting elements. Early computers had limited memory, so this design was crucial for efficient data management.

LinkedList
  └─ head
      ├─ Node(data, next) ──┐
      ├─ Node(data, next) ──┤
      └─ Node(data, null)   ┘

Operations:
AddFirst: newNode.next = head; head = newNode
AddLast: traverse to last; last.next = newNode
Remove: prev.next = current.next

Myth Busters - 4 Common Misconceptions

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

Common Belief: A singly linked list lets you move forward and backward through the nodes easily.

Reality: A singly linked list only allows moving forward from head to tail; you cannot go backwards without extra pointers.

Why it matters: Trying to move backwards causes errors or requires inefficient traversal from the head each time, slowing down programs.

Quick: When adding a node at the end, do you think you can just set head.next to new node? Commit yes or no.

Common Belief: To add a node at the end, you can always set head.next to the new node.

Reality: You must find the last node (where next is null) and set its next pointer; head.next only works if the list has exactly one node.

Why it matters: Incorrectly setting head.next overwrites existing nodes and breaks the list, causing data loss.

Quick: Does removing a node mean deleting the node object directly? Commit yes or no.

Common Belief: Removing a node means deleting the node object from memory immediately.

Reality: In languages with garbage collection like TypeScript, you remove references to the node; the system frees memory later automatically.

Why it matters: Trying to manually delete nodes can cause errors; understanding references prevents bugs and memory leaks.

Quick: Is it safe to assume the list is never empty after creation? Commit yes or no.

Common Belief: Once a linked list is created, it always has at least one node.

Reality: A linked list can be empty with head set to null until nodes are added.

Why it matters: Assuming non-empty lists causes runtime errors when accessing head or next pointers.

Expert Zone

1

Efficient linked lists often keep a tail pointer to avoid traversing the entire list when adding at the end.

2

In performance-critical systems, node allocation and deallocation can be optimized using object pools to reduce memory overhead.

3

Singly linked lists can be made circular by pointing the last node back to head, enabling continuous traversal but requiring careful handling to avoid infinite loops.

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 alternatives. For very large data, balanced trees or hash tables may offer faster search and update.

Production Patterns

In real systems, singly linked lists are used for simple queues, stacks, and adjacency lists in graphs. They are often combined with sentinel nodes to simplify edge case handling and improve code clarity.

Connections

Doubly Linked List

Builds-on

Understanding singly linked lists is essential before learning doubly linked lists, which add backward pointers for two-way traversal.

Memory Management

Underlying principle

Linked lists illustrate how pointers and references manage memory dynamically, a concept crucial in systems programming and garbage collection.

Supply Chain Logistics

Structural similarity

Like linked lists, supply chains connect stages in a sequence where each step depends on the previous, showing how linear dependencies work in different fields.

Common Pitfalls

#1 Losing the rest of the list when adding a new head node.

Wrong approach:

addFirst(data: T) {
const newNode = new Node(data);
this.head = newNode; // Forgot to link newNode.next to old head
}

Correct approach:

addFirst(data: T) {
const newNode = new Node(data);
newNode.next = this.head;
this.head = newNode;
}

Root cause:

Not updating the new node's next pointer causes the old list to become unreachable.

#2 Trying to remove a node without tracking the previous node.

Wrong approach:

remove(data: T) {
let current = this.head;
while (current) {
if (current.data === data) {
current = current.next; // Does not update previous node's next
return;
}
current = current.next;
}
}

Correct approach:

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

Root cause:

Failing to update the previous node's next pointer leaves the list broken and the node not removed.

#3 Assuming the list is never empty and accessing head.next directly.

Wrong approach:

printList() {
let current = this.head.next; // Error if head is null
while (current) {
console.log(current.data);
current = current.next;
}
}

Correct approach:

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

Root cause:

Not checking if head is null causes runtime errors when the list is empty.

Key Takeaways

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

The head pointer is the entry point to the list and must be carefully updated during insertions and deletions to maintain list integrity.

Traversing the list means following next pointers from head until reaching null, which marks the end.

Proper pointer updates prevent losing nodes or creating broken links, which are common sources of bugs.

Understanding edge cases and memory behavior ensures robust and efficient linked list implementations.

Practice

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

easy

A. To store elements in a sequence where each element points to the next one

B. To store elements with keys and values for fast lookup

C. To store elements in a sorted array for quick access

D. To store elements in a tree-like hierarchy

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 in the sequence.

2. Step 2: Compare with other data structures

   Unlike key-value stores or trees, singly linked lists maintain a simple linear chain of elements.

3. Final Answer:

   To store elements in a sequence where each element points to the next one -> Option A

4. Quick Check:

   Singly Linked List = sequence with next pointers [OK]

Hint: Remember: singly linked list nodes point only forward [OK]

Common Mistakes:

• Confusing linked lists with arrays
• Thinking linked lists store key-value pairs
• Assuming linked lists are hierarchical like trees

2. Which of the following is the correct TypeScript syntax to define a node class for a singly linked list?

easy

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

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

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

D. class Node { value: number; next: any; constructor(value: number) { this.value = value; this.next = undefined; } }

Solution

1. Step 1: Check the type of the next pointer

   The next pointer should be either another Node or null if it is the last node.

2. Step 2: Verify constructor initialization

   The constructor sets the value and initializes next to null, which is correct for a new node.

3. Final Answer:

   class Node { value: number; next: Node | null; constructor(value: number) { this.value = value; this.next = null; } } -> Option A

4. Quick Check:

   next can be Node or null = class Node { value: number; next: Node | null; constructor(value: number) { this.value = value; this.next = null; } } [OK]

Hint: Use union type for next: Node | null [OK]

Common Mistakes:

• Forgetting to allow next to be null
• Setting next to undefined instead of null
• Using any type for next which loses type safety

3. What will be the output after running this TypeScript code that creates a singly linked list with values 10, 20, 30 and prints it?

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

class LinkedList {
  head: Node | null = null;

  append(value: number) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      return;
    }
    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.append(10);
list.append(20);
list.append(30);
list.print();

medium

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

B. null

C. 10 -> 20 -> null

D. 10 -> 20 -> 30 -> null

Solution

1. Step 1: Append nodes in order

   Nodes with values 10, 20, and 30 are appended in that order, so the list is 10 -> 20 -> 30.

2. Step 2: Print the list

   The print method traverses from head to end, concatenating values with ' -> ' and ending with 'null'.

3. Final Answer:

   10 -> 20 -> 30 -> null -> Option D

4. Quick Check:

   Appending preserves order = 10 -> 20 -> 30 -> null [OK]

Hint: Append adds at end; print shows sequence [OK]

Common Mistakes:

• Assuming append adds at head instead of tail
• Forgetting to add 'null' at the end
• Printing values in reverse order

4. Identify the error in this TypeScript code snippet that tries to append a node to a singly linked list:

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

class LinkedList {
  head: Node | null = null;

  append(value: number) {
    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.next = newNode;
    }
  }
}

const list = new LinkedList();
list.append(5);
list.append(10);
console.log(list.head.next.value);

medium

A. Error: head is undefined

B. Error: Cannot read property 'value' of null

C. No error; output will be 10

D. Error: next property is missing in Node

Solution

1. Step 1: Check append logic

   The append method correctly adds the first node as head and subsequent nodes at the end.

2. Step 2: Verify output of console.log

   After appending 5 and 10, head.next points to the node with value 10, so accessing value is valid.

3. Final Answer:

   No error; output will be 10 -> Option C

4. Quick Check:

   Proper append and access = 10 [OK]

Hint: Check if head and next are properly assigned before access [OK]

Common Mistakes:

• Forgetting to return after setting head in append
• Accessing next.value when next is null
• Not initializing next to null in Node

5. You want to create a method reverse() in your singly linked list class that reverses the list in place. Which approach correctly reverses the links between nodes?

hard

A. Create a new list and append nodes from the original list in reverse order

B. Iterate through the list, for each node set its next to the previous node, updating previous and current pointers

C. Swap the values of the first and last nodes repeatedly until the middle is reached

D. Remove all nodes and re-insert them at the head one by one

Solution

1. Step 1: Understand in-place reversal

   Reversing links means changing each node's next pointer to point to the previous node, not creating new nodes.

2. Step 2: Identify correct method

   Iterating with previous and current pointers and updating next links reverses the list efficiently in place.

3. Final Answer:

   Iterate through the list, for each node set its next to the previous node, updating previous and current pointers -> Option B

4. Quick Check:

   In-place reversal = update next pointers backward [OK]

Hint: Reverse by redirecting next pointers, not swapping values [OK]

Common Mistakes:

• Swapping node values instead of links
• Creating a new list instead of reversing in place
• Removing and re-adding nodes unnecessarily