Design Linked List

Medium

Asked by:

17 views

Topics:

Linked Lists

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 index^th 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 index^th 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 index^th 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 <= 1000
Please do not use the built-in LinkedList library.
At most 2000 calls will be made to get, addAtHead, addAtTail, addAtIndex and deleteAtIndex.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of possible values for the nodes in the linked list?
Will there be a large number of calls to the `get` operation, potentially requiring optimization?
What should I return if I try to access an index that is out of bounds (e.g., `get` with an invalid index)? Should I return `null`, throw an exception, or something else?
Are we implementing a singly linked list or a doubly linked list?
For the `addAtHead` and `addAtTail` operations, what happens if the provided value is `null` or invalid? Should I handle such cases?

Brute Force Solution

Approach

The brute force approach to creating a linked list involves manually managing each connection. It's like physically linking paperclips together, one by one, to form a chain. We directly manipulate the links to add, remove, or find specific paperclips.

Here's how the algorithm would work step-by-step:

To start, imagine you have no paperclips linked together yet. This is an empty list.
When asked to add a new paperclip (a new value) at the front, just grab that paperclip and make it the first in the chain.
When asked to add a paperclip to the end, you must follow the chain from the first paperclip, one at a time, until you reach the last one. Then, connect the new paperclip to the end of that last one.
When asked to add a paperclip at a specific spot, you would start from the beginning and manually follow the links to get to the spot before the place you want to add the new one. Then you would connect the new paperclip in that spot, re-arranging the links.
When asked to remove a paperclip, you start from the beginning and follow the chain until you find the paperclip you want to remove. Then you disconnect it by re-arranging the links to bypass it.
When asked to find the value of a paperclip at a specific spot, you start from the beginning and count your way along the chain until you reach the correct spot. Then you simply tell the value of that paperclip.

Code Implementation

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class MyLinkedList:

    def __init__(self):
        self.head = None
        self.size_of_linked_list = 0

    def get(self, index: int) -> int:
        if index < 0 or index >= self.size_of_linked_list:
            return -1
        
        current_node = self.head
        for _ in range(index):
            current_node = current_node.next
        return current_node.value

    def addAtHead(self, value: int) -> None:
        new_node = Node(value)
        new_node.next = self.head
        self.head = new_node
        self.size_of_linked_list += 1

    def addAtTail(self, value: int) -> None:
        new_node = Node(value)
        
        # Handle empty list case
        if not self.head:
            self.head = new_node
            self.size_of_linked_list += 1
            return

        current_node = self.head
        while current_node.next:
            current_node = current_node.next
        current_node.next = new_node
        self.size_of_linked_list += 1

    def addAtIndex(self, index: int, value: int) -> None:
        if index < 0 or index > self.size_of_linked_list:
            return

        if index == 0:
            self.addAtHead(value)
            return

        new_node = Node(value)
        current_node = self.head
        
        # Traverse up to node before target index
        for _ in range(index - 1):
            current_node = current_node.next

        new_node.next = current_node.next
        current_node.next = new_node
        self.size_of_linked_list += 1

    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.size_of_linked_list:
            return

        # Handle deleting head node
        if index == 0:
            self.head = self.head.next
            self.size_of_linked_list -= 1
            return

        current_node = self.head
        # Traverse to the node BEFORE the one to delete
        for _ in range(index - 1):
            current_node = current_node.next

        # Correct the pointers to remove the node
        current_node.next = current_node.next.next
        self.size_of_linked_list -= 1

Big(O) Analysis

Time Complexity

O(n) – Adding a node at the head takes constant time, O(1). Adding a node at the tail or at a specific index requires traversing the list from the head to the specified position, which can take up to n steps in the worst case, where n is the number of nodes in the list. Similarly, removing a node at a specific index also requires traversing the list to find the node, resulting in O(n) time complexity. Getting the value at a specific index also needs traversal, making it an O(n) operation in the worst case when the index is near the end. Therefore, the dominant operations are those that potentially require traversing the entire list, leading to an overall time complexity of O(n).

Space Complexity

O(N) – The design linked list implementation stores each added value in a new node. In the worst case, if we add N values to the linked list, we will create N nodes. Each node consumes a constant amount of memory. Therefore, the auxiliary space required grows linearly with the number of values stored in the list, where N represents the number of values added to the list.

Optimal Solution

Approach

We will create a custom list data structure. This involves defining a way to link items together, and then providing operations to add, remove, and retrieve items from that list, while keeping track of the list's connections.

Here's how the algorithm would work step-by-step:

