707. Design Linked List

MediumDesignLinked List
Leetcode Link

Problem Description

The problem requires designing a custom implementation of a linked list, with the option to use either a singly or a doubly linked list. A singly linked list is made of nodes where each node contains a value (val) and a reference to the next node (next). In the case of a doubly linked list, an additional reference to the previous node (prev) is also included, but this aspect is optional for the problem.

The linked list should be capable of performing the following operations:

  • MyLinkedList() (constructor): Initialize the linked list object.
  • get(index): Retrieve the value at the indexth position of the linked list. If index is not valid (i.e., it's outside the range of the list's nodes), the function should return -1.
  • addAtHead(val): Insert a new node with value val at the beginning of the linked list.
  • addAtTail(val): Insert a new node with value val at the end of the linked list.
  • addAtIndex(index, val): Insert a new node with value val just before the indexth node. If index equals the length of the list, the node is added to the end. If the index is greater than the length, the node isn't added.
  • deleteAtIndex(index): Delete the node at the indexth position if the index is valid.

The linked list nodes are assumed to be 0-indexed, which means the first node has an index of 0, the second has an index of 1, and so on.

Intuition

The solution follows the standard approach for managing a singly linked list with essential operations like adding and removing elements. The main idea is to establish dummy head nodes to simplify insertions and deletions at the head to avoid edge cases.

  • To retrieve a value (get), traverse nodes sequentially until reaching the desired index.
  • To add a node (addAtHead, addAtTail, addAtIndex), find the correct insertion point considering the index and insert the new node by adjusting the references of the neighboring nodes. When adding to the head or tail, the operations are simplified since these are common cases, handled by redirecting the dummy head or tail reference to the new node.
  • To delete a node (deleteAtIndex), locate the node just before the one to be deleted. Adjust its next reference to bypass the deleted node, effectively removing it from the list.

Counting nodes (cnt) and dummy nodes (dummy) make operations more straightforward by reducing edge-case checking and maintenance of the list’s size, which is crucial when checking for valid indexes.

The operations' time complexity is generally O(n), except for adding at the head, which is O(1). The space complexity is O(1) for each operation since we only use a constant amount of extra space.

Learn more about Linked List patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

Solution Approach

The implementation of the MyLinkedList class follows common design patterns used in object-oriented programming for linked list manipulation, relying on the concept of nodes and references that point from one node to the next. The solution includes an inner class, ListNode, to define the structure of each node in the linked list.

Let's break down the main components of the implementation:

  • ListNode Class: This is a nested helper class within MyLinkedList. Each instance of ListNode represents a node in the linked list, containing the elements val (the current node's value) and next (a pointer to the next node in the list).

  • Dummy Node: A dummy head node, self.dummy, initialized to ListNode(), is used to simplify edge cases when modifying the head of the list. The dummy node does not hold any data and is used to reference the first actual element in the linked list.

  • Node Count: The self.cnt variable tracks the current number of nodes in the linked list, excluding the dummy node. This is crucial for validating indexes and simplifying the adding processes.

Here is how each method is implemented:

  • __init__(self): Initializes the linked list object with a dummy node and a node count set to zero.

  • get(self, index): Returns the value of the node at the given index by first ensuring the index is within bounds (0 to self.cnt - 1). It then traverses the list starting from the node after the dummy node using a simple loop up to the desired index.

  • addAtHead(self, val): Simplifies adding a new node at the head by calling addAtIndex with 0 as the index, thus adding it immediately after the dummy node.

  • addAtTail(self, val): Calls addAtIndex with self.cnt as the index, effectively placing the new node at the end of the list.

  • addAtIndex(self, index, val): Adds a new node at a specific index by traversing up to the node just before the target position. Once there, it inserts the new node by adjusting the next references to link the new node into the list. If the given index is greater than self.cnt, the method exits without making any changes, as specified by the problem description.

  • deleteAtIndex(self, index): Removes a node from a specific index by first making sure the index is valid, then finding the node just before the one that should be deleted, and adjusting its next reference to skip the node to be removed.

This carefully designed implementation accounts for various edge cases and makes use of the dummy node pattern and node count to enhance the efficiency and readability of the linked list operations.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm should you use to find a node that is close to the root of the tree?

Example Walkthrough

Let's walk through a small example to illustrate the implementation of our MyLinkedList class.

  1. Initialize: Suppose we call MyLinkedList() constructor.

    • The linked list is now initialized. It has a dummy node and the count (self.cnt) is set to 0.
    • Currently, the list looks like this: dummy -> null.

  2. addAtHead(1): We want to add a value 1 at the head of the list.

    • The method addAtHead(1) is invoked, which internally calls addAtIndex(0, 1).
    • Since the index is 0, the new node with value 1 is inserted right after the dummy node.
    • Now the list looks like this: dummy -> 1 -> null.
    • The count (self.cnt) is incremented to 1.

  3. addAtTail(3): Now, we add a value 3 at the tail of the list.

    • Calling addAtTail(3) will invoke addAtIndex(self.cnt, 3).
    • The new node with value 3 is inserted after the node with value 1.
    • The list now looks like this: dummy -> 1 -> 3 -> null.
    • The count (self.cnt) is incremented to 2.

  4. addAtIndex(1, 2): Next, we insert a value 2 at index 1.

    • The addAtIndex(1, 2) method will traverse the list and insert the new node with value 2 between the nodes 1 and 3.
    • The list is now: dummy -> 1 -> 2 -> 3 -> null.
    • The count (self.cnt) is updated to 3.

  5. get(1): To get the value at index 1.

    • We call the get(1) method. This method traverses the list and returns the value of the node at index 1.
    • This will return 2 since the node at index 1 has the value 2.

  6. deleteAtIndex(1): Now, let's delete the node at index 1.

    • Invoking deleteAtIndex(1) method locates the node just before the target node (the node with value 1) and updates its next reference to the node after the target node (the node with value 3).
    • The node with value 2 is now removed from the list.
    • The list becomes: dummy -> 1 -> 3 -> null.
    • The count (self.cnt) is decremented to 2.

At each step, the aforementioned methods manipulate the linked list by adding, retrieving, or deleting nodes while keeping track of the node count for index validations and the integrity of the list. This simple example demonstrates the fundamental operations of our custom singly linked list.

Solution Implementation

1class ListNode:
2    def __init__(self, value=0, next_node=None):
3        self.val = value
4        self.next = next_node
5
6class MyLinkedList:
7    def __init__(self):
8        # A dummy node is used to simplify edge cases by providing a non-null next node.
9        self.dummy = ListNode()
10        # Counter for the number of elements in the linked list.
11        self.size = 0
12
13    def get(self, index: int) -> int:
14        # If index is out of bounds, return -1.
15        if index < 0 or index >= self.size:
16            return -1
17      
18        # Traverse the linked list to the given index.
19        current = self.dummy.next
20        for _ in range(index):
21            current = current.next
22        # Return the value at the given index.
23        return current.val
24
25    def addAtHead(self, val: int) -> None:
26        # Delegate to addAtIndex to add an element at the head (index 0).
27        self.addAtIndex(0, val)
28
29    def addAtTail(self, val: int) -> None:
30        # Delegate to addAtIndex to add an element at the tail (end of the list).
31        self.addAtIndex(self.size, val)
32
33    def addAtIndex(self, index: int, val: int) -> None:
34        # If index is greater than the size, don't perform the add.
35        if index > self.size:
36            return
37      
38        # Find the predecessor node (pre) for the index where new node will be added.
39        predecessor = self.dummy
40        for _ in range(index):
41            predecessor = predecessor.next
42      
43        # Insert new node with value `val` after predecessor node.
44        new_node = ListNode(val, predecessor.next)
45        predecessor.next = new_node
46        # Increment size after addition.
47        self.size += 1
48
49    def deleteAtIndex(self, index: int) -> None:
50        # If index is out of range, do nothing.
51        if index < 0 or index >= self.size:
52            return
53      
54        # Find the predecessor node of the node to be deleted.
55        predecessor = self.dummy
56        for _ in range(index):
57            predecessor = predecessor.next
58      
59        # Skip over the node at the index to delete it.
60        to_delete = predecessor.next
61        predecessor.next = to_delete.next
62        # Optional: clear the next reference of the deleted node.
63        to_delete.next = None
64        # Decrement size after deletion.
65        self.size -= 1
66
67
68# Commentary on how this code might be used:
69# This MyLinkedList class can be instantiated and then methods can be called on the instance
70# to manipulate the linked list, such as adding at the head, tail, or arbitrary index, 
71# deleting at an index, or getting the value at an index. For example:
72# linked_list = MyLinkedList()
73# linked_list.addAtHead(1)
74# linked_list.addAtTail(2)
75# print(linked_list.get(1))  # Should print the value `2`.
76# linked_list.addAtIndex(1, 3)  # Linked list is now 1 -> 3 -> 2.
77# linked_list.deleteAtIndex(1)  # Linked list is now 1 -> 2.
78
1// Definition for singly-linked list node.
2class ListNode {
3    int value; // Value of the node.
4    ListNode next; // Reference to the next node.
5
6    // Constructor to create a node with specified value and next node reference.
7    ListNode(int val, ListNode next) {
8        this.value = val;
9        this.next = next;
10    }
11
12    // Constructor to create a node with specified value.
13    ListNode(int val) {
14        this(val, null);
15    }
16}
17
18// Class representing a singly-linked list.
19class MyLinkedList {
20    // A dummy head to simplify the edge cases.
21    private ListNode dummyHead = new ListNode(0); 
22    private int size; // Number of elements in the linked list.
23
24    // Constructor for initializing the linked list.
25    public MyLinkedList() {
26    }
27
28    // Method to get the value of the index-th node in the linked list. If the index is invalid, return -1.
29    public int get(int index) {
30        if (index < 0 || index >= size) {
31            return -1; // Index out of bounds.
32        }
33        ListNode current = dummyHead.next;
34        while (index-- > 0) {
35            current = current.next;
36        }
37        return current.value;
38    }
39
40    // Method to add a node of value val before the first element of the linked list.
41    public void addAtHead(int val) {
42        addAtIndex(0, val);
43    }
44
45    // Method to append a node of value val to the last element of the linked list.
46    public void addAtTail(int val) {
47        addAtIndex(size, val);
48    }
49
50    // Method to add a node of value val before the index-th node in the linked list.
51    public void addAtIndex(int index, int val) {
52        // If index is greater than the size, the node will not be inserted.
53        if (index > size) {
54            return;
55        }
56        ListNode precursor = dummyHead;
57        while (index-- > 0) {
58            precursor = precursor.next;
59        }
60        precursor.next = new ListNode(val, precursor.next);
61        size++; // Increase list size.
62    }
63
64    // Method to delete the index-th node in the linked list, if the index is valid.
65    public void deleteAtIndex(int index) {
66        if (index < 0 || index >= size) {
67            return; // Index out of bounds.
68        }
69        ListNode precursor = dummyHead;
70        while (index-- > 0) {
71            precursor = precursor.next;
72        }
73        ListNode toDelete = precursor.next;
74        precursor.next = toDelete.next;
75        toDelete.next = null; // Help the garbage collector by removing references.
76        size--; // Decrease list size.
77    }
78}
79
80/**
81 * Your MyLinkedList object will be instantiated and called as follows:
82 * MyLinkedList obj = new MyLinkedList();
83 * int param_1 = obj.get(index);
84 * obj.addAtHead(val);
85 * obj.addAtTail(val);
86 * obj.addAtIndex(index, val);
87 * obj.deleteAtIndex(index);
88 */
89
1// Definition for singly-linked list node.
2struct ListNode {
3    int val;
4    ListNode *next;
5    ListNode(int x) : val(x), next(nullptr) {}
6    ListNode(int x, ListNode *next) : val(x), next(next) {}
7};
8
9// Class to implement singly linked list with basic operations.
10class MyLinkedList {
11private:
12    ListNode* dummy = new ListNode(0); // Create a dummy node to act as a sentinel node.
13    int size = 0; // Store the size of the linked list.
14
15public:
16    // Constructor initializes the linked list.
17    MyLinkedList() {
18    }
19
20    // Function to return the value at the given index. If the index is invalid, return -1.
21    int get(int index) {
22        if (index < 0 || index >= size) {
23            return -1;
24        }
25        ListNode* current = dummy->next;
26        while (index--) {
27            current = current->next;
28        }
29        return current->val;
30    }
31
32    // Function to add a node with the given value at the head of the list.
33    void addAtHead(int val) {
34        addAtIndex(0, val);
35    }
36
37    // Function to add a node with the given value at the tail of the list.
38    void addAtTail(int val) {
39        addAtIndex(size, val);
40    }
41
42    // Function to add a node with the given value at the specified index.
43    void addAtIndex(int index, int val) {
44        if (index > size) {
45            return;
46        }
47        ListNode* prev = dummy;
48        while (index-- > 0) {
49            prev = prev->next;
50        }
51        prev->next = new ListNode(val, prev->next);
52        size++;
53    }
54
55    // Function to delete a node at the specified index.
56    void deleteAtIndex(int index) {
57        if (index < 0 || index >= size) {
58            return;
59        }
60        ListNode* prev = dummy;
61        while (index-- > 0) {
62            prev = prev->next;
63        }
64        ListNode* temp = prev->next;
65        prev->next = temp->next;
66        delete temp; // Free the memory allocated to the node.
67        size--;
68    }
69};
70
71/**
72 * Your MyLinkedList object will be instantiated and called as such:
73 * MyLinkedList* obj = new MyLinkedList();
74 * int param_1 = obj->get(index);
75 * obj->addAtHead(val);
76 * obj->addAtTail(val);
77 * obj->addAtIndex(index, val);
78 * obj->deleteAtIndex(index);
79 */
80
1type LinkNode = {
2    val: number;
3    next: LinkNode | null;
4};
5
6// Global head node for the linked list, initially set to null
7let head: LinkNode | null = null;
8
9// Fetches the value at the specified index in the linked list
10function get(index: number): number {
11    if (head == null) {
12        return -1;
13    }
14  
15    let currentNode: LinkNode | null = head;
16    let currentIndex: number = 0;
17  
18    while (currentIndex < index) {
19        if (currentNode.next == null) {
20            return -1;
21        }
22      
23        currentNode = currentNode.next;
24        currentIndex++;
25    }
26  
27    return currentNode.val;
28}
29
30// Adds a new node with the given value at the start of the linked list
31function addAtHead(val: number): void {
32    head = { val, next: head };
33}
34
35// Adds a new node with the given value at the end of the linked list
36function addAtTail(val: number): void {
37    const newNode: LinkNode = { val, next: null };
38  
39    if (head == null) {
40        head = newNode;
41        return;
42    }
43  
44    let currentNode: LinkNode = head;
45  
46    while (currentNode.next != null) {
47        currentNode = currentNode.next;
48    }
49  
50    currentNode.next = newNode;
51}
52
53// Adds a new node with the given value at the specified index
54function addAtIndex(index: number, val: number): void {
55    if (index <= 0) {
56        addAtHead(val);
57        return;
58    }
59  
60    const dummyNode: LinkNode = { val: 0, next: head };
61    let currentNode: LinkNode = dummyNode;
62    let currentIndex: number = 0;
63  
64    while (currentIndex < index) {
65        if (currentNode.next == null) {
66            return;
67        }
68      
69        currentNode = currentNode.next;
70        currentIndex++;
71    }
72  
73    const newNode: LinkNode = { val, next: currentNode.next };
74    currentNode.next = newNode;
75  
76    if (dummyNode.next !== head) {
77        head = dummyNode.next;
78    }
79}
80
81// Deletes the node at the specified index from the linked list
82function deleteAtIndex(index: number): void {
83    if (index === 0) {
84        head = head ? head.next : null;
85        return;
86    }
87  
88    const dummyNode: LinkNode = { val: 0, next: head };
89    let currentNode: LinkNode = dummyNode;
90    let currentIndex: number = 0;
91  
92    while (currentIndex < index) {
93        if (currentNode.next == null) {
94            return;
95        }
96      
97        currentNode = currentNode.next;
98        currentIndex++;
99    }
100  
101    currentNode.next = currentNode.next ? currentNode.next.next : null;
102  
103    if (dummyNode.next !== head) {
104        head = dummyNode.next;
105    }
106}
107
Not Sure What to Study? Take the 2-min Quiz：

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Time and Space Complexity

Time Complexity

  • get(index): The time complexity is O(index) because it traverses the list up to the given index.
  • addAtHead(val): This is O(1) as it calls addAtIndex with 0, which means it inserts the node right after the dummy head without any traversal.
  • addAtTail(val): The time complexity is O(n) where n is the number of elements in the linked list, as it traverses the entire list to find the end before insertion.
  • addAtIndex(index, val): The time complexity is O(min(index, n)) where n is the number of elements in the list because it traverses the list up to the given index for insertion.
  • deleteAtIndex(index): The time complexity is O(index) as it has to traverse up to the index to find the node to delete.

Space Complexity

  • For all operations, the space complexity is O(1) if we don't consider the space occupied by the elements themselves, as we're only using a constant amount of extra space for pointers and temporary variables in all the methods. However, if we account for the growing size of the list, then we can consider the space complexity for the whole data structure to be O(n) where n is the number of elements in the linked list.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

How many ways can you arrange the three letters A, B and C?

Recommended Readings

Linked List Cycle

Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