链表

前言

前面讲了顺序表，顺序表的缺点在于无法动态扩容，若顺序表的容量达到上限，再来一个数据，就需要重新申请足够大的内存空间来重新存储。那有没有数据结构能够实现数据来一个就增加一个而不需要重新申请内存空间呢？链表就是这么一个数据结构。

为什么需要链表

顺序表的构建需要预先知道数据大小来申请连续的存储空间，而在进行扩充时又需要进行数据的搬迁，所以使用起来并不是很灵活。

链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。

链表的定义

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

链表

案例

假设一开是有一个数据200，存储在某个内存空间中，这时候又来一个数据400，也存储在某个内存空间中，600同理。现在先要把这些离散存储的数据给连续起来，怎么实现呢？

首先，把400的内存地址放在200的内存空间里，使得200可以链接到400，同理400->600，这样就可以把一组离散内存空间存储的数据给联系起来，这就是链表。

image-20210130210358864

链表(单向)的示意如下图：

image-20210130211304095

单向链表

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

image-20210130211651645

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

拓展

如何理解Python中的：

1
2
3
a = 10
b = 20
a, b = b, a

image-20210130212632797

image-20210130212936537

由此可见，a, b = b, a，赋值并不是真正的赋值，而是把a, b引用的地址导向给转换。

而pyton之所以能够实现隐式申明是因为变量a保存的是一个地址，a的地址指向谁，a就是谁。

也正因为python的“=”的特殊性，python实现的链表中，链接域并非是地址，而是一个类节点，具体参考下面的节点实现代码。

节点实现

1
2
3
4
5
6
7
class SingleNode(object):
    """单链表的结点"""
    def __init__(self,item):
        # _item存放数据元素
        self.item = item
        # _next是下一个节点的标识
        self.next = None	# 指向下一个SingleNode对象

单链表的操作

  • is_empty() 链表是否为空
  • length() 链表长度
  • travel() 遍历整个链表
  • add(item) 链表头部添加元素
  • append(item) 链表尾部添加元素
  • insert(pos, item) 指定位置添加元素
  • remove(item) 删除节点(如果有多个相同的，仅删除靠左边的第一个节点)
  • search(item) 查找节点是否存在

单链表的实现

image-20210130222522597

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
# coding:utf-8
class Node(object):
    """节点"""
    def __init__(self, elem):
        self.elem = elem
        self.next = None

# 把节点窜连起来
class SingalLinkList(object):
    """单链表"""
    def __init__(self, node=None):  # node如果一开始没指定，则是空来链表，头指针指向none
        """创建头节点，指向第一个节点"""
        # 头节点的属性是内部维护的，对外不暴露,是私有的,在变量名前加一个"_"
        self._head = node
    def is_empty(self):
        """链表是否为空"""
        pass

    def length(self):
        """返回链表长度"""
        pass
        # cur初始时指向头节点
        cur = self._head
        count = 0
        # 尾节点指向None，当未到达尾部时
        while cur != None:
            count += 1
            # 将cur后移一个节点
            cur = cur.next
        return count

    def travel(self):
        """遍历链表"""
        cur = self._head
        while cur != None:
            print cur.item,
            cur = cur.next
        print ""

    def add(self, item):
        """链表头部添加元素"""
        pass

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

    def insert(self, item):
        """指定位置插入元素"""
        pass

    def remove(self, item):
        """删除节点"""
        pass

    def search(self, item):
        """查找节点是否存在"""
        pass

头部添加元素

单链表表头插入元素

1
2
3
4
5
6
7
def add(self, item):
    """链表头部添加元素，头插法"""
    node = Node(item)
    # 使得新节点的next域指向原有的首节点
    # 再考虑初始链表为空链表的情况
    node.next = self.__head
    self.__head = node

头插法结果

尾部添加元素

1
2
3
4
5
6
7
8
9
10
11
12
def append(self, item):
    """尾部添加元素"""
    node = SingleNode(item)
    # 先判断链表是否为空，若是空链表，则将_head指向新节点
    if self.is_empty():
        self._head = node
    # 若不为空，则找到尾部，将尾节点的next指向新节点
    else:
        cur = self._head
        while cur.next != None:
            cur = cur.next
        cur.next = node

指定位置添加元素

单链表指定位置添加元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def insert(self, pos, item):
    """指定位置插入元素
    :param pos start from 0
    """
    # pre用来指向指定位置pos的前一个位置pos-1，初始从头节点开始移动到指定位置
    pre = self.__head
    count = 0
    # 将pos<0看作是跟0一个效果，即头插法
    # 若指定位置pos为第一个元素之前，则执行头部插入
    if pos < 0:
        self.add(item)
    # 若指定位置超过链表尾部，则执行尾部插入
    elif pos > (self.length() - 1):
        self.append(item)
    else:
        # 当循环结束后，pre指向pos-1位置
        while count < (pos - 1):
            pre = pre.next
            count += 1
        node = Node(item)
        # 先将新节点node的next指向插入位置的节点
        node.next = pre.next
         # 将插入位置的前一个节点的next指向新节点
        pre.next = node

