Linked List in Python#
Singly Linked List#
1class Node:
2 def __init__(self, data):
3 self.data = data
4 self.next = None
5
6
7class LinkedList:
8 def __init__(self) -> None:
9 self.head = None
10 self.tail = None
11
12 def print_list(self):
13 tmp = self.head
14 while tmp:
15 print(tmp.data, end=" ")
16 tmp = tmp.next
17 if tmp:
18 print("-> ", end=" ")
19 print()
20
21 def append(self, value):
22 # O(1) if know the tail
23 new_node = Node(value)
24 if self.head == None:
25 self.head = new_node
26 self.tail = new_node
27 else:
28 self.tail.next = new_node
29 self.tail = new_node
30
31 def prepend(self, value):
32 # O(1)
33 new_node = Node(value)
34 if self.head == None:
35 self.head = new_node
36 self.tail = new_node
37 else:
38 new_node.next = self.head
39 self.head = new_node
40
41 def pop_first(self):
42 # O(1)
43 if self.head == None:
44 return
45 if self.head.next == None:
46 self.head = None
47 self.tail = None
48 return
49
50 tmp = self.head
51 self.head = self.head.next
52 tmp.next = None
53 return tmp
54
55 def pop(self):
56 # O(N)
57 if self.head == None:
58 return
59 if self.head.next == None:
60 self.head = None
61 self.tail = None
62 return
63
64 temp = self.head
65 while temp.next.next:
66 temp = temp.next
67
68 temp.next = None
69 self.tail = temp
70 return temp
71
72 def reverse(self, head):
73 # # O(N)
74 # if self.head == None:
75 # return
76 # if self.head.next == None:
77 # return
78
79 # prev = None
80 # curr = self.head
81 # after = curr.next
82
83 # while after:
84 # curr.next = prev
85 # prev = curr
86 # curr = after
87 # after = after.next
88
89 # curr.next = prev
90 # self.head, self.tail = self.tail, self.head
91 if not self.head:
92 return None
93
94 new_head = self.head
95 if self.head.next:
96 new_head = self.reverse(head=self.head.next)
97 self.head.next.next = self.head
98
99 self.head.next = None
100 return new_head
101
102
103if __name__ == "__main__":
104
105 linkedlist = LinkedList()
106 linkedlist.append(1)
107 linkedlist.append(2)
108 linkedlist.append(3)
109
110 linkedlist.print_list()
111 linkedlist.prepend(0)
112 linkedlist.print_list()
113
114 linkedlist.reverse(linkedlist.head)
115
116 linkedlist.print_list()
Doubly Linked List#
1class Node:
2 def __init__(self, data) -> None:
3 self.data = data
4 self.next = None
5 self.prev = None
6
7
8class DoublyLinkedList:
9 def __init__(self) -> None:
10 self.head = None
11 self.tail = None
12
13 def print_list(self):
14 tmp = self.head
15 while tmp:
16 print(tmp.data, end=" ")
17 tmp = tmp.next
18 if tmp:
19 print(" <-> ", end=" ")
20 print()
21
22 def append(self, value):
23 # O(1) if know tail
24 new_node = Node(value)
25 if self.head == None:
26 self.head = new_node
27 self.tail = new_node
28 else:
29 self.tail.next = new_node
30 new_node.prev = self.tail
31 self.tail = new_node
32
33 def prepend(self, value):
34 # O(1)
35 new_node = Node(value)
36 if self.head == None:
37 self.head = new_node
38 self.tail = new_node
39 else:
40 new_node.next = self.head
41 self.head.prev = new_node
42 self.head = new_node
43
44 def pop_first(self):
45 # O(1)
46 if self.head == None:
47 return
48 if self.head.next == None:
49 self.head = None
50 self.tail = None
51 return
52
53 temp = self.head
54 self.head = self.head.next
55 self.head.prev = None
56 temp.next = None
57 return temp
58
59 def pop(self):
60 # O(1)
61 if self.head == None:
62 return
63 if self.head.next == None:
64 self.head = None
65 self.tail = None
66
67 temp = self.tail
68 self.tail = self.tail.prev
69 self.tail.next = None
70 temp.prev = None
71 return temp
72
73
74if __name__ == "__main__":
75
76 dl = DoublyLinkedList()
77 dl.append(1)
78 dl.append(2)
79 dl.append(3)
80 dl.prepend(0)
81 dl.prepend(-1)
82 dl.print_list()
83
84 dl.pop()
85 dl.print_list()
86
87 dl.pop_first()
88 dl.print_list()