Data-Structures/dll.py at master · SnSCoderBros/Data-Structures · 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
122
123
124
125
126
127
128
129
130
"""
Doubly Linked Lists
- uses Nodes
None < A >< B >< C >< D >< E > None
'E'

"""


class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None


class DLL:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)

        if not self.head:
            self.head = new_node
            return

        cur = self.head

        while cur.next:
            cur = cur.next

        cur.next = new_node
        new_node.prev = cur

    def print_list(self):
        cur = self.head

        while cur:
            print(cur.data)
            cur = cur.next

    def delete(self, data):

        if not self.head:
            print('List is empty.')
            return

        cur = self.head

        while cur:
            if cur.data == data:
                if cur == self.head:
                    self.head = self.head.next
                else:
                    cur.prev.next = cur.next

                    if cur.next:
                        cur.next.prev = cur.prev

            cur = cur.next

    def reverse(self):

        prev = None
        cur = self.head

        while cur:
            nxt = cur.next
            cur.next = cur.prev

            if cur.prev:
                cur.prev = cur.next

            prev = cur
            cur = nxt

        self.head = prev

    def is_palindrome(self):
        cur = self.head
        last = self.head

        while last.next:
            last = last.next

        while cur != last:
            # print(cur.data, last.data)

            if cur.data != last.data:
                return False

            cur = cur.next
            if cur == last:
                return True

            last = last.prev

        return True

    def find_kth_node_from_end(self, k):
        # A B C D E  - 2

        last = self.head

        while last.next:
            last = last.next

        count = 1

        while count != k:
            if not last.prev:
                return None

            last = last.prev
            count += 1

        return last.data


dll = DLL()
dll.append('A')
dll.append('B')
dll.append('C')
dll.append('D')
dll.append('E')

val = dll.find_kth_node_from_end(7)

print(val)