数据结构第三章：链表

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

例如： list = [200] —–> list = [200,400] —–>list = [200, 400, 600]

在扩充的时候，需要预估 400、600 的数据大小来申请存储空间，在进行 400 及其数据地址的搬迁和存储，那么这个时候，我们可以设想在申请 200 的存储空间时，再多出一块空间存储直接指向下一个数据的地址，这样就可以通过 200 这个数据去找到 400，而非重新检索一个新的、不相干的空间，同时在创建 400 的时候作再多一块空间出来存储 600，这样子所有的数据就都能够由最初的数据检索到。

画板

单项链表

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

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

对于元素很好理解，地址该如何理解呢？

1
2
a = 10
b = 20

在 python 中交换 a、b 变量数值操作为

1
a,b = b,a

其本质是什么呢？

在 python 当中，10 有属于自己的地址空间，而 a = 10 的意思是 a 的空间指向 10 的空间。

在执行这句话的时候，首先创建了一个存储空间 a，其空间地址为 0x21，然后将这个空间地址指向存储 10 的空间地址，是引用 10，而非赋值 10。

画板

可以这么理解，变量 a 保存的是一个地址，=相当于一个指针，这个指针使得 a 的地址指向保存 10 的地址。

因此在 python 当中，a 可以=任何东西，例如 def、class 都可以，因为是它只是一个地址的名字，它的实际储存只是一个地址。通俗讲，大家都知道南京路 108 号有一个别墅，这个时候我说我申请了一块门牌，取名为 a，门牌地址是南京路 108 号，于是大家就明白了 a 这个地方是一个别墅，但其实呢，a 就是一个门牌，门牌储存了一个地址，这个地址上是一个别墅，但是你不能说我的 a 上面建了一个别墅，它是门牌，只是我的门牌地址指向一个别墅罢了。

明白了这个之后，就可以明白链表是怎么运作的

画板

next = node2 这一步的意思就是，next 这个存储空间存储的地址是指向 node2 的地址。

节点的创建方式：

1
2
3
4
5
6
7
class SingleNode(object):
    """单链表的结点"""
    def __init__(self,item):
        # item存放数据元素
        self.item = item
        # next是下一个节点的标识，在初始化的时候指向none
        self.next = None

通过以上创建 node = SingleNode(100) 时，会创建 | 100 | none | 这样一个数据。

我们需要的单链表的操作：

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

在此，我们构建的 SingleLinkList 是一种新的数据类型，在使用该新数据类型的时候，相当于创建一个该数据类型的对象。例如：single_obj = SingleLinkList() =====> li = List()

li、single_obj 都是具体的对象，而 SingleLinkList、List 都是类，是数据类型，是抽象的，不具体的。所以，在其中每一个链表的头节点都应该是一个对象属性， init 方法中 self.head 指向 none。而在完成了初始化之后，我们这个对象的的属性必须只能用自己内部的 def 使用，于是要用** _head 表示私有**。

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
class SingleLinkList(object):
    """单链表"""
    def __init__(self):
        self._head = None

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

    def length(self):
        """链表长度"""
        # 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 = cur.next
        print("Done!")


头部添加元素

1
2
3
4
5
6
7
8
def add(self, item):
    """头部添加元素"""
    # 先创建一个保存item值的节点
    node = SingleNode(item)
    # 将新节点的链接域next指向原头节点，即_head指向的位置
    node.next = self._head
    # 将链表的头_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
def insert(self, pos, item):
    """指定位置添加元素"""
    # 若指定位置pos为第一个元素之前，则执行头部插入
    if pos <= 0:
        self.add(item)
    # 若指定位置超过链表尾部，则执行尾部插入
    elif pos > (self.length()-1):
        self.append(item)
    # 找到指定位置
    else:
        node = SingleNode(item)
        count = 0
        # pre用来指向指定位置pos的前一个位置pos-1，初始从头节点开始移动到指定位置
        pre = self._head
        while count < (pos-1):
            count += 1
            pre = pre.next
        # 先将新节点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
def remove(self,item):
    """删除节点"""
    cur = self._head
    pre = None
    while cur != None:
        # 找到了指定元素
        if cur.item == item:
            # 如果第一个就是删除的节点
            if not pre:
                # 将头指针指向头节点的后一个节点
                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
def search(self,item):
    """链表查找节点是否存在，并返回True或者False"""
    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
23
24
25
26
27
28
29
30
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()

'''
结果
length: 4
2
1
4
3
Done!
True
False
length: 3
2
4
3
Done!
'''

链表与顺序表对比

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

