linked list operations in python

1# Linked list operations in Python
2
3
4# Create a node
5class Node:
6    def __init__(self, data):
7        self.data = data
8        self.next = None
9
10
11class LinkedList:
12
13    def __init__(self):
14        self.head = None
15
16    # Insert at the beginning
17    def insertAtBeginning(self, new_data):
18        new_node = Node(new_data)
19
20        new_node.next = self.head
21        self.head = new_node
22
23    # Insert after a node
24    def insertAfter(self, prev_node, new_data):
25
26        if prev_node is None:
27            print("The given previous node must inLinkedList.")
28            return
29
30        new_node = Node(new_data)
31        new_node.next = prev_node.next
32        prev_node.next = new_node
33
34    # Insert at the end
35    def insertAtEnd(self, new_data):
36        new_node = Node(new_data)
37
38        if self.head is None:
39            self.head = new_node
40            return
41
42        last = self.head
43        while (last.next):
44            last = last.next
45
46        last.next = new_node
47
48    # Deleting a node
49    def deleteNode(self, position):
50
51        if self.head is None:
52            return
53
54        temp = self.head
55
56        if position == 0:
57            self.head = temp.next
58            temp = None
59            return
60
61        # Find the key to be deleted
62        for i in range(position - 1):
63            temp = temp.next
64            if temp is None:
65                break
66
67        # If the key is not present
68        if temp is None:
69            return
70
71        if temp.next is None:
72            return
73
74        next = temp.next.next
75
76        temp.next = None
77
78        temp.next = next
79
80    # Search an element
81    def search(self, key):
82
83        current = self.head
84
85        while current is not None:
86            if current.data == key:
87                return True
88
89            current = current.next
90
91        return False
92
93    # Sort the linked list
94    def sortLinkedList(self, head):
95        current = head
96        index = Node(None)
97
98        if head is None:
99            return
100        else:
101            while current is not None:
102                # index points to the node next to current
103                index = current.next
104
105                while index is not None:
106                    if current.data > index.data:
107                        current.data, index.data = index.data, current.data
108
109                    index = index.next
110                current = current.next
111
112    # Print the linked list
113    def printList(self):
114        temp = self.head
115        while (temp):
116            print(str(temp.data) + " ", end="")
117            temp = temp.next
118
119
120if __name__ == '__main__':
121
122    llist = LinkedList()
123    llist.insertAtEnd(1)
124    llist.insertAtBeginning(2)
125    llist.insertAtBeginning(3)
126    llist.insertAtEnd(4)
127    llist.insertAfter(llist.head.next, 5)
128
129    print('linked list:')
130    llist.printList()
131
132    print("\nAfter deleting an element:")
133    llist.deleteNode(3)
134    llist.printList()
135
136    print()
137    item_to_find = 3
138    if llist.search(item_to_find):
139        print(str(item_to_find) + " is found")
140    else:
141        print(str(item_to_find) + " is not found")
142
143    llist.sortLinkedList(llist.head)
144    print("Sorted List: ")
145    llist.printList()