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 <= 10002000 calls will be made to get, addAtHead, addAtTail, addAtIndex and deleteAtIndex.In #707 Design Linked List, you must implement a linked list from scratch and support operations such as get, addAtHead, addAtTail, addAtIndex, and deleteAtIndex. The key idea is to manage node connections efficiently while tracking the current size of the list.
A common approach is to build a doubly linked list with sentinel (dummy) head and tail nodes. These dummy nodes simplify edge cases when inserting or deleting at the beginning or end. Each node stores its value and pointers to the previous and next nodes. When performing operations at an index, traverse from the head (or tail if optimized) until reaching the desired position.
Maintaining a size variable helps quickly validate indices and avoid unnecessary traversal. Most updates like adding at head or tail can be done in constant time, while operations involving arbitrary indices require traversal.
The overall design emphasizes clean pointer manipulation and careful boundary handling to maintain correct list structure.
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Get by Index | O(n) | O(1) |
| Add at Head / Tail | O(1) | O(1) |
| Add at Index | O(n) | O(1) |
| Delete at Index | O(n) | O(1) |
Ashish Pratap Singh
In this approach, you will design a singly linked list where each node has a value and a pointer to the next node. This type of list is simple and efficient for certain operations, especially when traversing only forwards is sufficient.
Time Complexity:
- get: O(n)
- addAtHead: O(1)
- addAtTail: O(n)
- addAtIndex: O(n)
- deleteAtIndex: O(n)
Space Complexity: O(n), where n is the number of nodes in the list.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct Node {
5 int val;
6 struct Node*
The above code implements a singly linked list in C. It provides functions to add nodes at the head, tail, a specific index, get the value at an index, and delete a node at an index. The linked list maintains a head pointer and nodes are dynamically allocated using malloc.
This approach designs a doubly linked list, allowing traversal both forwards and backwards. Each node maintains a reference to both the next and previous node, facilitating operations such as adding or removing nodes from either end more efficiently.
Time Complexity:
- get: O(n)
- addAtHead: O(1)
- addAtTail: O(n)
- addAtIndex: O(n)
- deleteAtIndex: O(n)
Space Complexity: O(n), where n is the number of nodes in the list.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Dummy or sentinel nodes help avoid special cases when inserting or deleting at the beginning or end of the list. They provide stable boundary nodes so pointer updates become consistent across all operations.
Yes, linked list design and manipulation problems are common in FAANG-style interviews. They test understanding of pointers, data structure implementation, and handling edge cases in low-level operations.
A doubly linked list is usually the best structure for this problem because it allows efficient insertion and deletion with access to both previous and next nodes. Dummy nodes further simplify operations at the head and tail.
The optimal approach is to implement a doubly linked list with sentinel head and tail nodes. This design simplifies insertion and deletion at boundaries and reduces edge-case handling. Maintaining a size variable also helps validate indices efficiently.
The C implementation of a doubly linked list adds a prev pointer to each node, enabling two-way node traversal and efficient deletion and insertion operations from both ends.