数据结构与算法之Python实现——单链表

🍁 简述链表

什么是链表？

拿顺序表做个对比，顺序表是把数据存储在一个“整体”里面，而链表则是将每个数据分割开，每一个数据元素就是一个“整体”，如下图：
链表中分割后的多个整体之间通过某种方式将它们连起来，这里把“连”改为指向，也就是一个整体“指向”另一个整体，这也是符合顺序表的“先后关系”的。可以说，链表是一种另类的“顺序”表，它更加灵活多变。

为什么要学习链表？

相较于顺序表，链表肯定是有更突出的优点，不然咱学它干嘛呢？

由顺序表的特点我们可以知道，在对顺序表进行插入元素时，若在表中间插入，那么我们就需要将插入位置的元素及它后面的全部元素都往后移一位，删除元素的操作也是如此。

然而，链表的优点正是在此，它插入元素、删除元素最多只需涉及到原链表中的两个数据，十分方便。

但是，它也有自己的缺点，就是存储空间开销大，且不能按下标对数据元素进行操作，只能从表头开始，一个一个往下找。

链表的类型

• 单链表
• 循环链表
• 双向链表

本篇博客就对单链表的学习做一个记录＾∀＾

🍁 单链表

由上述可知，对于单链表中一个一个的“整体”，我们将它定义为结点。而一个结点中肯定要有存储的数据的值，并且还需要有一个东西来表示它指向的下一个结点，我们将这个东西定义为指针。而链表中包含的就是一个一个链接起来的结点，所以只需在表结构中定义一个初始结点即可，由这一个结点指向下一个结点，再由下一个结点指向下下个结点，由此反复…。并且将这个初始结点称为头结点。

如下：

# The structure of node ——结点的结构
class LNode:                                       
    def __init__(self, elem, next_ = None):
        self.elem = elem     					# Data field ——数据域，用来存储“值”                       
        self.next_ = next_     					# Pointer field ——指针域，用来指示下一个结点                     

# The structure of linked list ——链表的结构
class LList:                                        
    def __init__(self):
        self.head = None                  		# Head node ——头结点          
1
2
3
4
5
6
7
8
9
10

然后就是与链表操作相关的函数了，因为是针对于链表的操作，所以这些函数就定义在链表的结构中了。下面一一介绍。

🍃 三种插入方法

🍂 头插法

    def insert_head(self, elem):
        # Create a new node ——创建一个新的结点
        node = LNode(elem)
        # If head node is None,assign the new node to head node ——如果头结点为空，将新结点赋给头结点
        if self.head == None:
            self.head = node
        else:
            # Make new node points to the head node
            # 让新创建的结点指向头结点
            node.next_ = self.head
            # Make the head node points to the new node
            # 让头结点指向新结点
            self.head = node
1
2
3
4
5
6
7
8
9
10
11
12
13

🍂 尾插法

    def insert_tail(self, elem):
        # Create a new node
        node = LNode(elem)
        # If head node is None,assign new node to head node
        # 如果头结点为空，将新结点赋给头结点
        if self.head is None:
            self.head = node
        # If head node isn't None ——如果头结点不为空
        else:
            # Replace head node with cur ——用cur来代替头结点，也就是说保持头结点head node 不动，用其它变量来顺着链表往下遍历，直到遍历到符合条件或空的位置为止
            # Make cur points to head node ——让cur指向头结点
            cur = self.head
            # Fine cur that cur.next is Node ——cur指向下一结点为空的结点
            while cur.next_ is not None:
                cur = cur.next_
            # Assign new node to cur.next ——将新结点赋给cur的下一结点
            cur.next_ = node
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

🍂 一般插法

    def insert_general(self, pos, elem):
        node = LNode(elem)
        # If add new data on position 0 ——如果在0号位置添加新元素
        if pos == 0:
            # Make new node points to head node ——让新结点指向头结点
            node.next_ = self.head
            # Make new node be head node ——让新结点成为头结点
            self.head = node
            return
        # Counter ——计数器
        count = 0
        cur = self.head
        # Fine the position before the position you want to insert
        # 找到你想插入位置的前一个位置
        while count < pos - 1:
            cur = cur.next_
            count += 1
        # Make the new node points the next node of cur ——让新结点指向cur的下一个结点
        node.next_ = cur.next_
        # Make cur points to new node ——让cur指向新结点
        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 length(self):
        # Counter,denotes the length of the list ——计数器，用来指示链表的长度
        count = 0
        cur = self.head
        while cur is not None:
            cur = cur.next_
            count += 1
        return count
1
2
3
4
5
6
7
8

