链表

Posted on Edited on In

我们为了解决问题，需要将数据保存下来，然后根据数据的存储方式来设计算法实现进行处理，那么数据的存储方式不同就会导致需要不同的算法进行处理。我们希望算法解决问题的效率越快越好，于是我们就需要考虑数据究竟如何保存的问题，这就是数据结构。

算法与数据结构的区别

数据结构指数据对象中数据元素之间的关系。
高效的程序需要在数据结构的基础上设计和选择算法。

程序 = 数据结构 + 算法
总结：算法是为了解决实际问题而设计的，数据结构是算法需要处理的问题载体

链表定义

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是不像顺序表一样连续存储数据，而是在每一个节点（数据存储单元）里存放下一个节点的位置信息（即地址）。
链表

单向链表

单向链表也叫单链表，是链表中最简单的一种形式，它的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。

单向链表

表元素域elem用来存放具体的数据。
链接域next用来存放下一个节点的位置（python中的标识）
变量p指向链表的头节点（首节点）的位置，从p出发能找到表中的任意节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
"""
节点的实现
class SingleNode(object):
    # 单链表的节点
    def __init__(self,item):
        # _item存放数据元素
        self.item = item
        # _next是下一个节点的标识
        self.next = None
    # python中等号的意思为 将变量指向某个地址 比如 a=10 将a指向了存放10的地址 比如109323281251
    # next = 下一个节点的标识 就是将next指向了下一个节点的地址
    # ！！！  做到了单链表的 [元素][next]——[元素][next]     
"""

class Node(object):
    """节点"""

    def __init__(self, elem):
        self.elem = elem
        self.next = None


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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
"""
单链表的操作：
is_empty() 链表是否为空
length() 链表长度
travel() 遍历整个链表
add(item) 链表头部添加元素
append(item) 链表尾部添加元素
insert(pos, item) 指定位置添加元素
remove(item) 删除节点
search(item) 查找节点是否存在
"""

class singleLinkList(object):
    """单链表"""

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

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

    def length(self):
        """返回链表长度"""
        # cur用来遍历节点
        cur = self._head

        # cur = self._head = node
        # 所以后面循环中 会有 cur = cur.next = node.next 把游标cur 移到下一个节点
        # count用来计数

        count = 0
        while cur != None:
            cur = cur.next
            count += 1
        # 把游标 cur 指向第一个节点 如果第一个节点不是None 计数+1
        return count

    def travel(self):
        """遍历整个列表"""
        cur = self._head
        while cur != None:
            print(cur.elem, end=" ")
            cur = cur.next
        print(' ')

    def add(self, elem):
        """链表头部添加元素"""
        node = Node(elem)
        self._head, node.next = node, self._head

    def append(self, elem):
        """链表尾部添加元素"""

        # cur = self._head
        # while cur != None:
        #     cur = cur.next
        # cur.elem = elem
        # cur.next = None
        # 当cur = None的时候说明已经到了最后一个节点的Next 空节点
        # cur指向空节点 在空节点上创建Node 就是添加元素 个人理解

        node = Node(elem)
        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, elem):
        """指定位置添加元素"""
        if pos <= 0:
            self.add(elem)
        elif pos > (self.length() - 1):
            self.append(elem)
        else:
            cur = self._head
            i = 1
            node = Node(elem)
            while i < pos:
                i += 1
                cur = cur.next
            # 当循环退出后 cur找到前一个节点

            node.next = cur.next
            cur.next = node

    def remove(self, elem):
        """移除指定元素"""
        """还需要加个是否为空的判断"""

        # cur = self._head
        # # 如果第一节点就是要删除的元素 那么直接让self._head指向第二节点
        # if cur.elem == elem:
        #     self._head = cur.next
        # # 现在第一位不是要删除的了
        # # 那么假设 cur指向第一节点 behind指向第二节点 只要behind.elem是要删除的元素
        # # 就让cur.next指向 behind.next就可以实现第一节点指向第三节点 丢弃第二节点
        # # 实现删除功能
        # else:
        #     behind = cur.next
        #     while behind != None:
        #         if behind.elem == elem:
        #             cur.next = behind.next
        #
        #         cur = behind
        #         behind = cur.next

        cur = self._head
        pre = None
        while cur != None:
            # 判断元素
            if cur.elem == elem:
                # 判断是否头节点
                if cur == self._head:
                    self._head = cur.next
                else:
                    pre.next = cur.next
                break
            else:
                pre = cur
                cur = cur.next


    def search(self, elem):
        """查询指定元素"""
        cur = self._head
        while cur != None:
            if cur.elem == elem:
                print('存在')
                break
            else:
                cur = cur.next
        return False


