algorithm/python/code/linkedlist/linked_list.py at master · yangfcm/algorithm · 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, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.__head__ = None
        self.__count__ = 0

    def count(self):
        return self.__count__

    def get_first(self):
        return self.__head__

    def get_last(self):
        if(self.__head__ == None):
            return None

        current = self.__head__
        while(current.next != None):
            current = current.next

        return current

    def get_at(self, index):
        if(index < 0 or index > self.__count__):
            raise IndexError("Index out of range")

        current = self.__head__
        for i in range(0, index):
            current = current.next

        return current

    def search(self, value):
        current = self.__head__
        while(current != None):
            if(current.data == value):
                return True
            current = current.next
        return False

    def clear(self):
        self.__head__ = None
        self.__count__ = 0

    def insert_first(self, value):
        newNode = Node(value)
        newNode.next = self.__head__
        self.__head__ = newNode
        self.__count__ += 1

    def insert_last(self, value):
        if self.__count__ == 0:
            self.insert_first(value)
            return
        lastNode = self.get_last()
        newNode = Node(value)
        lastNode.next = newNode
        self.__count__ += 1

    def insert_at(self, index, value):
        if(index < 0 or index > self.__count__):
            raise IndexError("Index out of range")
        if(index == 0):
            self.insert_first(value)
            return

        if(index == self.__count__):
            self.insert_last(value)
            return

        current = self.__head__
        for i in range(0, index-1):
            current = current.next

        newNode = Node(value)
        newNode.next = current.next
        current.next = newNode
        self.__count__ += 1

    def remove_first(self):
        if(self.__head__ == None):
            return

        self.__head__ = self.__head__.next
        self.__count__ -= 1

    def remove_last(self):
        if(self.__head__ == None):
            return

        if(self.__head__.next == None):
            self.__head__ = None
            self.__count__ -= 1
            return

        current = self.__head__
        while(current.next.next != None):
            current = current.next
        current.next = None
        self.__count__ -= 1

    def remove_at(self, index):
        if(index < 0 or index > self.__count__):
            raise IndexError("Index out of range")
        if(index == 0):
            self.remove_first()
            return

        if(index == self.__count__):
            self.remove_last()
            return

        current = self.__head__
        for i in range(0, index-1):
            current = current.next
        current.next = current.next.next
        self.__count__ -= 1