指定位置添加元素

删除节点

单链表删除节点

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
  
def remove(self, item):
    """删除节点"""
    # 不按照位置删除，而是删除具体数据
    # 有两种方式(由游标决定)
    cur = self.__head
    # 1.建立两个游标
    pre = None
    while cur is not None:
        # 删除元素在尾部的情况也ok
        if cur.elem == item:
            # 删除元素是首节点，pre=None，判断节点是否是头节点
            # 如果第一个就是删除的节点
            if cur == self.__head:
                # 将头指针指向头节点的后一个节点
                self.__head = cur.next
            else:
                # 删除元素在中间情况下：直接改变链表所指即可，被删除的元素的指针不用管
                # 将删除位置前一个节点的next指向删除位置的后一个节点
                pre.next = cur.next
            break
        else:
            # 继续按链表后移节点
            pre = cur
            cur = cur.next

删除节点

查找节点是否存在

1
2
3
4
5
6
7
8
9
def search(self, item):
    """查找节点是否存在，返回True or False"""
    cur = self.__head
    while cur != None:
        if cur.elem == item:
            return True # 函数返回后结束
        else:
            cur = cur.next
    return False

查找节点是否存在

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
if __name__ == "__main__":
    ll = SingleLinkList()
    ll.add(1)
    ll.add(2)
    ll.append(3)
    ll.insert(2, 4)
    print "length:",ll.length()
    ll.travel()
    print ll.search(3)
    print ll.search(5)
    ll.remove(1)
    print "length:",ll.length()
    ll.travel()

链表与顺序表的对比

链表失去了顺序表随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大，但对存储空间的使用要相对灵活。

链表与顺序表的各种操作复杂度如下所示：

操作 链表 顺序表
访问元素 O(n) O(1)
在头部插入/删除 O(1) O(n)
在尾部插入/删除 O(n) O(1)
在中间插入/删除 O(n) O(n)

注意虽然表面看起来复杂度都是 O(n)，但是链表和顺序表在插入和删除时进行的是完全不同的操作。链表的主要耗时操作是遍历查找，删除和插入操作本身的复杂度是O(1)。顺序表查找很快，主要耗时的操作是拷贝覆盖。因为除了目标元素在尾部的特殊情况，顺序表进行插入和删除时需要对操作点之后的所有元素进行前后移位操作，只能通过拷贝和覆盖的方法进行。

补充概念：

当前节点的后一个节点叫做后继节点，前一个节点叫前驱节点。

单向循环链表

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

单向循环链表

操作

  • is_empty() 判断链表是否为空
  • length() 返回链表的长度
  • travel() 遍历
  • add(item) 在头部添加一个节点
  • append(item) 在尾部添加一个节点
  • insert(pos, item) 在指定位置pos添加节点
  • remove(item) 删除一个节点
  • search(item) 查找节点是否存在

实现

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
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
from SingalLinkList import SingalLinkList


class Node(object):
    """
    单节点
    本链表头节点索引为0
    """

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


class CirSingalLinkList(SingalLinkList):
    """
    单向循环链表
    """

    def __init__(self, node=None):
        """当链表是空，头节点指向None"""
        super(CirSingalLinkList, self).__init__(node)
        self.__head = None

    def is_empty(self):
        """和单链表一样，方法不需要修改直接继承"""
        pass

    def length(self):
        """
        因为尾部节点指针指向头部所以需要修改
        """
        if self.__head:

            # num = 1
            num = 0
            length = self.__head.next
            # while length:
            while (length != self.__head):
                num += 1
                length = length.next
            # print(f"SingalLinkList Length Is {num}")
            #
            # return num
            return num+1

        return 0
             

    def travel(self):
        # 重写方法
        if self.__head:
            # num = 1
            num = 0
            length = self.__head.next
            print(f"{num} : {self.__head.item}")
            # while length:
            while (length != self.__head):
                num += 1
                print(f"{num} : {length.item}")
                length = length.next

        else:
            print("The SingalLinkList Is None")

    def add(self, item):
        """链表头部添加元素,尾部指针指向头节点"""
        new = Node(item)

        # if not self.length():
        if not self.__head:
            self.__head = new
            new.next = self.__head
        else:
            point = self.__head.next
            while (point.next != self.__head):
                point = point.next

            new.next = self.__head
            point.next = new
            self.__head = new

    def append(self, item):
        """链表尾部添加元素"""
        new = Node(item)

        if not self.__head:
            self.__head = new
            new.next = self.__head

        else:
            point = self.__head.next
            while (point.next != self.__head):
                point = point.next

            new.next = point.next
            point.next = new

    def insert(self, pos, item):
        # 相当于从头部插入
        # if pos == 1:
        if pos == 0:
            self.add(item)
            return 0

        if pos < 0:
            """输入负数位置，默认从头插入"""
            self.add(item)
            return 0

        """指定位置插入元素"""
        if self.length() < pos:
            if self.length == 0:
                print("SingalLinkList is Null")
            else:
                self.append(item)

        else:
            new = Node(item)

            point = self.__head
            # pos -= 2
            pos -= 1

            while pos:
                pos -= 1
                point = point.next

            new.next = point.next
            point.next = new

    def remove(self, item):
        # 修改
        """删除指定节点的数据，如果有多个相同的删除左边第一个"""
        find = False
        if not self.__head:
            print("SingalLinkList is Null!")

        else:
            # if self.length() == 1:
            # 	"""链表只有一个节点，直接让头结点== None"""
            # 	self.__head = None

            pre_point = None
            point = self.__head

            # while point:
            while (point.next != self.__head):

                if point.item == item:
                    find = True
                    break

                pre_point = point
                point = point.next

            if find:
                if pre_point == None:
                    # 代表删除的元素是头结点所指的情况
                    self.__head = self.__head.next

                else:
                    pre_point.next = point.next
            else:
                print("warning:No Found The Item That You Want To Delete!")


