Design Linked List

Med

#0661Time: - `get(index)`, `addAtIndex(index, val)`, `deleteAtIndex(index)`: O(k) where k is the target index. The worst-case complexity is O(N) when the index is near the end of the list. - `addAtHead(val)`: O(1), as it only involves updating the pointers at the head. - `addAtTail(val)`: O(N), as it requires traversing the entire list to reach the last node before appending the new node.Space: O(N), where N is the number of elements in the linked list. Each element requires a node to be stored.

Patterns

Design

Algorithms

LRU Cache

Data structures

Linked List

Prompt

Design your implementation of the linked list. You can choose to use a singly or doubly linked list.
A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node.
If you want to use the doubly linked list, you will need one more attribute prev to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed.

Implement the MyLinkedList class:

MyLinkedList() Initializes the MyLinkedList object.
int get(int index) Get the value of the index^th node in the linked list. If the index is invalid, return -1.
void addAtHead(int val) Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
void addAtTail(int val) Append a node of value val as the last element of the linked list.
void addAtIndex(int index, int val) Add a node of value val before the index^th node in the linked list. If index equals the length of the linked list, the node will be appended to the end of the linked list. If index is greater than the length, the node will not be inserted.
void deleteAtIndex(int index) Delete the index^th node in the linked list, if the index is valid.

Example 1:

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

Explanation
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2);    // linked list becomes 1->2->3
myLinkedList.get(1);              // return 2
myLinkedList.deleteAtIndex(1);    // now the linked list is 1->3
myLinkedList.get(1);              // return 3

Constraints:

0 <= index, val <= 1000
Please do not use the built-in LinkedList library.
At most 2000 calls will be made to get, addAtHead, addAtTail, addAtIndex and deleteAtIndex.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach implements the linked list using a singly-linked structure. Each node points only to the next node in the sequence. To simplify the implementation of insertion and deletion operations, especially at the head of the list, a sentinel (or dummy) node is used. This sentinel node acts as a placeholder before the actual first element, eliminating the need for special checks for an empty list or operations on the first node. We also keep track of the list's size to handle index-based operations correctly.

Algorithm

Node Structure: Each node, SinglyListNode, stores an integer value val and a reference next to the subsequent node.
Class Structure: The MyLinkedList class maintains an integer size for the current number of elements and a head node. This head is a sentinel or dummy node, which simplifies operations at the beginning of the list.
Initialization: The constructor sets size to 0 and initializes the sentinel head node.
get(index): Traverses index + 1 nodes starting from the sentinel head to find the target node. Time complexity is O(k) for index k.
addAtHead(val): A special case of addAtIndex(0, val). With a sentinel node, this becomes an O(1) operation.
addAtTail(val): A special case of addAtIndex(size, val). This requires traversing the entire list to find the last node, resulting in O(N) time complexity.
addAtIndex(index, val): First, it traverses index nodes from the sentinel head to find the predecessor of the insertion point. Then, it updates the next pointers to insert the new node. This takes O(k) for index k.
deleteAtIndex(index): Similar to addAtIndex, it finds the predecessor of the node to be deleted by traversing index nodes. It then updates the predecessor's next pointer to bypass and effectively remove the target node. This also takes O(k) for index k.

Walkthrough

