Sponsored
Sponsored
In this approach, you will design a singly linked list where each node has a value and a pointer to the next node. This type of list is simple and efficient for certain operations, especially when traversing only forwards is sufficient.
Time Complexity:
- get: O(n)
- addAtHead: O(1)
- addAtTail: O(n)
- addAtIndex: O(n)
- deleteAtIndex: O(n)
Space Complexity: O(n), where n is the number of nodes in the list.
1class Node:
2 def __init__(self, val: int):
3 self.val = val
4 self.next = None
5
6class MyLinkedList:
7 def __init__(self):
8 self.head = None
9
10 def get(self, index: int) -> int:
11 current = self.head
12 for i in range(index):
13 if current is None:
14 return -1
15 current = current.next
16 return current.val if current else -1
17
18 def addAtHead(self, val: int) -> None:
19 node = Node(val)
20 node.next = self.head
21 self.head = node
22
23 def addAtTail(self, val: int) -> None:
24 node = Node(val)
25 if not self.head:
26 self.head = node
27 else:
28 current = self.head
29 while current.next:
30 current = current.next
31 current.next = node
32
33 def addAtIndex(self, index: int, val: int) -> None:
34 if index == 0:
35 self.addAtHead(val)
36 return
37 current = self.head
38 for i in range(index - 1):
39 if current is None:
40 return
41 current = current.next
42 if not current: return
43 node = Node(val)
44 node.next = current.next
45 current.next = node
46
47 def deleteAtIndex(self, index: int) -> None:
48 if index == 0:
49 if self.head:
50 self.head = self.head.next
51 return
52 current = self.head
53 for i in range(index - 1):
54 if current is None:
55 return
56 current = current.next
57 if current and current.next:
58 current.next = current.next.nextThis Python solution uses a class-based approach to represent nodes and the singly linked list. The list starts at the head node and supports operations like adding and removing elements at various positions efficiently.
This approach designs a doubly linked list, allowing traversal both forwards and backwards. Each node maintains a reference to both the next and previous node, facilitating operations such as adding or removing nodes from either end more efficiently.
Time Complexity:
- get: O(n)
- addAtHead: O(1)
- addAtTail: O(n)
- addAtIndex: O(n)
- deleteAtIndex: O(n)
Space Complexity: O(n), where n is the number of nodes in the list.
1
The C implementation of a doubly linked list adds a prev pointer to each node, enabling two-way node traversal and efficient deletion and insertion operations from both ends.