DSA/doubly_linked_list.py at main · broyce24/DSA · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
class Node:
    def __init__(self, prev=None, data=None, next=None):
        self.prev = prev
        self.data = data
        self.next = next


class DoublyLinkedList:
    def __init__(self, values=None):
        self.size = 0
        self.head = None
        if values is not None:
            for value in values:
                self.append(value)

    def insert_at_beginning(self, data):
        new_node = Node(None, data, self.head)
        self.head = new_node
        self.size += 1

    def append(self, data):
        if self.head is None:
            self.insert_at_beginning(data)
            return

        itr = self.head
        while itr.next:
            itr = itr.next
        new_node = Node(itr, data, None)
        itr.next = new_node
        self.size += 1

    def print(self):
        if self.head is None:
            return 'DoublyLinkedList is empty!'
        itr = self.head
        output = '<- ' + str(itr.data) + ' ->'
        while itr.next:
            itr = itr.next
            output += '<- ' + str(itr.data) + ' ->'
        print(output)

    def insert_values(self, values):  # append values from iterable onto DLL
        for val in values:
            self.append(val)

    def clear(self):
        self.head = None
        self.size = 0

    def get_length(self):
        return self.size

    def remove_at(self, index):
        if index < 0 or index >= self.size:
            raise Exception("Invalid index!")

        if index == 0:
            self.head = self.head.next
            self.size -= 1
            return

        itr = self.head
        i = 0
        while itr:
            if i == index - 1:
                itr.next = itr.next.next
                if index < self.size - 1:
                    itr.next.prev = itr
            i += 1
            itr = itr.next
        self.size -= 1

    def insert_at(self, index, data):
        if index < 0 or index >= self.size:
            raise Exception("Invalid index!")
        if index == 0:
            self.insert_at_beginning(data)
            return
        itr = self.head
        i = 0
        while itr:
            if i == index - 1:
                new_node = Node(itr, data, itr.next)
                itr.next = new_node
                itr.next.next.prev = new_node
            i += 1
            itr = itr.next

    def insert_after_value(self, val, data):
        itr = self.head
        while itr:
            if itr.data == val:
                new_node = Node(itr, data, itr.next)
                itr.next = new_node
                itr.next.next.prev = new_node
                return
            itr = itr.next
        raise Exception(f"Value {val} not found!")

    def remove_by_value(self, val):
        if self.head.data == val:
            self.head = self.head.next
            return
        itr = self.head
        while itr:
            if itr.data == val:
                itr.prev.next = itr.next
                if itr.next:
                    itr.next.prev = itr.prev
                return
            itr = itr.next
        print(f"Value {val} not found!")


def main():
    ll = DoublyLinkedList()


if __name__ == '__main__':
    main()