Design Linked List
Problem Description
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 theMyLinkedListobject.int get(int index)Get the value of theindexthnode in the linked list. If the index is invalid, return-1.void addAtHead(int val)Add a node of valuevalbefore 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 valuevalas the last element of the linked list.void addAtIndex(int index, int val)Add a node of valuevalbefore theindexthnode in the linked list. Ifindexequals the length of the linked list, the node will be appended to the end of the linked list. Ifindexis greater than the length, the node will not be inserted.void deleteAtIndex(int index)Delete theindexthnode 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
Constraints:
0 <= index, val <= 1000- Please do not use the built-in LinkedList library.
- At most
2000calls will be made toget,addAtHead,addAtTail,addAtIndexanddeleteAtIndex.
Solve it on LeetCode
Approaches
1. Singly Linked List
Intuition:
A singly linked list is a data structure that consists of a sequence of elements, where each element points to the next one. The basic operations include adding an element, removing an element, and retrieving an element at a specific index. The singly linked list is efficient for insertion and deletion operations as it doesn't require shifting elements like an array does. The challenge is to efficiently handle edge cases such as indexing beyond the bounds of the list.
Approach:
For a singly linked list:
- Maintain a
ListNodeclass with properties for the value and a pointer to the next node. - Keep track of the head of the list and the size to manage insertion and deletion at specific points.
- The add operation involves traversing to the desired index and adjusting the pointers.
- The delete operation involves traversing and re-linking the list to skip the deleted node.
Code:
- Time Complexity:
O(n)for get, add, and delete operations as each requires traversal. - Space Complexity:
O(1)for each operation as we maintain a fixed number of references regardless of input size.
2. Doubly Linked List
Intuition:
The doubly linked list extends the singly linked list by adding a previous pointer to each node. This allows for efficient bidirectional traversal. It helps improve the deletion operation by providing direct access to the previous node, thereby avoiding full traversal for backtracking operations.
Approach:
For a doubly linked list:
- Extend the node definition to include pointers to both previous and next nodes.
- Maintain both head and tail pointers to easily add elements to both ends.
- Update operations (add, delete) ensure that previous pointers are maintained along with next pointers.
Code:
- Time Complexity:
O(n)for get, add, and delete operations. The selection between forward or backward traversal provides a slight optimization. - Space Complexity:
O(1)for each operation; each node holds additional reference, but overall the space is linear with the number of elements.