蒙珣的博客

活好当下，做好今天该做的事情。

0%

链表

Posted on Edited on In
Symbols count in article: 9.2k Reading time ≈ 8 mins.

链表(linked_list)是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，每个元素包含两个结点，一个是存储元素的数据域 (内存空间)，另一个是指向下一个结点地址的指针域。根据指针的指向，链表能形成不同的结构，例如单链表，双向链表，循环链表等。

链表通过将链点 i 与其邻居链点 i+1 通过指针相关联，从索引 0 到索引 N-1 对链点进行排序。

单链表

链表分为单链表和双链表两种。在接下来的内容里，我们将逐步介绍单链表的具体功能是如何实现的。

1. 创建 Node 类

创建一个 Node 的类，作为基础数据结构：链点，并初始化对应的内参。

具体实现代码如下：

1
2
3
4
class Node:
    def __init__(self, data):
        self.data = data  # 表示对应的元素值
        self.next = None  # 表示下一个链接的链点

2. 创建 Linked_List 类

创建一个 Linked_List 的类，并初始化对应的内参。

具体实现代码如下：

1
2
3
class Linked_List:
    def __init__(self, head=None):  # 链表初始化函数
        self.head = head  # 表示链表的头部元素

3. 添加 append 函数

添加一个 append 的函数，功能是向链表添加新的结点

具体实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
def append(self, new_element):
    # 将头部结点指向临时变量 current
    current = self.head
    # 当头部结点存在时
    if self.head:
        # 循环遍历到链表的最后一个元素
        while current.next:
            current = current.next
        current.next = new_element
    # 当头部结点不存在时
    else:
        self.head = new_element

4. 添加 is_empty 函数

添加一个 is_empty 的函数，功能是判断链表是否为空

具体实现代码如下：

1
2
3
4
5
6
def is_empty(self):
    """
    判断链表是否为空
    """
    # bool() 函数只返回 True 和 False
    return not self.head

5. 添加 insert 函数

insert(new_element) 往链表中任意位置添加一个 new_element 元素

流程如下：

  1. 先判断要插入的位置是否在链表的索引范围内。
  2. 当插入的位置是头结点（即索引为 0）时，做特殊情况处理。
  3. 当要插入结点的位置不在 0 时，找到要插入的位置，插入新结点

具体实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def insert(self, position, new_element):
    """
    在链表中指定索引处插入元素
    """
    if position < 0 or position > self.get_length():
        raise IndexError('insert 插入时,key 的值超出了范围')
    temp = self.head
    # 将插入元素的 next 属性指向老的头结点，并将新的元素赋值给头结点
    if position == 0:
        new_element.next = temp
        self.head = new_element
        # new_element.next, self.head = temp, new_element
        return
    i = 0
    # 遍历找到索引值为 position 的结点后, 在其后面插入结点
    while i < position:
        pre = temp
        temp = temp.next
        # pre, temp = temp, temp.next
        i += 1
    pre.next = new_element
    new_element.next = temp
    # pre.next, new_element.next = new_element, temp

6. 添加 remove 函数

remove() 从链表中任意位置删除一个元素

流程如下：

  1. 先判断要删除的元素索引是否存在，如果不存在抛出错误
  2. 接着判断当存在链表元素时才能执行删除操作。
  3. 当要删除的是头结点时（即索引为 0），做特殊情况处理。
  4. 其他情况时，通过循环找到要删除的结点。
  5. 最后要做的就是把这个结点删除掉。

具体实现代码如下：

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
def remove(self, position):
    """
    删除指定索引的链表元素
    """
    if position < 0 or position > self.get_length()-1:
        # print("insert error")
        raise IndexError('删除元素的索引超出范围')

    i = 0
    temp = self.head
    # 当存在链表元素时才能执行删除操作
    while temp != None:
        # 将头结点的后一个结点赋值给新的头结点，再将之前的头结点指向 `None`
        if position == 0:
            self.head = temp.next
            temp.next = None
            return

        pre = temp
        # 以此来遍历链表
        temp = temp.next
        # pre, temp = temp, temp.next
        i += 1
        if i == position:
            # 将 pre 的 next 属性指向 temp 的下一个结点
            pre.next = temp.next
            temp.next = None
            # pre.next, temp.next = temp.next, None
            return

7. 添加其他函数

get_length:获取链表的长度

print_list:遍历链表，并将元素依次打印出来

reverse:将链表反转

initlist: 将列表转换为链表

具体实现代码如下：

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
def get_length(self):
    """
    返回链表的长度
    """
    头部结点赋值给头部结点
    temp = self.head
    # 计算链表的长度变量
    length = 0
    while temp != None:
        length = length+1
        temp = temp.next
    # 返回链表的长度
    return length

def print_list(self):
    """
    遍历链表，并将元素依次打印出来
    """
    print("linked_list:")
    # 头部结点赋值给临时变量 temp
    temp = self.head
    while temp is not None:
        print(temp.data)
        temp = temp.next

def reverse(self):
    """
    将链表反转
    """
    prev = None
    current = self.head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    self.head = prev

def initlist(self,data_list):
    """
    将列表转换为链表
    """
    # 创建头结点
    self.head = Node(data_list[0])
    temp = self.head
    # 逐个为 data 内的数据创建结点, 建立链表
    for i in data_list[1:]:
        node = Node(i)
        temp.next = node
        temp = temp.next

基于链表的基本功能介绍，我们给出链表的完整代码

在/home/shiyanlou/下新建一个文件linked_list.py。