🍃 删除链表中的数据

    def delete(self,pos):
        # Delete head node ——删除头结点
        if pos == 0:
            # Make the node after head node be the head node ——让头结点的下一个结点成为头结点
            self.head = self.head.next_
        else:
            count = 0
            cur = self.head
           # Find the position of the node before the node you want to delete ——找到你想删除结点的前一个结点的位置
            while count < pos - 1:
                cur = cur.next_
                count += 1
            # Make the node points to the node after the node you want to delete ——让这个结点指向被删除结点的下一个结点，也就指向下下个结点
            cur.next_ = cur.next_.next_
1
2
3
4
5
6
7
8
9
10
11
12
13
14

提问：Python中有指针吗？

• 答：Python中没有像C、C++那样的指针，只是用到了指针的思想。就我个人理解，对于如下语句

a = 1
1

一般来说是将1赋值给了a这个变量，但在python中我们可以理解为由变量a指向了1。用这样的思想，在学习链表时就会轻松许多。

提问：链表操作中结点的“=”到底是赋值还是“指向”的意思？

• 答：例如如下语句

cur = self.head
1

就一般来看，是将self.head赋值给了cur，那么cur=cur.next_就是将cur的下一个结点赋值给cur。

如果用指针的思想理解一下，就是cur指向了self.head，cur=cur.next_就是使cur指向了cur的下一个结点。

所以你可以认为“=”是赋值的意思，也可以认为是“指向”的意思，只要自己能理解那个点就好。

我个人对于python中变量的描述可能不太准确，只是想说一说我自己对python中链表的理解

🍃 单链表的实现（总代码）

class LNode:                                        
    def __init__(self, elem, next_ = None):
        self.elem = elem                           
        self.next_ = next_                          

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

    def insert_head(self, elem):
        node = LNode(elem)
        if self.head == None:
            self.head = node
        else:
            node.next_ = self.head
            self.head = node

    def insert_tail(self, elem):
        node = LNode(elem)
        if self.head is None:
            self.head = node
        else:
            cur = self.head
            while cur.next_ is not None:
                cur = cur.next_
            cur.next_ = node

    def insert_general(self, pos, elem):
        node = LNode(elem)
        if pos == 0:
            node.next_ = self.head
            self.head = node
            return
        count = 0
        cur = self.head
        while count < pos - 1:
            cur = cur.next_
            count += 1
        node.next_ = cur.next_
        cur.next_ = node

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

    def delete(self,pos):
        if pos == 0:
            self.head = self.head.next_
        else:
            count = 0
            cur = self.head
            while count < pos - 1:
                cur = cur.next_
                count += 1
            cur.next_ = cur.next_.next_

# 请输入一串数据，并将每个数据以空格隔开
data = list(map(int,input('Please input a series of datas and split them by spaces:').split()))
# The datas will be stored in the list 'data' ——输入的数据将会存储在data这个列表中
print('The list is :')
print(data)
# 开始创建链表
print('Starting to build the linked list----------------------------------------')
l = LList()
# Through tail insertion to create the linked list ——通过尾插法创建链表
for i in range(len(data)):
    l.insert_tail(data[i])
# The data of the linked list is ——链表中的数据是：
print('The linked list is:')
cur = l.head
for i in range(l.length()):
    print(cur.elem)
    cur = cur.next_
# Operations to the linked list ——对链表的增删操作
while True:
    # First is the adding operation ——首先是增加操作
    ans = input("Do you want to add data?Please input 'y'(yes) or 'n'(no):")
    if ans == 'y':
        new_data = int(input("Please input the data you want to add:"))
        pos = int(input("Please input the position that you want to inset:"))
        l.insert_general(pos,new_data)

        print("The linked list after you add new data is:")
        cur1 = l.head
        for i in range(l.length()):
            print(cur1.elem)
            cur1 = cur1.next_

    # Second is the deleting operation ——然后是删除操作
    ans = input("Do you want to delete data?Please input 'y'(yes) or 'n'(no):")
    if ans == 'y':
        pos = int(input("Please input the position of the data you want to delete:"))
        l.delete(pos)
        print("The linked list after you delete centain is:")
        cur2 = l.head
        for i in range(l.length()):
            print(cur2.elem)
            cur2 = cur2.next_


    sign = input("If you want to end up modifying ? If so,input '#';else,input '$':")
    if sign == '#':
        break
print("The operation of the linked list ends.")
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

执行结果为：

注：链表还有其它很多的操作，例如查找、判断是否为空等等，可以自己试着写一写，也不太难。上面的代码还是比较有局限性的，我也只是用整型来做一个测试，供大家参考~~

单链表的学习就到这里，下期将会学习循环链表与双向链表。

如有不足之处，希望大家多多指正。