单链表的实现

# 结点定义
class Node(object):
    def __init__(self, elem):
        self.elem = elem
        self.next = None

# 链表实现
class SingleLinkList(object):
    def __init__(self, node=None):
        self.__head = node

    def is_empty(self):
        return self.__head == None

    def length(self):
        cur = self.__head
        count = 0
        while cur is not None:
            count += 1
            cur = cur.next
        return count

    def travel(self):
        cur = self.__head
        while cur != None:
            print(cur.elem, end=" ")
            cur = cur.next
        print(end="\n")

    def add(self, item):
        node = Node(item)
        node.next = self.__head
        self.__head = node

    def append(self, item):
        node = Node(item)
        if self.is_empty():
            self.__head = node
        else:
            cur = self.__head
            while cur.next is not None:
                cur = cur.next
            cur.next = node

    def insert(self, pos, item):
        node = Node(item)
        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.next = pre.next
            pre.next = node

    def remove(self, item):
        cur = self.__head
        pre = None
        while cur is not 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):
        cur = self.__head
        while cur is not None:
            if cur.elem == item:             
                return True  
            else:
                cur = cur.next
        return False

#测试代码
if __name__ == "__main__":
    ll = SingleLinkList()
    print(ll.is_empty())
    print(ll.length())

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

    ll.append(2)
    ll.append(3)
    ll.insert(2, 93)
    ll.travel()
    ll.append(4)
    ll.append(5)
    ll.add(88)
    ll.append(6)
    ll.travel()
    ll.remove(5)
    ll.travel()
    print(ll.is_empty())
    print(ll.length())
    print(ll.search(88))

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

测试结果如下

True
0
False
1
1 2 93 3 
88 1 2 93 3 4 5 6 
88 1 2 93 3 4 6 
False
7
找到了
1
2
3
4
5
6
7
8
9
10

双向链表

class Node(object):
    def __init__(self, item):
        self.elem = item
        self.next = None
        self.prev = None


class DoubleLinkList(object):     # DoubleLinkList（SingleLinkList）可以继承单链表
    def __init__(self, node=None):
        self.__head = node

    def is_empty(self):
        return self.__head is None

    def length(self):
        cur = self.__head
        count = 0
        while cur is not None:
            count += 1
            cur = cur.next
        return count

    def travel(self):
        cur = self.__head
        while cur is not None:
            print(cur.elem, end=" ")
            cur = cur.next
        print(end="\n")

    def add(self, item):
        node = Node(item)
        if self.is_empty():     # 处理空链表
            self.__head = node
        else:
            node.next = self.__head
            self.__head = node
            node.next.prev = node       # 此句对空链表产生影响
            # self.__head.prev = node
            # self.__head = node

    def append(self, item):
        node = Node(item)
        cur = self.__head
        if self.is_empty():       # 处理空链表
            self.__head = node
        else:
            while cur.next is not None:
                cur = cur.next
            cur.next = node
            node.prev = cur

    def insert(self, pos, item):
        node = Node(item)
        if pos <= 0:
            self.add(item)
        elif pos > (self.length()-1):
            self.append(item)
        # 写法1：定位到pos结点前一个pre
        # else:
        #     count = 0
        #     pre = self.__head
        #
        #     while count < pos-1:
        #         count += 1
        #         pre = pre.next
        #     node.next = pre.next
        #     node.prev = pre
        #     node.next = pre.next
        #     pre.next = node
        # 写法2:定位到当前结点pos cur
        else:
            count = 0
            cur = self.__head
            while count < pos:
                count += 1
                cur = cur.next
            node.next = cur
            node.prev = cur.prev
            # cur.prev = node
            # node.prev.next = node
            # 最后两句还可以替换指向顺序
            cur.prev.next = node
            node.next = cur

    def remove(self, item):
        cur = self.__head
        pre = None
        cur = self.__head
        while cur is not None:
            if cur.elem == item:

                if cur == self.__head:          # 头结点
                    self.__head = cur.next      # 只有一个头结点
                    if cur.next:                # 不只是一个头指针
                        cur.next.prev = None
                else:
                    cur.prev.next = cur.next    # 尾结点
                    if cur.next:                # 不是 尾结点
                        cur.next.prev = cur.prev
                break
            else:
                cur = cur.next

    def search(self, item):
        cur = self.__head
        while cur is not None:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        return False


if __name__ == "__main__":
    
    ll = DoubleLinkList()
    print(ll.length())
    print(ll.is_empty())
    ll.insert(3, 1000)
    ll.remove(1000)
    ll.travel()
    ll.append(899)
    ll.add(5)
    ll.add(56)
    ll.add(9)
    ll.travel()
    ll.remove(5)
    ll.travel()
    ll.add(44)
    print(ll.length())
    print(ll.is_empty())
    ll.travel()
    print(ll.search(7))
    ll.remove(899)
    ll.travel()
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
134
135

测试结果如下

0
True

9 56 5 899 
9 56 899 
4
False
44 9 56 899 
False
44 9 56 
1
2
3
4
5
6
7
8
9
10