First, create a blueprint for each item in the list. Each item will hold some data and also a pointer to the next item.
Then, set up the list itself. The list needs to remember the first item and the last item, so we can quickly add to the beginning or end.
To add an item at the beginning, create the new item, make it point to the old first item, and then update the list to remember the new item as the first one.
To add an item at the end, create the new item, make the old last item point to it, and then update the list to remember the new item as the last one.
To add an item at a specific spot, go to the item right before that spot. Change the next pointer of that item to point to the new item. The new item's next pointer should point to the item that originally came after.
To remove an item, find the item right before the one you want to remove. Make its next pointer point to the item that comes after the one you're removing, effectively skipping over it. If you're removing the first item, update the list to remember the second item as the new first item.
To get an item at a certain location, start from the first item and follow the next pointers until you reach the desired location.

Code Implementation

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class MyLinkedList:

    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def get(self, index: int) -> int:
        if index < 0 or index >= self.size:
            return -1

        current_node = self.head
        for _ in range(index):
            current_node = current_node.next
        return current_node.value

    def addAtHead(self, value: int) -> None:
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head = new_node

        self.size += 1

    def addAtTail(self, value: int) -> None:
        new_node = Node(value)
        if self.tail is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node

        self.size += 1

    def addAtIndex(self, index: int, value: int) -> None:
        if index < 0 or index > self.size:
            return

        if index == 0:
            self.addAtHead(value)
            return

        if index == self.size:
            self.addAtTail(value)
            return

        new_node = Node(value)
        current_node = self.head
        for _ in range(index - 1):
            current_node = current_node.next

        # Insert the new node in the linked list
        new_node.next = current_node.next
        current_node.next = new_node
        self.size += 1

    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.size:
            return

        if index == 0:
            # Handle deleting the head
            self.head = self.head.next
            if self.head is None:
                self.tail = None
            self.size -= 1
            return

        current_node = self.head
        for _ in range(index - 1):
            current_node = current_node.next

        # Handle deleting the last node
        if current_node.next == self.tail:
            current_node.next = None
            self.tail = current_node
        else:
            current_node.next = current_node.next.next

        self.size -= 1

Big(O) Analysis

Time Complexity

O(n) – Adding at the beginning and end of the list involves constant time operations. However, inserting or deleting at a specific index requires traversing the list from the head to reach the desired position. In the worst-case scenario, we might need to traverse almost the entire list of n elements to reach the index. Getting an element at a specific index also requires traversal, taking up to n steps. Therefore, operations involving indexing have a time complexity of O(n).

Space Complexity

O(1) – The algorithm's space complexity is O(1) because it primarily manipulates pointers within the linked list structure. While adding or removing nodes, only a few extra variables are used to store the new node and potentially a previous node. These variables occupy a constant amount of space, irrespective of the number of nodes (N) in the linked list, meaning the space usage does not scale with the input size.

Edge Cases

Case	How to Handle
Adding to the head of an empty list	The head and tail pointers should both point to the new node
Adding to the tail of an empty list	The head and tail pointers should both point to the new node
Deleting the only element in the list	The head and tail pointers should both be set to null
Deleting the head element	The head pointer should be updated to the next node, and previous head's next pointer must be set to null
Deleting the tail element	The tail pointer should be updated to the previous node, and previous tail's previous pointer must be set to null
Deleting an element in the middle of the list	The previous node's next pointer and the next node's previous pointer should point to each other, bypassing the deleted node
Index out of bounds for get, addAtIndex, deleteAtIndex	Return -1 for get, do nothing for addAtIndex and deleteAtIndex if index is out of bounds
Integer overflow when calculating list size or index	Ensure list size is tracked with appropriate data type, and index calculations avoid overflow

Adding to the head of an empty list

How to Handle:

The head and tail pointers should both point to the new node

Adding to the tail of an empty list

How to Handle:

The head and tail pointers should both point to the new node

Deleting the only element in the list

How to Handle:

The head and tail pointers should both be set to null

Deleting the head element

How to Handle:

The head pointer should be updated to the next node, and previous head's next pointer must be set to null

Deleting the tail element

How to Handle:

The tail pointer should be updated to the previous node, and previous tail's previous pointer must be set to null

Deleting an element in the middle of the list

How to Handle:

The previous node's next pointer and the next node's previous pointer should point to each other, bypassing the deleted node

Index out of bounds for get, addAtIndex, deleteAtIndex

How to Handle:

Return -1 for get, do nothing for addAtIndex and deleteAtIndex if index is out of bounds

Integer overflow when calculating list size or index

How to Handle:

Ensure list size is tracked with appropriate data type, and index calculations avoid overflow