具体实现代码如下：

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
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class Linked_List:
    def __init__(self, head=None):
        self.head = head

    def append(self, new_element):
        """
        在链表后面增加一个元素
        """
        current = self.head
        if self.head:
            while current.next:
                current = current.next
            current.next = new_element
        else:
            self.head = new_element

    def is_empty(self):
        """
        判断链表是否为空
        """
        return not self.head

    def get_length(self):
        """
        获取链表的长度
        """
        # 临时变量指向队列头部
        temp = self.head
        # 计算链表的长度变量
        length = 0
        while temp != None:
            length = length+1
            temp = temp.next
        # 返回链表的长度
        return length

    def insert(self, position, new_element):
        """
        在链表中指定索引处插入元素
        """
        if position < 0 or position > self.get_length():
            raise IndexError('insert 插入时,key 的值超出了范围')
        temp = self.head
        if position == 0:
            # new_element.next = temp
            # self.head = new_element
            new_element.next, self.head = temp, new_element
            return
        i = 0
        # 遍历找到索引值为 position 的结点后, 在其后面插入结点
        while i < position:
            # pre = temp
            # temp = temp.next
            pre, temp = temp, temp.next
            i += 1
        # pre.next = node
        # node.next = temp
        pre.next, new_element.next = new_element, temp

    def print_list(self):
        """
        遍历链表，并将元素依次打印出来
        """
        print("linked_list:")
        temp = self.head
        new_list = []
        while temp is not None:
            new_list.append(temp.data)
            temp = temp.next
        print(new_list)

    def remove(self, position):
        """
        删除指定索引的链表元素
        """
        if position < 0 or position > self.get_length()-1:
            # print("insert error")
            raise IndexError('删除元素的位置超出范围')

        i = 0
        temp = self.head
        # 遍历找到索引值为 position 的结点
        while temp != None:
            if position == 0:
                self.head = temp.next
                temp.next = None
                return True
            # pre = temp
            # temp = temp.next
            pre, temp = temp, temp.next

            i += 1
            if i == position:
                # pre.next = temp.next
                # temp.next = None
                pre.next, temp.next = temp.next, None
                return

    def reverse(self):
        """
        将链表反转
        """
        prev = None
        current = self.head
        while current:
            # next_node = current.next
            # current.next = prev
            # prev = current
            # current = next_node
            next_node, current.next = current.next, prev
            prev, current = current, next_node
        self.head = prev

    def initlist(self, data_list):
        “”“
        将列表转换为链表
        ”“”
        # 创建头结点
        self.head = Node(data_list[0])
        temp = self.head
        # 逐个为 data 内的数据创建结点, 建立链表
        for i in data_list[1:]:
            node = Node(i)
            temp.next = node
            temp = temp.next

复杂度分析

链表属于常见的一种线性结构，对于插入和移除而言，时间复杂度都为 O(1)

但是对于搜索操作而言，不管从链表的头部还是尾部，都需要遍历 O(n)，所以最好复杂度为 O(1)，最坏的情况就是从头部遍历到尾部才搜索出对应的元素，所以最坏复杂度为 O(n)，平均复杂度为 O(n)。

归纳如下：

  • 最好复杂度为 O(1)
  • 最坏复杂度为 O(n)
  • 平均复杂度为 O(n)

双链表

双向链表（Double_linked_list）也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

这里直接给出参考代码，大家有兴趣请自行探索，这里就不再详细介绍。

具体实现代码如下：

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
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 get_length(self):
        # 返回链表的长度
        cur = self._head
        count = 0
        while cur != None:
            count = 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():
            # 如果是空链表，将 node 赋值给 _head
            self._head = node
        else:
            # 将 node 的 next 属性指向头节点 _head
            node.next = self._head
            # 将头节点 _head 的 prev 属性指向 node
            self._head.prev = node
            # 将 node 赋值给 _head
            self._head = node

    def append(self, item):
        # 尾部插入元素
        node = Node(item)
        if self.is_empty():
            # 如果是空链表，将 node 赋值给 _head
            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

    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

    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

交换单链表里两个链点

在这个实验中，我们要给定两个值，如果这两个值都在单链表的链点中，即交换这两个链点在单链表的位置。

举例：

1->2->3->4->5

input:1 4 output:4->2->3->1->5

目标：

  1. 交换两个链点在链表中的位置
  2. 不改变其他链点在链表中的位置

思路：

  • 采用 insert 的思想，对于要交换的两个链点 d1 d2，各自声明新的 D1 D2 ，使 D1=d1, D2=d2
  • 然后把 然后再根据 d1 d2 的位置，改变索引的位置，即完成交换的全部操作

参考代码

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
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class Linkedlist:
    def __init__(self):
        self.head = None

    def print_list(self):  # 遍历链表，并将元素依次打印出来
        print("linked_list:")
        temp = self.head
        new_list = []
        while temp is not None:
            new_list.append(temp.data)
            temp = temp.next
        print(new_list)

    def insert(self, new_data):
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node

    def swapNodes(self, d1, d2):
        prevD1 = None
        prevD2 = None
        if d1 == d2:
            return
        else:
            D1 = self.head
            while D1 is not None and D1.data != d1:
                prevD1 = D1
                D1 = D1.next
            D2 = self.head
            while D2 is not None and D2.data != d2:
                prevD2 = D2
                D2 = D2.next
            if D1 is None and D2 is None:
                return
            if prevD1 is not None:
                prevD1.next = D2
            else:
                self.head = D2
            if prevD2 is not None:
                prevD2.next = D1
            else:
                self.head = D1
            temp = D1.next
            D1.next = D2.next
            D2.next = temp


if __name__ == '__main__':
    list = Linkedlist()
    list.insert(5)
    list.insert(4)
    list.insert(3)
    list.insert(2)
    list.insert(1)
    list.print_list()
    list.swapNodes(1, 4)
    print("After swapping")
    list.print_list()