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()