How do you solve Design Linked List on LeetCode?

Design Linked List (LeetCode #707) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Using a linked list allows for dynamic memory allocation and efficient insertions/deletions.

What is the brute force solution for Design Linked List?

The brute force approach for Design Linked List is Brute Force, with O(n²) time complexity and O(1) space complexity. In this approach, we will use a simple array to represent the linked list. Each operation will involve iterating through the list to find the correct position for insertion or deletion, making it straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Design Linked List?

Design Linked List uses the following concepts: Linked List, Design. The recommended patterns to study are: Linked List, Dynamic Arrays.

What are the interview tips for Design Linked List?

Always clarify if the linked list is singly or doubly linked. Discuss the time complexity of each operation during the interview. Practice implementing both types of linked lists to understand their differences.

What are common mistakes when solving Design Linked List?

Not handling edge cases like adding/deleting at the head or tail correctly. Forgetting to update the size of the linked list after operations.

#707

Design Linked List

Medium

Linked ListDesignLinked ListDynamic Arrays

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

Using a doubly linked list allows us to efficiently manage node insertions and deletions at both ends and in the middle, providing O(1) time complexity for these operations.

⚙️

Algorithm

6 steps

1Step 1: Create a Node class to represent each node with val, next, and prev pointers.
2Step 2: Initialize the head and tail pointers in MyLinkedList.
3Step 3: For 'addAtHead', create a new node and adjust pointers accordingly.
4Step 4: For 'addAtTail', create a new node and adjust pointers accordingly.
5Step 5: For 'addAtIndex', traverse to the index, create a new node, and adjust pointers.
6Step 6: For 'deleteAtIndex', traverse to the index and adjust pointers to remove the node.

solution.py77 lines

1class Node:
2    def __init__(self, val=0, next=None, prev=None):
3        self.val = val
4        self.next = next
5        self.prev = prev
6
7class MyLinkedList:
8    def __init__(self):
9        self.head = None
10        self.tail = None
11        self.size = 0
12
13    def get(self, index):
14        if index < 0 or index >= self.size:
15            return -1
16        curr = self.head
17        for _ in range(index):
18            curr = curr.next
19        return curr.val
20
21    def addAtHead(self, val):
22        new_node = Node(val)
23        if self.size == 0:
24            self.head = self.tail = new_node
25        else:
26            new_node.next = self.head
27            self.head.prev = new_node
28            self.head = new_node
29        self.size += 1
30
31    def addAtTail(self, val):
32        new_node = Node(val)
33        if self.size == 0:
34            self.head = self.tail = new_node
35        else:
36            new_node.prev = self.tail
37            self.tail.next = new_node
38            self.tail = new_node
39        self.size += 1
40
41    def addAtIndex(self, index, val):
42        if index < 0 or index > self.size:
43            return
44        if index == 0:
45            self.addAtHead(val)
46        elif index == self.size:
47            self.addAtTail(val)
48        else:
49            new_node = Node(val)
50            curr = self.head
51            for _ in range(index):
52                curr = curr.next
53            new_node.prev = curr.prev
54            new_node.next = curr
55            curr.prev.next = new_node
56            curr.prev = new_node
57            self.size += 1
58
59    def deleteAtIndex(self, index):
60        if index < 0 or index >= self.size:
61            return
62        if index == 0:
63            self.head = self.head.next
64            if self.head:
65                self.head.prev = None
66        elif index == self.size - 1:
67            self.tail = self.tail.prev
68            if self.tail:
69                self.tail.next = None
70        else:
71            curr = self.head
72            for _ in range(index):
73                curr = curr.next
74            curr.prev.next = curr.next
75            if curr.next:
76                curr.next.prev = curr.prev
77        self.size -= 1

ℹ

Complexity note: The time complexity is O(n) for get and addAtIndex operations due to the need to traverse the list, while addAtHead and addAtTail are O(1). The space complexity is O(n) because we store n nodes.

1Using a linked list allows for dynamic memory allocation and efficient insertions/deletions.
2Doubly linked lists provide easier traversal in both directions.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.