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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

**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.

Solution

Method 1 – Doubly Linked List with Dummy Head and Tail

Intuition

A doubly linked list with dummy head and tail nodes simplifies edge cases for insertions and deletions at the head and tail. We maintain a size variable for O(1) length checks and index validation.

Approach

  1. Define a doubly linked list node with val, prev, and next.
  2. Use dummy head and tail nodes to avoid null checks for head/tail operations.
  3. Maintain a size variable to track the number of elements.
  4. For get(index), traverse from head or tail depending on which is closer.
  5. For addAtHead(val), insert after dummy head.
  6. For addAtTail(val), insert before dummy tail.
  7. For addAtIndex(index, val), insert at the correct position if index is valid.
  8. For deleteAtIndex(index), remove the node at the index if valid.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

class MyLinkedList {
    struct Node {
        int val;
        Node *prev, *next;
        Node(int v) : val(v), prev(nullptr), next(nullptr) {}
    } *head, *tail;
    int sz;
public:
    MyLinkedList() {
        head = new Node(0);
        tail = new Node(0);
        head->next = tail;
        tail->prev = head;
        sz = 0;
    }
    int get(int idx) {
        if (idx < 0 || idx >= sz) return -1;
        Node* cur;
        if (idx + 1 < sz - idx) {
            cur = head->next;
            for (int i = 0; i < idx; ++i) cur = cur->next;
        } else {
            cur = tail;
            for (int i = 0; i < sz - idx; ++i) cur = cur->prev;
        }
        return cur->val;
    }
    void addAtHead(int val) {
        Node* n = new Node(val);
        n->next = head->next;
        n->prev = head;
        head->next->prev = n;
        head->next = n;
        sz++;
    }
    void addAtTail(int val) {
        Node* n = new Node(val);
        n->prev = tail->prev;
        n->next = tail;
        tail->prev->next = n;
        tail->prev = n;
        sz++;
    }
    void addAtIndex(int idx, int val) {
        if (idx < 0 || idx > sz) return;
        Node* cur;
        if (idx < sz - idx) {
            cur = head;
            for (int i = 0; i < idx; ++i) cur = cur->next;
        } else {
            cur = tail;
            for (int i = 0; i < sz - idx + 1; ++i) cur = cur->prev;
        }
        Node* n = new Node(val);
        n->next = cur->next;
        n->prev = cur;
        cur->next->prev = n;
        cur->next = n;
        sz++;
    }
    void deleteAtIndex(int idx) {
        if (idx < 0 || idx >= sz) return;
        Node* cur;
        if (idx < sz - idx) {
            cur = head;
            for (int i = 0; i < idx; ++i) cur = cur->next;
        } else {
            cur = tail;
            for (int i = 0; i < sz - idx; ++i) cur = cur->prev;
        }
        Node* toDel = cur->next;
        cur->next = toDel->next;
        toDel->next->prev = cur;
        delete toDel;
        sz--;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

type Node struct {
    val  int
    prev *Node
    next *Node
}
type MyLinkedList struct {
    head, tail *Node
    sz int
}
func Constructor() MyLinkedList {
    head := &Node{}
    tail := &Node{}
    head.next = tail
    tail.prev = head
    return MyLinkedList{head, tail, 0}
}
func (l *MyLinkedList) Get(idx int) int {
    if idx < 0 || idx >= l.sz {
        return -1
    }
    var cur *Node
    if idx+1 < l.sz-idx {
        cur = l.head.next
        for i := 0; i < idx; i++ {
            cur = cur.next
        }
    } else {
        cur = l.tail
        for i := 0; i < l.sz-idx; i++ {
            cur = cur.prev
        }
    }
    return cur.val
}
func (l *MyLinkedList) AddAtHead(val int) {
    n := &Node{val: val}
    n.next = l.head.next
    n.prev = l.head
    l.head.next.prev = n
    l.head.next = n
    l.sz++
}
func (l *MyLinkedList) AddAtTail(val int) {
    n := &Node{val: val}
    n.prev = l.tail.prev
    n.next = l.tail
    l.tail.prev.next = n
    l.tail.prev = n
    l.sz++
}
func (l *MyLinkedList) AddAtIndex(idx, val int) {
    if idx < 0 || idx > l.sz {
        return
    }
    var cur *Node
    if idx < l.sz-idx {
        cur = l.head
        for i := 0; i < idx; i++ {
            cur = cur.next
        }
    } else {
        cur = l.tail
        for i := 0; i < l.sz-idx+1; i++ {
            cur = cur.prev
        }
    }
    n := &Node{val: val}
    n.next = cur.next
    n.prev = cur
    cur.next.prev = n
    cur.next = n
    l.sz++
}
func (l *MyLinkedList) DeleteAtIndex(idx int) {
    if idx < 0 || idx >= l.sz {
        return
    }
    var cur *Node
    if idx < l.sz-idx {
        cur = l.head
        for i := 0; i < idx; i++ {
            cur = cur.next
        }
    } else {
        cur = l.tail
        for i := 0; i < l.sz-idx; i++ {
            cur = cur.prev
        }
    }
    toDel := cur.next
    cur.next = toDel.next
    toDel.next.prev = cur
    l.sz--
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

public class MyLinkedList {
    class Node {
        int val;
        Node prev, next;
        Node(int v) { val = v; }
    }
    Node head, tail;
    int sz;
    public MyLinkedList() {
        head = new Node(0);
        tail = new Node(0);
        head.next = tail;
        tail.prev = head;
        sz = 0;
    }
    public int get(int idx) {
        if (idx < 0 || idx >= sz) return -1;
        Node cur;
        if (idx + 1 < sz - idx) {
            cur = head.next;
            for (int i = 0; i < idx; ++i) cur = cur.next;
        } else {
            cur = tail;
            for (int i = 0; i < sz - idx; ++i) cur = cur.prev;
        }
        return cur.val;
    }
    public void addAtHead(int val) {
        Node n = new Node(val);
        n.next = head.next;
        n.prev = head;
        head.next.prev = n;
        head.next = n;
        sz++;
    }
    public void addAtTail(int val) {
        Node n = new Node(val);
        n.prev = tail.prev;
        n.next = tail;
        tail.prev.next = n;
        tail.prev = n;
        sz++;
    }
    public void addAtIndex(int idx, int val) {
        if (idx < 0 || idx > sz) return;
        Node cur;
        if (idx < sz - idx) {
            cur = head;
            for (int i = 0; i < idx; ++i) cur = cur.next;
        } else {
            cur = tail;
            for (int i = 0; i < sz - idx + 1; ++i) cur = cur.prev;
        }
        Node n = new Node(val);
        n.next = cur.next;
        n.prev = cur;
        cur.next.prev = n;
        cur.next = n;
        sz++;
    }
    public void deleteAtIndex(int idx) {
        if (idx < 0 || idx >= sz) return;
        Node cur;
        if (idx < sz - idx) {
            cur = head;
            for (int i = 0; i < idx; ++i) cur = cur.next;
        } else {
            cur = tail;
            for (int i = 0; i < sz - idx; ++i) cur = cur.prev;
        }
        Node toDel = cur.next;
        cur.next = toDel.next;
        toDel.next.prev = cur;
        sz--;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

class MyLinkedList {
    class Node(var v: Int) {
        var prev: Node? = null
        var next: Node? = null
    }
    private val head = Node(0)
    private val tail = Node(0)
    private var sz = 0
    init {
        head.next = tail
        tail.prev = head
    }
    fun get(idx: Int): Int {
        if (idx < 0 || idx >= sz) return -1
        var cur: Node?
        if (idx + 1 < sz - idx) {
            cur = head.next
            repeat(idx) { cur = cur?.next }
        } else {
            cur = tail
            repeat(sz - idx) { cur = cur?.prev }
        }
        return cur?.v ?: -1
    }
    fun addAtHead(v: Int) {
        val n = Node(v)
        n.next = head.next
        n.prev = head
        head.next?.prev = n
        head.next = n
        sz++
    }
    fun addAtTail(v: Int) {
        val n = Node(v)
        n.prev = tail.prev
        n.next = tail
        tail.prev?.next = n
        tail.prev = n
        sz++
    }
    fun addAtIndex(idx: Int, v: Int) {
        if (idx < 0 || idx > sz) return
        var cur: Node?
        if (idx < sz - idx) {
            cur = head
            repeat(idx) { cur = cur?.next }
        } else {
            cur = tail
            repeat(sz - idx + 1) { cur = cur?.prev }
        }
        val n = Node(v)
        n.next = cur?.next
        n.prev = cur
        cur?.next?.prev = n
        cur?.next = n
        sz++
    }
    fun deleteAtIndex(idx: Int) {
        if (idx < 0 || idx >= sz) return
        var cur: Node?
        if (idx < sz - idx) {
            cur = head
            repeat(idx) { cur = cur?.next }
        } else {
            cur = tail
            repeat(sz - idx) { cur = cur?.prev }
        }
        val toDel = cur?.next
        cur?.next = toDel?.next
        toDel?.next?.prev = cur
        sz--
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

class Node:
    def __init__(self, v: int):
        self.v = v
        self.prev: Node | None = None
        self.next: Node | None = None
class MyLinkedList:
    def __init__(self):
        self.head = Node(0)
        self.tail = Node(0)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.sz = 0
    def get(self, idx: int) -> int:
        if idx < 0 or idx >= self.sz:
            return -1
        if idx + 1 < self.sz - idx:
            cur = self.head.next
            for _ in range(idx):
                cur = cur.next
        else:
            cur = self.tail
            for _ in range(self.sz - idx):
                cur = cur.prev
        return cur.v
    def addAtHead(self, v: int) -> None:
        n = Node(v)
        n.next = self.head.next
        n.prev = self.head
        self.head.next.prev = n
        self.head.next = n
        self.sz += 1
    def addAtTail(self, v: int) -> None:
        n = Node(v)
        n.prev = self.tail.prev
        n.next = self.tail
        self.tail.prev.next = n
        self.tail.prev = n
        self.sz += 1
    def addAtIndex(self, idx: int, v: int) -> None:
        if idx < 0 or idx > self.sz:
            return
        if idx < self.sz - idx:
            cur = self.head
            for _ in range(idx):
                cur = cur.next
        else:
            cur = self.tail
            for _ in range(self.sz - idx + 1):
                cur = cur.prev
        n = Node(v)
        n.next = cur.next
        n.prev = cur
        cur.next.prev = n
        cur.next = n
        self.sz += 1
    def deleteAtIndex(self, idx: int) -> None:
        if idx < 0 or idx >= self.sz:
            return
        if idx < self.sz - idx:
            cur = self.head
            for _ in range(idx):
                cur = cur.next
        else:
            cur = self.tail
            for _ in range(self.sz - idx):
                cur = cur.prev
        toDel = cur.next
        cur.next = toDel.next
        toDel.next.prev = cur
        self.sz -= 1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

struct Node {
    v: i32,
    prev: Option<*mut Node>,
    next: Option<*mut Node>,
}
struct MyLinkedList {
    head: *mut Node,
    tail: *mut Node,
    sz: usize,
}
// Rust implementation would use unsafe pointers for doubly linked list.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

class Node {
    v: number;
    prev: Node | null = null;
    next: Node | null = null;
    constructor(v: number) { this.v = v; }
}
class MyLinkedList {
    private head = new Node(0);
    private tail = new Node(0);
    private sz = 0;
    constructor() {
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }
    get(idx: number): number {
        if (idx < 0 || idx >= this.sz) return -1;
        let cur: Node;
        if (idx + 1 < this.sz - idx) {
            cur = this.head.next!;
            for (let i = 0; i < idx; ++i) cur = cur.next!;
        } else {
            cur = this.tail;
            for (let i = 0; i < this.sz - idx; ++i) cur = cur.prev!;
        }
        return cur.v;
    }
    addAtHead(v: number): void {
        const n = new Node(v);
        n.next = this.head.next;
        n.prev = this.head;
        this.head.next!.prev = n;
        this.head.next = n;
        this.sz++;
    }
    addAtTail(v: number): void {
        const n = new Node(v);
        n.prev = this.tail.prev;
        n.next = this.tail;
        this.tail.prev!.next = n;
        this.tail.prev = n;
        this.sz++;
    }
    addAtIndex(idx: number, v: number): void {
        if (idx < 0 || idx > this.sz) return;
        let cur: Node;
        if (idx < this.sz - idx) {
            cur = this.head;
            for (let i = 0; i < idx; ++i) cur = cur.next!;
        } else {
            cur = this.tail;
            for (let i = 0; i < this.sz - idx + 1; ++i) cur = cur.prev!;
        }
        const n = new Node(v);
        n.next = cur.next;
        n.prev = cur;
        cur.next!.prev = n;
        cur.next = n;
        this.sz++;
    }
    deleteAtIndex(idx: number): void {
        if (idx < 0 || idx >= this.sz) return;
        let cur: Node;
        if (idx < this.sz - idx) {
            cur = this.head;
            for (let i = 0; i < idx; ++i) cur = cur.next!;
        } else {
            cur = this.tail;
            for (let i = 0; i < this.sz - idx; ++i) cur = cur.prev!;
        }
        const toDel = cur.next!;
        cur.next = toDel.next;
        toDel.next!.prev = cur;
        this.sz--;
    }
}

Complexity

  • ⏰ Time complexity: O(min(k, n-k)) for get, add, and delete operations, where k is the index and n is the list size.
  • 🧺 Space complexity: O(n), where n is the number of nodes in the list.