# Design Linked List
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/design-linked-list)
Canonical: https://scaleengineer.com/dsa/problems/design-linked-list
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Algorithms:** [LRU Cache](https://scaleengineer.com/algorithms/lru-cache)
**Data structures:** Linked List
---
## Problem
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 `indexth` 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 `indexth` 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 `indexth` 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
## Singly Linked List
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.
**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.
**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.
### Explanation
```java
class MyLinkedList {
    class SinglyListNode {
        int val;
        SinglyListNode next;
        SinglyListNode(int val) {
            this.val = val;
        }
    }

    private int size;
    private SinglyListNode head; // Sentinel node

    /** Initialize your data structure here. */
    public MyLinkedList() {
        size = 0;
        head = new SinglyListNode(0); // Dummy head
    }

    /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
    public int get(int index) {
        if (index < 0 || index >= size) {
            return -1;
        }
        SinglyListNode curr = head.next;
        for (int i = 0; i < index; i++) {
            curr = curr.next;
        }
        return curr.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. */
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }

    /** Append a node of value val to the last element of the linked list. */
    public void addAtTail(int val) {
        addAtIndex(size, val);
    }

    /** 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. */
    public void addAtIndex(int index, int val) {
        if (index > size || index < 0) {
            return;
        }
        SinglyListNode pred = head;
        for (int i = 0; i < index; i++) {
            pred = pred.next;
        }
        SinglyListNode toAdd = new SinglyListNode(val);
        toAdd.next = pred.next;
        pred.next = toAdd;
        size++;
    }

    /** Delete the index-th node in the linked list, if the index is valid. */
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return;
        }
        SinglyListNode pred = head;
        for (int i = 0; i < index; i++) {
            pred = pred.next;
        }
        pred.next = pred.next.next;
        size--;
    }
}
```
### 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.

## Doubly Linked List with Sentinels
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.
**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.
**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.
### Explanation
```java
class MyLinkedList {
    class DoublyListNode {
        int val;
        DoublyListNode next, prev;
        DoublyListNode(int val) { this.val = val; }
    }

    private int size;
    private DoublyListNode head, tail; // Sentinel nodes

    public MyLinkedList() {
        size = 0;
        head = new DoublyListNode(0);
        tail = new DoublyListNode(0);
        head.next = tail;
        tail.prev = head;
    }

    // Helper to get the node at a specific index.
    private DoublyListNode getNode(int index) {
        DoublyListNode p;
        if (index < size / 2) {
            p = head.next;
            for (int i = 0; i < index; i++) {
                p = p.next;
            }
        } else {
            p = tail.prev;
            for (int i = 0; i < size - 1 - index; i++) {
                p = p.prev;
            }
        }
        return p;
    }

    public int get(int index) {
        if (index < 0 || index >= size) {
            return -1;
        }
        return getNode(index).val;
    }

    public void addAtHead(int val) {
        addAtIndex(0, val);
    }

    public void addAtTail(int val) {
        addAtIndex(size, val);
    }

    public void addAtIndex(int index, int val) {
        if (index < 0 || index > size) {
            return;
        }
        
        DoublyListNode pred, succ;
        if (index < size / 2) {
            pred = head;
            for (int i = 0; i < index; i++) {
                pred = pred.next;
            }
            succ = pred.next;
        } else {
            succ = tail;
            for (int i = 0; i < size - index; i++) {
                succ = succ.prev;
            }
            pred = succ.prev;
        }
        
        size++;
        DoublyListNode toAdd = new DoublyListNode(val);
        toAdd.prev = pred;
        toAdd.next = succ;
        pred.next = toAdd;
        succ.prev = toAdd;
    }

    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return;
        }
        
        DoublyListNode toDelete = getNode(index);
        toDelete.prev.next = toDelete.next;
        toDelete.next.prev = toDelete.prev;
        size--;
    }
}
```
### 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)).

# Solutions
### Java

```java
class 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); */
```

### CPP

```cpp
class 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); */
```

### Python

```python
# 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)
```