1class MyLinkedList {2    class SinglyListNode {3        int val;4        SinglyListNode next;5        SinglyListNode(int val) {6            this.val = val;7        }8    }9 10    private int size;11    private SinglyListNode head; // Sentinel node12 13    /** Initialize your data structure here. */14    public MyLinkedList() {15        size = 0;16        head = new SinglyListNode(0); // Dummy head17    }18 19    /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */20    public int get(int index) {21        if (index < 0 || index >= size) {22            return -1;23        }24        SinglyListNode curr = head.next;25        for (int i = 0; i < index; i++) {26            curr = curr.next;27        }28        return curr.val;29    }30 31    /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */32    public void addAtHead(int val) {33        addAtIndex(0, val);34    }35 36    /** Append a node of value val to the last element of the linked list. */37    public void addAtTail(int val) {38        addAtIndex(size, val);39    }40 41    /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */42    public void addAtIndex(int index, int val) {43        if (index > size || index < 0) {44            return;45        }46        SinglyListNode pred = head;47        for (int i = 0; i < index; i++) {48            pred = pred.next;49        }50        SinglyListNode toAdd = new SinglyListNode(val);51        toAdd.next = pred.next;52        pred.next = toAdd;53        size++;54    }55 56    /** Delete the index-th node in the linked list, if the index is valid. */57    public void deleteAtIndex(int index) {58        if (index < 0 || index >= size) {59            return;60        }61        SinglyListNode pred = head;62        for (int i = 0; i < index; i++) {63            pred = pred.next;64        }65        pred.next = pred.next.next;66        size--;67    }68}

Complexity

Time

- `get(index)`, `addAtIndex(index, val)`, `deleteAtIndex(index)`: O(k) where k is the target index. The worst-case complexity is O(N) when the index is near the end of the list. - `addAtHead(val)`: O(1), as it only involves updating the pointers at the head. - `addAtTail(val)`: O(N), as it requires traversing the entire list to reach the last node before appending the new node.

Space

O(N), where N is the number of elements in the linked list. Each element requires a node to be stored.

Trade-offs

Pros

The node structure is simple, requiring less memory per node compared to a doubly linked list.
The implementation logic is relatively straightforward.

Cons

Index-based operations like get, addAtIndex, and deleteAtIndex can be slow, with a worst-case time complexity of O(N) if the target index is near the end of the list.
Traversing backwards is not possible.
Without an explicit tail pointer, addAtTail is an O(N) operation, which is inefficient.

A more optimized approach is to use a doubly linked list. This structure enhances the singly linked list by adding a prev pointer to each node, allowing for bidirectional traversal. The key advantage is the ability to access nodes from either the head or the tail. For any operation on an index, we can start traversing from whichever end is closer, significantly improving performance for indices in the latter half of the list. To further streamline the code and eliminate edge cases, this implementation uses two sentinel nodes: a head and a tail. These sentinels mark the boundaries of the list and are always present, even when the list is empty.

Algorithm

Node Structure: Each DoublyListNode contains an integer val, a next pointer to the following node, and a prev pointer to the preceding node.
Class Structure: The MyLinkedList class maintains size, and two sentinel nodes: head and tail. The head sentinel is positioned before the first element, and the tail sentinel is after the last element. In an empty list, head.next points to tail, and tail.prev points to head.
Optimization: For any index-based operation, we check if the index is in the first or second half of the list (i.e., index < size / 2). If it's in the first half, we traverse from the head sentinel; otherwise, we traverse backward from the tail sentinel. This cuts the maximum traversal distance in half.
get(index): Traverses from the closer end (head or tail) to find the node at the given index. Time complexity is O(min(k, N-k)).
addAtHead(val) / addAtTail(val): These are O(1) operations due to the sentinel nodes. They involve updating pointers of the respective sentinel and its adjacent node.
addAtIndex(index, val): Finds the predecessor and successor of the insertion point by traversing from the closer end, then updates the pointers to link the new node in between. Time complexity is O(min(k, N-k)).
deleteAtIndex(index): First, it finds the node to be deleted by traversing from the closer end. Then, it updates the next and prev pointers of its neighbors to remove it from the list. Time complexity is O(min(k, N-k)).

Walkthrough

1class MyLinkedList {2    class DoublyListNode {3        int val;4        DoublyListNode next, prev;5        DoublyListNode(int val) { this.val = val; }6    }7 8    private int size;9    private DoublyListNode head, tail; // Sentinel nodes10 11    public MyLinkedList() {12        size = 0;13        head = new DoublyListNode(0);14        tail = new DoublyListNode(0);15        head.next = tail;16        tail.prev = head;17    }18 19    // Helper to get the node at a specific index.20    private DoublyListNode getNode(int index) {21        DoublyListNode p;22        if (index < size / 2) {23            p = head.next;24            for (int i = 0; i < index; i++) {25                p = p.next;26            }27        } else {28            p = tail.prev;29            for (int i = 0; i < size - 1 - index; i++) {30                p = p.prev;31            }32        }33        return p;34    }35 36    public int get(int index) {37        if (index < 0 || index >= size) {38            return -1;39        }40        return getNode(index).val;41    }42 43    public void addAtHead(int val) {44        addAtIndex(0, val);45    }46 47    public void addAtTail(int val) {48        addAtIndex(size, val);49    }50 51    public void addAtIndex(int index, int val) {52        if (index < 0 || index > size) {53            return;54        }55        56        DoublyListNode pred, succ;57        if (index < size / 2) {58            pred = head;59            for (int i = 0; i < index; i++) {60                pred = pred.next;61            }62            succ = pred.next;63        } else {64            succ = tail;65            for (int i = 0; i < size - index; i++) {66                succ = succ.prev;67            }68            pred = succ.prev;69        }70        71        size++;72        DoublyListNode toAdd = new DoublyListNode(val);73        toAdd.prev = pred;74        toAdd.next = succ;75        pred.next = toAdd;76        succ.prev = toAdd;77    }78 79    public void deleteAtIndex(int index) {80        if (index < 0 || index >= size) {81            return;82        }83        84        DoublyListNode toDelete = getNode(index);85        toDelete.prev.next = toDelete.next;86        toDelete.next.prev = toDelete.prev;87        size--;88    }89}

Complexity

Time

- `get(index)`, `addAtIndex(index, val)`, `deleteAtIndex(index)`: O(min(k, N-k)), where k is the index and N is the list size. This is because we can traverse from the closer end. The worst-case is O(N) for the middle element. - `addAtHead(val)`, `addAtTail(val)`: O(1), thanks to the head and tail sentinel nodes.

Space

O(N), where N is the number of elements. While still linear, the constant factor is higher than for a singly linked list because each node stores an additional pointer.

Trade-offs

Pros

Index-based operations (get, addAtIndex, deleteAtIndex) are faster on average due to bidirectional traversal.
addAtHead and addAtTail are both efficient O(1) operations.
Deletion is efficient if a pointer to the node is already known, as its predecessor can be accessed in O(1).

Cons

Each node requires more memory due to the extra prev pointer.
The implementation is slightly more complex because both next and prev pointers must be managed correctly for every operation.

Solutions

Solution

1class MyLinkedList { private ListNode dummy = new ListNode (); private int cnt ; public MyLinkedList () { } public int get ( int index ) { if ( index < 0 || index >= cnt ) { return - 1 ; } var cur = dummy . next ; while ( index -- > 0 ) { cur = cur . next ; } return cur . val ; } public void addAtHead ( int val ) { addAtIndex ( 0 , val ); } public void addAtTail ( int val ) { addAtIndex ( cnt , val ); } public void addAtIndex ( int index , int val ) { if ( index > cnt ) { return ; } var pre = dummy ; while ( index -- > 0 ) { pre = pre . next ; } pre . next = new ListNode ( val , pre . next ); ++ cnt ; } public void deleteAtIndex ( int index ) { if ( index < 0 || index >= cnt ) { return ; } var pre = dummy ; while ( index -- > 0 ) { pre = pre . next ; } var t = pre . next ; pre . next = t . next ; t . next = null ; -- cnt ; } } /** * Your MyLinkedList object will be instantiated and called as such: * MyLinkedList obj = new MyLinkedList(); * int param_1 = obj.get(index); * obj.addAtHead(val); * obj.addAtTail(val); * obj.addAtIndex(index,val); * obj.deleteAtIndex(index); */

1class MyLinkedList { private: ListNode * dummy = new ListNode (); int cnt = 0 ; public: MyLinkedList () { } int get ( int index ) { if ( index < 0 || index >= cnt ) { return - 1 ; } auto cur = dummy -> next ; while ( index -- ) { cur = cur -> next ; } return cur -> val ; } void addAtHead ( int val ) { addAtIndex ( 0 , val ); } void addAtTail ( int val ) { addAtIndex ( cnt , val ); } void addAtIndex ( int index , int val ) { if ( index > cnt ) { return ; } auto pre = dummy ; while ( index -- > 0 ) { pre = pre -> next ; } pre -> next = new ListNode ( val , pre -> next ); ++ cnt ; } void deleteAtIndex ( int index ) { if ( index >= cnt ) { return ; } auto pre = dummy ; while ( index -- > 0 ) { pre = pre -> next ; } auto t = pre -> next ; pre -> next = t -> next ; t -> next = nullptr ; -- cnt ; } }; /** * Your MyLinkedList object will be instantiated and called as such: * MyLinkedList* obj = new MyLinkedList(); * int param_1 = obj->get(index); * obj->addAtHead(val); * obj->addAtTail(val); * obj->addAtIndex(index,val); * obj->deleteAtIndex(index); */

1# doubly linked node class ListNode : def __init__ ( self , value = 0 , prev = None , next = None ): self . value = value self . prev = prev self . next = next class MyLinkedList : def __init__ ( self ): self . head = ListNode ( 0 ) # Sentinel node as pseudo-head self . tail = ListNode ( 0 ) # Sentinel node as pseudo-tail self . head . next = self . tail self . tail . prev = self . head self . size = 0 def get ( self , index : int ) -> int : if index < 0 or index >= self . size : return - 1 if index + 1 < self . size - index : # decide start from head or tail curr = self . head for _ in range ( index + 1 ): curr = curr . next else : curr = self . tail for _ in range ( self . size - index ): curr = curr . prev return curr . value def addAtHead ( self , val : int ) -> None : pred , succ = self . head , self . head . next self . size += 1 to_add = ListNode ( val , pred , succ ) pred . next = to_add succ . prev = to_add def addAtTail ( self , val : int ) -> None : succ , pred = self . tail , self . tail . prev self . size += 1 to_add = ListNode ( val , pred , succ ) pred . next = to_add succ . prev = to_add def addAtIndex ( self , index : int , val : int ) -> None : if index > self . size : return if index < 0 : index = 0 if index < self . size - index : # decide start from head or tail pred = self . head for _ in range ( index ): pred = pred . next succ = pred . next else : succ = self . tail for _ in range ( self . size - index ): succ = succ . prev pred = succ . prev self . size += 1 to_add = ListNode ( val , pred , succ ) pred . next = to_add succ . prev = to_add def deleteAtIndex ( self , index : int ) -> None : if index < 0 or index >= self . size : return if index < self . size - index : pred = self . head for _ in range ( index ): pred = pred . next succ = pred . next . next else : succ = self . tail for _ in range ( self . size - index - 1 ): succ = succ . prev pred = succ . prev . prev self . size -= 1 pred . next = succ succ . prev = pred # Your MyLinkedList object will be instantiated and called as such: # obj = MyLinkedList() # param_1 = obj.get(index) # obj.addAtHead(val) # obj.addAtTail(val) # obj.addAtIndex(index,val) # obj.deleteAtIndex(index) ####################### # singly linked node class MyLinkedList : def __init__ ( self ): self . dummy = ListNode () self . cnt = 0 def get ( self , index : int ) -> int : if index < 0 or index >= self . cnt : return - 1 cur = self . dummy . next for _ in range ( index ): cur = cur . next return cur . val def addAtHead ( self , val : int ) -> None : self . addAtIndex ( 0 , val ) def addAtTail ( self , val : int ) -> None : self . addAtIndex ( self . cnt , val ) def addAtIndex ( self , index : int , val : int ) -> None : if index > self . cnt : return pre = self . dummy for _ in range ( index ): pre = pre . next pre . next = ListNode ( val , pre . next ) # insert in-between self . cnt += 1 def deleteAtIndex ( self , index : int ) -> None : if index >= self . cnt : return pre = self . dummy for _ in range ( index ): pre = pre . next t = pre . next pre . next = t . next t . next = None # don't forget to cutoff self . cnt -= 1 # Your MyLinkedList object will be instantiated and called as such: # obj = MyLinkedList() # param_1 = obj.get(index) # obj.addAtHead(val) # obj.addAtTail(val) # obj.addAtIndex(index,val) # obj.deleteAtIndex(index)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem