data_structures_and_algorithms/sinlyLinkedList.py at master · Rswcf/data_structures_and_algorithms · 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
131
132
133
class Node(object):
    '''节点'''
    def __init__(self, elem):
        self.elem = elem
        self.next = None


#node = Node(100)

class sinlyLinkedList(object):
    '''单链表'''

    def __init__(self, node = None):
        self.__head = node

    def is_empty(self):
        '''链表是否为空'''
        return self.__head == None

    def length(self):
        '''length of the linked list'''
        # cur游标，用来移动遍历节点
        cur = self.__head
        # count记录
        count = 0
        while cur != None:
            count += 1
            cur = cur.next

        return count

    def travel(self):
        '''traversal of the linked list'''
        cur = self.__head
        while cur != None:
            print(cur.elem, end= ' ')
            cur = cur.next
        print('')


    def add(self, item):
        '''add an item to the top of the linked list'''
        node = Node(item)
        node.next = self.__head
        self.__head = node

    def append(self, item):
        '''add an item to the end of the linked list'''
        node = Node(item)
        if self.is_empty():
            self.__head = node
        else:
            cur = self.__head
            while cur.next != None:
                cur = cur.next
            cur.next = node

    def insert(self, pos, item):
        '''insert the itemsto the specified position of the linked list'''
        if pos <= 0:
            self.add(item)
        elif pos > (self.length() - 1):
            self.append(item)
        else:
            pre = self.__head
            count = 0
            while count < (pos - 1):
                count += 1
                pre = pre.next
            node = Node(item)
            node.next = pre.next
            pre.next = node

    def remove(self,item):
        '''delete the item in the list'''
        cur = self.__head
        pre = None
        while cur != None:
            if cur.elem == item:
                # 先判断此节点是否是头节点
                # 头节点
                if cur == self.__head:
                    self.__head = cur.next
                else:
                    pre.next = cur.next
                break
            else:
                pre = cur
                cur = cur.next

    def search(self, item):
        '''search the the item in the list'''
        cur = self.__head
        while cur.next != None:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        return False


if __name__ == '__main__':
    ll = sinlyLinkedList()
    print(ll.is_empty())
    print(ll.length())

    ll.append(1)
    print(ll.is_empty())
    print(ll.length())

    ll.append(2)
    ll.add(8)
    ll.append(3)
    ll.append(4)
    ll.append(5)
    ll.append(6)
    # 8 1 2 3 4 5 6
    ll.insert(-1, 9)
    ll.travel()
    ll.insert(3, 100)
    ll.travel()
    ll.insert(10, 200)
    ll.travel()
    ll.remove(9)
    ll.travel()
    ll.remove(200)
    ll.travel


    ll.remove(1000)

    ll.travel()