Design Linked List
Medium · Linked Lists · Linked List · Design
Problem
Build your own linked list, singly or doubly linked, without a built-in list library. Indices are 0-based. Implement MyLinkedList:
- MyLinkedList() creates an empty list.
- int get(int index) returns the value at index, or -1 if the index is not valid.
- void addAtHead(int val) inserts val before the first element; it becomes the new first element.
- void addAtTail(int val) appends val after the last element.
- void addAtIndex(int index, int val) inserts val so that it ends up at position index. If index equals the length, the value is appended. If index is greater than the length, nothing happens.
- void deleteAtIndex(int index) removes the element at index if the index is valid; otherwise nothing happens.
The tests call the class through a list of operation names and a list of their arguments; each call's return value is collected, with None for the constructor and the void methods.
Examples
Input: ops = ["MyLinkedList","addAtTail","addAtHead","addAtIndex","get","deleteAtIndex","get","addAtIndex","get"], args = [[],[5],[2],[1,9],[2],[0],[0],[5,1],[2]] Output: [None, None, None, None, 5, None, 9, None, -1]
The list goes [5], [2,5], [2,9,5]; deleting index 0 leaves [9,5]; inserting at index 5 is ignored, so index 2 is out of range.
Input: ops = ["MyLinkedList","addAtIndex","get","deleteAtIndex","get"], args = [[],[0,4],[0],[3],[1]] Output: [None, None, 4, None, -1]
Inserting at index 0 of an empty list is allowed; deleting the invalid index 3 does nothing, and index 1 does not exist.
Input: ops = ["MyLinkedList","addAtHead","addAtTail","addAtIndex","get","deleteAtIndex","get"], args = [[],[1],[3],[2,4],[2],[1],[1]] Output: [None, None, None, None, 4, None, 4]
Index 2 equals the length of [1,3], so 4 is appended; deleting index 1 then leaves [1,4].
Constraints
- 0 <= index, val <= 1000
- At most 2000 calls are made in total
- Do not use a built-in linked list library
Approaches
- Baseline: singly linked list with a sentinel — time O(i) per call, space O(n)
Follow-up
Every operation here is O(index) because finding a position means walking to it. A skip list adds express lanes over the nodes and brings index lookups down to O(log n) on average; a balanced tree keyed by subtree size (an order-statistic tree, or a rope) does it in O(log n) worst case. When most work happens at the two ends, a doubly linked list with both sentinels already gives O(1) for those.
Related problems
Start free on Cariara · Coding problems · System design studio
