DSA problem
Design Linked List
Design your own implementation of a linked list. You may choose a singly or doubly linked list. A node in a singly linked list stores a value and a pointer to the next node; in a doubly linked list it also stores a pointer to the previous node. Assume all node values are non-negative integers and the list is 0-indexed.
Your MyLinkedList class must support these operations: get(index) returns the value of the index-th node, or -1 if the index is invalid; addAtHead(val) inserts a node at the front; addAtTail(val) appends a node at the end; addAtIndex(index, val) inserts before the index-th node (if index equals the length it appends, and if index exceeds the length nothing happens); and deleteAtIndex(index) removes the index-th node if the index is valid.
The central challenge is correct index bookkeeping at the boundaries: head, tail, the empty list, and out-of-range indices. A robust trick is to maintain a size counter and a sentinel (dummy) head node. The sentinel guarantees that every insertion or deletion, even at index 0, is handled by the same generic logic of locating the predecessor node.
The optimal design walks from the sentinel exactly index steps to reach the node just before the target position, then performs a constant-time pointer rewire. Each operation therefore costs O(index) time, bounded by O(n), and the structure uses O(1) extra space per call beyond the nodes themselves.
Examples
["MyLinkedList","addAtHead","addAtTail","addAtIndex","get","deleteAtIndex","get"]\n[[],[1],[3],[1,2],[1],[1],[1]][null,null,null,null,2,null,3]["MyLinkedList","addAtIndex","get"]\n[[],[0,10],[0]][null,null,10]["MyLinkedList","get","deleteAtIndex"]\n[[],[0],[0]][null,-1,null]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.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.