为什么我们要用链表呢？

在使用链表的时候，存储的数据内存是连续的，假如我们有一堆庞大的数据，在常规读取的时候，分配的内存是离散的，这个时候要对这些庞大数据进行读取和操作，就很慢，而用链表储存数据时，能够将这些离散的内存地址连续串起来，这样计算机在读取你的数据时，就不用检索很久，只要找到链表的任意数据的任意内存位置，就能够对其他数据位置进行定位，从而直接检索查到，这样读取数据就会快很多。

对于插入/删除，随然链表和顺序表时间复杂度都是 O(n)，但是两个 n 是不一样的。对于链表，n 是用在了遍历上，而对于顺序表，n 是用在 了数据搬迁上。

双向链表

相对于单向链表，双向链表在于，每个节点申请如上三个存储空间，并且把第一个块空间用来指向前一个节点。

操作：

  • 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
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("")

上面这段代码与单向链表是一致的，可以通过 DLinkList(SingleLinkList) 来继承，这样就不用写这一段代码了。

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
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
24
25
def remove(self, item):
    """删除元素"""
    if self.is_empty():
        return
    else:
        cur = self._head
        if cur.item == item:
            # 如果首节点的元素即是要删除的元素
            if cur.next == None:
                # 如果链表只有这一个节点
                self._head = None
            else:
                # 将第二个节点的prev设置为None
                cur.next.prev = None
                # 将_head指向第二个节点
                self._head = cur.next
            return
        while cur != None:
            if cur.item == item:
                # 将cur的前一个节点的next指向cur的后一个节点
                cur.prev.next = cur.next
                # 将cur的后一个节点的prev指向cur的前一个节点
                cur.next.prev = cur.prev
                break
            cur = cur.next

单向循环链表

单链表的一个变形是单向循环链表，链表中最后一个节点的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
class Node(object):
    """节点"""
    def __init__(self, item):
        self.item = item
        self.next = None


class SinCycLinkedlist(object, node=None):
    """单向循环链表"""
    def __init__(self):
        self._head = node
        if node:
            node.next = node
        
    def is_empty(self):
        """判断链表是否为空"""
        return self._head == None

    def length(self):
        """返回链表的长度"""
        # 如果链表为空，返回长度0
        if self.is_empty():
            return 0
        count = 1
        cur = self._head
        while cur.next != self._head:
            count += 1
            cur = cur.next
        return count

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


    def add(self, item):
        """头部添加节点"""
        node = Node(item)
        if self.is_empty():
            self._head = node
            node.next = self._head
        else:
            #添加的节点指向_head
            node.next = self._head
            # 移到链表尾部，将尾部节点的next指向node
            cur = self._head
            while cur.next != self._head:
                cur = cur.next
            cur.next = node
            #_head指向添加node的
            self._head = node

    def append(self, item):
        """尾部添加节点"""
        node = Node(item)
        if self.is_empty():
            self._head = node
            node.next = self._head
        else:
            # 移到链表尾部
            cur = self._head
            while cur.next != self._head:
                cur = cur.next
            # 将尾节点指向node
            cur.next = node
            # 将node指向头节点_head
            node.next = self._head

    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.next = cur.next
            cur.next = node

    def remove(self, item):
        """删除一个节点"""
        # 若链表为空，则直接返回
        if self.is_empty():
            return
        # 将cur指向头节点
        cur = self._head
        pre = None
        # 若头节点的元素就是要查找的元素item
        if cur.item == item:
            # 如果链表不止一个节点
            if cur.next != self._head:
                # 先找到尾节点，将尾节点的next指向第二个节点
                while cur.next != self._head:
                    cur = cur.next
                # cur指向了尾节点
                cur.next = self._head.next
                self._head = self._head.next
            else:
                # 链表只有一个节点
                self._head = None
        else:
            pre = self._head
            # 第一个节点不是要删除的
            while cur.next != self._head:
                # 找到了要删除的元素
                if cur.item == item:
                    # 删除
                    pre.next = cur.next
                    return
                else:
                    pre = cur
                    cur = cur.next
            # cur 指向尾节点
            if cur.item == item:
                # 尾部删除
                pre.next = cur.next

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

单向循环链表区别于单向链表的实现方式的关键在于找尾部节点的方式不同，单向链表尾部节点指向 none，而单向循环链表的尾部节点指向头节点。

数据结构与算法
#数据结构与算法 #Python
数据结构第三章：链表
http://baikelwang.github.io/2025/07/15/数据结构第三章：链表/
作者
北海
发布于
2025年7月15日
许可协议