if __name__ == "__main__":
    ll = SingalLinkList()
    # 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.travel()

        # print(ll.search(1))    # True
    # print(ll.search(67))   # False
    # 8 1 2 3 4
    ll.insert(-1, 9)
    # 9 8 1 2 3 4
    ll.travel()

    ll.insert(2, 100)
    # 9 8 100 1 2 3 4
    ll.travel()
    ll.insert(10, 200)

3-12视频最后10mins关于链表补充

双向链表

一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接：一个指向前一个节点，当此节点为第一个节点时，指向空值；而另一个指向下一个节点，当此节点为最后一个节点时，指向空值。

双向链表

操作

  • is_empty() 链表是否为空
  • length() 链表长度
  • travel() 遍历链表
  • add(item) 链表头部添加
  • append(item) 链表尾部添加
  • insert(pos, item) 指定位置添加
  • remove(item) 删除节点
  • search(item) 查找节点是否存在

实现

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
class Node(object):
    """双向链表节点"""
    def __init__(self, item):
        self.item = item
        self.next = None
        self.prev = None


class DLinkList(object):
    """双向链表"""
    def __init__(self):
        self._head = None

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

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

    def travel(self):
        """遍历链表"""
        cur = self._head
        while cur != None:
            print cur.item,
            cur = cur.next
        print ""

    def add(self, item):
        """头部插入元素"""
        node = Node(item)
        if self.is_empty():
            # 如果是空链表，将_head指向node
            self._head = node
        else:
            # 将node的next指向_head的头节点
            node.next = self._head
            # 将_head的头节点的prev指向node
            self._head.prev = node
            # 将_head 指向node
            self._head = node

    def append(self, item):
        """尾部插入元素"""
        node = Node(item)
        if self.is_empty():
            # 如果是空链表，将_head指向node
            self._head = node
        else:
            # 移动到链表尾部
            cur = self._head
            while cur.next != None:
                cur = cur.next
            # 将尾节点cur的next指向node
            cur.next = node
            # 将node的prev指向cur
            node.prev = cur



    def search(self, item):
        """查找元素是否存在"""
        cur = self._head
        while cur != None:
            if cur.item == item:
                return True
            cur = cur.next
        return False

指定位置插入节点

双向链表指定位置插入元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def insert(self, pos, item):
    """在指定位置添加节点"""
    if pos <= 0:
        self.add(item)
    elif pos > (self.length()-1):
        self.append(item)
    else:
        node = Node(item)
        cur = self._head
        count = 0
        # 移动到指定位置的前一个位置
        while count < (pos-1):
            count += 1
            cur = cur.next
        # 将node的prev指向cur
        node.prev = cur
        # 将node的next指向cur的下一个节点
        node.next = cur.next
        # 将cur的下一个节点的prev指向node
        cur.next.prev = node
        # 将cur的next指向node
        cur.next = node

删除元素

双向链表删除节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def remove(self, item):
    """删除节点"""
    # 不按照位置删除，而是删除具体数据
    # 有两种方式(由游标决定)
    cur = self.__head
    while cur is not None:
        # 删除元素在尾部的情况也ok
        if cur.elem == item:
            # 删除元素是首节点，pre=None，判断节点是否是头节点
            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
            return
        else:
            cur = cur.next

测试

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
if __name__ == "__main__":
    ll = DoubleLinkList()
    # 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)

    # print(ll.search(1))    # True
    # print(ll.search(67))   # False
    # 8 1 2 3 4
    ll.insert(-1, 9)
    # 9 8 1 2 3 4
    ll.insert(2, 100)
    # 9 8 100 1 2 3 4
    ll.insert(10, 200)
    ll.travel()
    # 9 8 100 1 2 3 4 200
    ll.remove(9)
    ll.travel()
    # 8 100 1 2 3 4 200
    ll.remove(200)
    ll.travel()
    # 8 100 1 2 3 4
    ll.remove(400)
    ll.travel()

结果

image-20210202152018179