sorted linked list in python

Solutions on MaxInterview for sorted linked list in python by the best coders in the world

showing results for - "sorted linked list in python"
Vanessa
15 Oct 2017
1class Node:
2    def __init__(self, data, next1):
3        self.data = data
4        self.next = next1
5
6
7class Linkedlist:
8    def __init__(self):
9        self.head = None
10        self.size = 0
11
12    def length(self):
13        return self.size
14
15    def is_empty(self):
16        return self.size == 0
17    
18    # for normal singly linked list
19    
20    """
21    def insert_at_the_beginning(self, data):
22        self.insert_with_index(0, data)
23
24    def insert_at_the_ending(self, data):
25        self.insert_with_index(self.size, data)
26
27    def insert_with_index(self, index, data):
28        if index > self.size or index < 0:
29            print("check given", index, "index value and enter again")
30            return False
31        if index == 0:
32            self.head = Node(data, self.head)
33        else:
34            current = self.head
35            for i in range(index - 1):
36                current = current.next
37            current.next = Node(data, current.next)
38        self.size += 1
39    """
40
41    def peek_top(self):
42        return self.peek_index(0)
43
44    def peek_bottom(self):
45        return self.peek_index(self.size - 1)
46
47    def peek_index(self, index):
48        if index >= self.size or index < 0:
49            print("check given", index, "index value and enter again")
50            return False
51        current = self.head
52        for i in range(index):
53            current = current.next
54        return current.data
55
56    def peek_element(self, data):
57        current = self.head
58        while current.data != data:
59            if current.next is None:
60                print("element", data, "not found")
61                return False
62            current = current.next
63        print("element", data, "is found")
64        return True
65
66    def delete_top_element(self):
67        return self.delete_with_index(0)
68
69    def delete_bottom_element(self):
70        return self.delete_with_index(self.size - 1)
71
72    def delete_with_index(self, index):
73        if index >= self.size or index < 0:
74            print("check given", index, "index value and enter again")
75            return False
76        self.size -= 1
77        if index == 0:
78            temp = self.head
79            self.head = self.head.next
80            return temp.data
81        current = self.head
82        for i in range(index - 1):
83            current = current.next
84        temp = current.next
85        current.next = current.next.next
86        return temp.data
87
88    def delete_with_value(self, data):
89        current = self.head
90        previous = current
91        while current.data != data:
92            if current.next is None:
93                print("element", data, "not found")
94                return False
95            previous = current
96            current = current.next
97        temp = previous.next
98        previous.next = current.next
99        print("element", data, "is found and deleted")
100        self.size -= 1
101        return temp.data
102
103    def print_val(self):
104        current = self.head
105        while current:
106            print(current.data, "\b--->", end="")
107            current = current.next
108        print()
109
110
111class Sorted_Linked_List(Linkedlist):
112
113    def insert_element(self, data):
114        if self.head is None:
115            self.head = Node(data, self.head)
116        else:
117            current = self.head
118            previous = current
119            while current.data < data:
120                if current.next is None:
121                    current.next = Node(data, current.next)
122                    return True
123                previous = current
124                current = current.next
125            if previous == current:
126                self.head = Node(data, self.head)
127            else:
128                previous.next = Node(data, previous.next)
129        self.size += 1
130
131
132linkedlist = Sorted_Linked_List()
133
134
135def trail1():
136    linkedlist.insert_element(78)
137    linkedlist.insert_element(34)
138    linkedlist.insert_element(45)
139    linkedlist.insert_element(899)
140    linkedlist.insert_element(0)
141    linkedlist.insert_element(-1)
142    linkedlist.insert_element(8999999)
143    linkedlist.print_val()
144
145
146if __name__ == "__main__":
147    trail1()
148