if __name__ == "__main__":
    ll = singleLinkList()
    print(ll.is_empty())
    print(ll.length())
    ll.append(3)
    ll.append(4)
    ll.add(2)
    ll.add(1)
    # 1 2 3 4
    ll.insert(1, 100)
    ll.travel()
    # 1 100 2 3 4
    ll.insert(3, 200)
    # 1 100 2 200 3 4
    ll.travel()
    ll.remove(4)
    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
136
137
138
139
140
141
142
143
class Node(object):
    def __init__(self, elem):
        self.elem = elem
        self.next = None
        self.prev = None


class DoubleLinkList(object):
    """双向链表"""

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

    def is_empty(self):
        """链表是否为空"""
        return self._head is None

    def length(self):
        """返回链表长度"""
        # cur用来遍历节点
        cur = self._head
        # cur = self._head = node
        # 所以后面循环中 会有 cur = cur.next = node.next 把游标cur 移到下一个节点
        # count用来计数
        count = 0
        while cur is not None:
            cur = cur.next
            count += 1
        # 把游标 cur 指向第一个节点 如果第一个节点不是None 计数+1
        return count

    def travel(self):
        """遍历整个列表"""
        cur = self._head
        while cur is not None:
            print(cur.elem, end=" ")
            cur = cur.next
        print(' ')

    def add(self, elem):
        """链表头部添加元素"""
        node = Node(elem)
        if self.is_empty():
            self._head = node
        else:
            node.next = self._head
            self._head.prev = node
            self._head = node

    def append(self, elem):
        """链表尾部添加元素"""

        node = Node(elem)
        if self.is_empty():
            # 如果链表是空，就是直接添加节点
            self._head = node
        else:
            cur = self._head
            while cur.next is not None:
                cur = cur.next
            cur.next = node
            node.prev = cur

    def insert(self, pos, elem):
        """指定位置添加元素"""
        if pos <= 0:
            self.add(elem)
        elif pos > (self.length() - 1):
            self.append(elem)
        else:
            cur = self._head
            i = 1
            node = Node(elem)
            while i < pos:
                i += 1
                cur = cur.next
            # 当循环退出后 cur找到前一个节点

            # node指向cur的下一个节点
            node.next = cur.next
            # cur下一个节点的头指向node
            cur.next.prev = node
            # cur指向node
            cur.next = node
            # node的头指向cur
            node.prev = cur

    def remove(self, elem):
        """移除指定元素"""
        """还需要加个是否为空的判断"""
      
        cur = self._head
        pre = None
        while cur is not None:
            # 判断元素
            if cur.elem == elem:
                # 判断是否头节点
                if cur == self._head:
                    if cur.next is None:
                        self._head = None
                    else:
                        cur.next.prev = None
                        self._head = cur.next
                else:
                    pre.next = cur.next
                    cur.next.prev = pre
                break
            else:
                pre = cur
                cur = cur.next

    def search(self, elem):
        """查询指定元素"""
        cur = self._head
        while cur is not None:
            if cur.elem == elem:
                print('存在')
                break
            else:
                cur = cur.next
        return False


