LeetCode Solutions Blog

Design Linked List

Number: 838

Difficulty: Medium

Paid? No

Problem Description

Design a linked list data structure that supports operations to get an element by index, add elements at the head, tail, or a specific index, and delete an element at a specified index. The list can be implemented as either singly or doubly linked.

Key Insights

Use a dummy head node to simplify insertion and deletion at the head.
Maintain a size counter to quickly validate index-based operations.
For every operation, traverse the list up to the required point since random access is not available.
Ensure robustness by handling edge cases like negative indices and indices larger than the current length.

Space and Time Complexity

Time Complexity:

get, addAtIndex, and deleteAtIndex operations require O(n) time due to the need to traverse the list.
addAtHead and addAtTail (if tail pointer is not maintained) are O(n) in worst case; however, these can be optimized further if a tail pointer is added.

Space Complexity:

O(n) space for storing n nodes.

Solution

The solution employs a singly linked list with a dummy head node to ease edge-case handling. A size counter is maintained for quick index validations. Each node holds a value and a pointer to the next node. Operations operate by traversing the list to the correct insertion or deletion point. This design makes it simple to add the functionality of getting values, inserting at specified indices, and removing nodes.

Code Solutions

# Define a node for the singly linked list
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val   # The value of the node
        self.next = next # Pointer to the next node

class MyLinkedList:
    def __init__(self):
        # Initialize size and a dummy head node to simplify operations
        self.size = 0
        self.head = ListNode(0)  # dummy head

    def get(self, index: int) -> int:
        # If index is out of bounds, return -1
        if index < 0 or index >= self.size:
            return -1
        current = self.head.next  # start from the actual head
        for _ in range(index):
            current = current.next
        return current.val

    def addAtHead(self, val: int) -> None:
        self.addAtIndex(0, val)  # add at index 0

    def addAtTail(self, val: int) -> None:
        self.addAtIndex(self.size, val)  # add at the end

    def addAtIndex(self, index: int, val: int) -> None:
        # Normalize negative index to 0 (insert at head)
        if index < 0:
            index = 0
        # Only insert if index is valid (<= size)
        if index > self.size:
            return
        self.size += 1
        # Start from the dummy head node
        pred = self.head
        for _ in range(index):
            pred = pred.next
        # Insert new node
        new_node = ListNode(val)
        new_node.next = pred.next
        pred.next = new_node

    def deleteAtIndex(self, index: int) -> None:
        # If index is out of bounds, do nothing
        if index < 0 or index >= self.size:
            return
        self.size -= 1
        pred = self.head
        for _ in range(index):
            pred = pred.next
        # Remove the node by skipping it
        pred.next = pred.next.next