Design Linked List | Leetcode 707 | Explained in Python

The “Design Linked List” problem is a fundamental data structure question that tests your understanding of how linked lists work and how to implement them from scratch.

In this blog, we’ll explain the problem, the intuition behind each method, and walk through the implementation step by step, making it easy to follow for students and beginners.

Here’s the [Problem Link] to begin with.

What Does the Problem Say?

You have to design your own singly linked list. Implement the following methods:

• get(index): Get the value of the index-th node. If the index is invalid, return -1.
• addAtHead(val): Add a node of value val before the first node.
• addAtTail(val): Append a node of value val as the last node.
• addAtIndex(index, val): Add a node of value val before the index-th node.
• deleteAtIndex(index): Delete the index-th node in the list if the index is valid.

Example

Input:

["MyLinkedList","addAtHead","addAtTail","addAtIndex","get","deleteAtIndex","get"]
[[],[1],[3],[1,2],[1],[1],[1]]

Explanation:

[null,null,null,null,2,null,3]

Intuition and Approach

Why Linked List?

Unlike arrays, a linked list allows us to add or remove elements efficiently at the head, tail, or any given position without shifting other elements. Each node points to the next, and we control the connections.

How Does Each Operation Work?

1. get(index)
   • Start from the head and move to the next node index times.
   • If you reach the desired index, return its value; otherwise, return -1.
2. addAtHead(val)
   • Create a new node.
   • Set its next pointer to the current head.
   • Update the head to this new node.
3. addAtTail(val)
   • Move to the end (last node) of the list.
   • Set the next pointer of the last node to the new node.
4. addAtIndex(index, val)
   • Move to the node just before the target index.
   • Insert the new node by adjusting pointers.
   • Special case: if index is 0, use addAtHead.
5. deleteAtIndex(index)
   • Move to the node just before the target index.
   • Bypass the node to delete by adjusting pointers.
   • Special case: if index is 0, move head pointer to the next node.

Why do we keep track of size?
Tracking the size helps us quickly know if an index is valid for operations.

Code Implementation

class Node:
    def __init__(self, val=0, next=None):
        self.val = val              # Node value
        self.next = next            # Pointer to next node

class MyLinkedList:
    def __init__(self):
        self.head = None            # Start of the list
        self.size = 0               # Number of elements in list

    def get(self, index: int) -> int:
        if index < 0 or index >= self.size:
            return -1
        temp = self.head
        for _ in range(index):      # Move to index-th node
            temp = temp.next
        return temp.val

    def addAtHead(self, val: int) -> None:
        node = Node(val, self.head) # New node points to current head
        self.head = node            # Head is now the new node
        self.size += 1

    def addAtTail(self, val: int) -> None:
        node = Node(val)
        if not self.head:           # If list is empty
            self.head = node
        else:
            temp = self.head
            while temp.next:        # Go to last node
                temp = temp.next
            temp.next = node        # Link last node to new node
        self.size += 1

    def addAtIndex(self, index: int, val: int) -> None:
        if index < 0:
            index = 0
        if index > self.size:       # Out of bounds
            return
        if index == 0:              # Add at head
            self.addAtHead(val)
        else:
            prev = self.head
            for _ in range(index - 1):
                prev = prev.next    # Move to node before index
            node = Node(val, prev.next)
            prev.next = node        # Insert node
            self.size += 1

    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.size:  # Invalid index
            return
        if index == 0:                       # Delete head
            self.head = self.head.next
        else:
            prev = self.head
            for _ in range(index - 1):
                prev = prev.next            # Move to node before index
            prev.next = prev.next.next      # Bypass target node
        self.size -= 1

Code Explanation

• The Node class is a simple building block for the linked list, storing a value and a pointer to the next node.
• The MyLinkedList class keeps track of the list’s head and size.
• Each method manipulates the pointers and size to ensure the list remains valid after every operation.

Dry Run

Let’s visualize the following operations step by step:

Operations:
addAtHead(1) ⟶ addAtTail(3) ⟶ addAtIndex(1,2) ⟶ get(1) ⟶ deleteAtIndex(1) ⟶ get(1)

1. addAtHead(1): List – 
2. addAtTail(3): List – 
3. addAtIndex(1, 2): Move to node at index 0 (1), insert 2 after 1 → [1,
4. get(1): Move to node at index 1 → Value is 2
5. deleteAtIndex(1): Move to node at index 0 (1), skip the next node. Now list is 
6. get(1): Move to node at index 1 → Value is 3

Time and Space Complexity

• All operations: O(n) in the worst case (since you may need to traverse the list)
• Space Complexity: O(1) extra (not counting the nodes themselves)

Conclusion

Designing a linked list from scratch is great practice for learning pointers and dynamic data structures. Mastering these building blocks helps you understand more complex data structures and memory management.

If you practice and understand each step, you’ll be able to design your own linked lists and even more advanced structures in the future!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.