if __name__ == '__main__':
    dl = DoubleLinkList()
    dl.add(2)
    dl.add(1)
    dl.append(3)
    dl.append(4)
    dl.travel()
    # 1 2 3 4
    dl.insert(1, 100)
    dl.travel()
    # 1 100 2 3 4
    dl.insert(3, 200)
    dl.travel()
    # 1 100 2 200 3 4
    dl.remove(200)
    dl.travel()
    # 1 100 2 3 4
    dl.remove(100)
    dl.travel()
    # 1 2 3 4

单向循环链表

单链表的一个变形是单向循环链表，链表中最后一个节点的next域不再为None，而是指向链表的头节点。

单向循环链表

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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
class Node(object):
    """节点"""

    def __init__(self, elem):
        self.elem = elem
        self.next = None


class SingleCircleLinkList(object):
    """单向循环链表"""

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

    def is_empty(self):
        """链表是否为空"""
        return self._head is None

    def length(self):
        """返回链表长度"""
        if self._head is None:
            return 0
        count = 1
        cur = self._head
        while cur.next is not self._head:
            cur = cur.next
            count += 1
        return count

    def travel(self):
        """遍历整个列表"""
        if self.is_empty():
            return
        cur = self._head
        print(cur.elem)
        while cur.next is not self._head:
            cur = cur.next
            print(cur.elem)

        print(' ')

    def add(self, elem):
        """链表头部添加元素"""
        node = Node(elem)
        # 如果没有节点 头指向node node.next指向自己
        if self.is_empty():
            self._head = node
            node.next = self._head
        # 如果有节点存在 node.next指向头 尾部.next指向node
        else:
            cur = self._head
            node.next = self._head

            while cur.next is not self._head:
                cur = cur.next
            cur.next = node
            self._head = node

    def append(self, elem):
        """链表尾部添加元素"""

        node = Node(elem)
        if self.is_empty():
            # 如果链表是空，就是直接添加节点
            self._head = node
            node.next = self._head
        else:
            cur = self._head
            while cur.next is not self._head:
                cur = cur.next
            cur.next = node
            node.next = self._head

    def insert(self, pos, elem):
        """指定位置添加元素"""
        if pos <= 0:
            self.add(elem)
        elif pos > (self.length() - 1):
            self.append(elem)
        else:
            node = Node(elem)
            cur = self._head
            count = 0
            # 移动到指定位置的前一个位置
            while count < (pos - 1):
                count += 1
                cur = cur.next
            node.next = cur.next
            cur.next = node

    def remove(self, elem):
        """移除指定元素"""
        """还需要加个是否为空的判断"""

        if self.is_empty():
            return
        cur = self._head
        pre = None
        # 判断是否是头部
        if cur.elem is elem:
            # 判断链表是否只有一个节点
            if cur.next is self._head:
                self._head = None
            # 不止一个节点
            else:
                # pre = self._head
                while cur.next is not self._head:
                    cur = cur.next
                cur.next = self._head.next
                self._head = self._head.next
        # 不是头部
        else:
            pre = self._head
            while cur.next is not self._head:
                if cur.elem is elem:
                    pre.next = cur.next
                    return
                else:
                    pre = cur
                    cur = cur.next

    def search(self, elem):
        """查询指定元素"""
        cur = self._head
        while cur is not None:
            if cur.elem == elem:
                print('存在')
                break
            else:
                cur = cur.next
        return False


if __name__ == '__main__':
    dl = SingleCircleLinkList()
    dl.add(2)
    dl.add(1)
    dl.append(3)
    dl.append(4)
    dl.travel()
    # 1 2 3 4
    dl.insert(1, 100)
    dl.travel()
    # 1 100 2 3 4
    dl.insert(3, 200)
    dl.travel()
    # 1 100 2 200 3 4
    dl.remove(200)
    dl.travel()
    # 1 100 2 3 4
    dl.remove(100)
    dl.travel()
    # 1 2 3 4