Design Linked List Leetcode Problem 707 [Python Solution]

In the world of data structures and algorithms, linked lists are a fundamental concept.

Linked lists are linear data structures where elements are connected via pointers.

In this blog post, we'll tackle the Design Linked List problem from LeetCode, specifically problem 707. We'll provide a Python solution that covers the essential aspects of designing a linked list, such as adding nodes at the head and tail, inserting nodes at specific positions, deleting nodes, and retrieving values.

Problem Overview

The problem statement is as follows:

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.

You are required to implement the MyLinkedList class, which includes the following methods:

1. MyLinkedList(): Initializes the MyLinkedList object.
2. get(index): Gets the value of the index-th node in the linked list.

If the index is invalid, return -1.
3. addAtHead(val): Adds 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.
4. addAtTail(val): Appends a node of value val as the last element of the linked list.
5. addAtIndex(index, val): Adds a node of value val before the index-th node in the linked list.

If the index equals the length of the linked list, the node will be appended to the end of the linked list.

If the index is greater than the length, the node will not be inserted.
6. deleteAtIndex(index): Deletes the index-th node in the linked list if the index is valid.

Constraints

Before we dive into the solution, let's understand the constraints of this problem:

• 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.

With these constraints in mind, let's proceed to design a Python solution for this problem.

Problem Overview

To create a linked list, we need to define a node class.

In our solution, we will implement a doubly linked list.

Each node will have three attributes: val (to store the value of the node), next (to point to the next node), and prev (to point to the previous node).

Next, we'll design the MyLinkedList class with the specified methods: MyLinkedList(), get(index), addAtHead(val), addAtTail(val), addAtIndex(index, val), and deleteAtIndex(index).

Let's go through each method's implementation step by step.

Understanding Constraints

Before we proceed with the code, it's important to understand the constraints:

• 0 <= index, val <= 1000: Values and indices are limited to a reasonable range.
• Please do not use the built-in LinkedList library: We need to implement our custom linked list.
• At most 2000 calls will be made to the provided methods: Our solution should be efficient and able to handle a large number of function calls.

MyLinkedList Python Code Solution

Let's start by implementing the MyLinkedList class and its methods.

We'll use the doubly linked list approach to cover all the required functionalities.

Here's the Python code for the solution:

class ListNode:
    def __init__(self, val):
        self.val = val
        self.prev = None
        self.next = None

class MyLinkedList:

    def __init__(self):
        self.left = ListNode(0)
        self.right = ListNode(0)
        self.left.next = self.right
        self.right.prev = self.left

    def get(self, index: int) -> int:
        cur = self.left.next
        while cur and index > 0:
            cur = cur.next
            index -= 1

        if cur and cur != self.right and index == 0:
            return cur.val
        return -1

    def addAtHead(self, val: int) -> None:
        node, prev, next = ListNode(val), self.left, self.left.next
        node.next, node.prev = next, prev
        next.prev = node
        prev.next = node

    def addAtTail(self, val: int) -> None:
        node, prev, next = ListNode(val), self.right.prev, self.right
        node.next, node.prev = next, prev
        next.prev = node
        prev.next = node

    def addAtIndex(self, index: int, val: int) -> None:
        next = self.left.next
        while next and index > 0:
            next = next.next
            index -= 1

        if next and index == 0:
            node, prev = ListNode(val), next.prev
            node.next, node.prev = next, prev
            next.prev = node
            prev.next = node

    def deleteAtIndex(self, index: int) -> None:
        node = self.left.next
        while node and index > 0:
            node = node.next
            index -= 1

        if node and node != self.right and index == 0:
            node.prev.next = node.next
            node.next.prev = node.prev

Time and Space Complexity

Now that we've provided a Python solution for the Design Linked List problem, let's analyze the time and space complexity of our implementation.

Time Complexity

1. MyLinkedList() – O(1): The constructor initializes the linked list with two dummy nodes.
2. get(index) – O(N): In the worst case, we iterate through the entire linked list to find the node at the given index.
3. addAtHead(val) – O(1): Adding a node at the head involves basic pointer manipulations and is a constant time operation.
4. addAtTail(val) – O(1): Adding a node at the tail is also a constant time operation.
5. addAtIndex(index, val) – O(N): In the worst case, we iterate through the list to find the position before which we want to insert a node.
6. deleteAtIndex(index) – O(N): Similar to addAtIndex, in the worst case, we iterate through the list to find the node to delete.

Space Complexity

The space complexity of our implementation is O(N), where N is the number of nodes in the linked list.

This space is used to store the nodes themselves, the pointers, and the dummy nodes.

Reasoning Behind Our Approach

Our solution uses a doubly linked list with two dummy nodes (left and right) to simplify operations and avoid edge cases

.

Here's a brief explanation of our approach:

1. Initialization: We create two dummy nodes (left and right) and connect them to represent the beginning and end of the linked list.

This eliminates edge cases when adding or deleting nodes at the head or tail.

1. Get(index): We iterate through the linked list to find the node at the given index, returning its value.

If the index is invalid, we return -1.

1. addAtHead(val): To add a node at the head, we create a new node with the given value.

We update the pointers to connect the new node to the previous head and the left dummy node.

1. addAtTail(val): Adding a node at the tail is similar to adding at the head.

We create a new node and update the pointers accordingly.

1. addAtIndex(index, val): To add a node at a specific index, we iterate to find the node before the desired position.

We insert the new node between the previous node and the found node, updating pointers accordingly.

1. deleteAtIndex(index): Deleting a node at a specific index involves finding the node to delete, updating the pointers of the previous and next nodes, effectively removing the node from the linked list.

Our approach simplifies all operations, making them consistent and efficient, with a space complexity that scales with the number of nodes in the linked list.

Related Interview Questions By Company:

• Snakes And Ladders LeetCode
• Online Stock Span LeetCode
• Subsets LeetCode

Related Interview Questions By Difficulty:

• Lru Cache LeetCode
• Merge Two Sorted Lists LeetCode
• Design Linked List LeetCode

Related Interview Questions By Category:

• Maximum Product Subarray LeetCode
• Kth Smallest Element In A BST LeetCode
• Lowest Common Ancestor Of A Binary Search Tree LeetCode

Conclusion

In this blog post, we tackled the Design Linked List problem (LeetCode Problem 707) and provided a Python solution for implementing a doubly linked list with various functionalities.

We discussed the problem statement, constraints, and provided a detailed explanation of our code.

Our solution addresses the core aspects of designing a linked list, including adding and deleting nodes at different positions, and retrieving values.

As you delve deeper into the world of data structures and algorithms, understanding and implementing linked lists is a fundamental skill.

We hope this blog post has helped you grasp the concepts and provided you with a clear solution to this problem.

If you have any questions, suggestions, or comments, please feel free to share them.

You can also experiment with the code and try different scenarios to deepen your understanding.

Happy coding!

Question Link

Remember, practice and exploration are key to mastering algorithms and data structures.

Encourage you to experiment, ask questions, and share knowledge with others in the programming community.

Keep coding and learning!