〇. 目录
一. 链表的基本概念
- 链表是比较重要的结构化数据类型，也是经典的线性表。链表是动态数据结构，它使用不连续的内存空间存储数据，具有线性的特性。
- 优点：数据插入和删除操作比较方便，不需要移动大量的数据；链表的内存分配是在程序运行过程中完成的，不需要事先声明，能节省内存。
- 缺点：设计数据结构比较麻烦，在查找数据时不能随机读取，需要按顺序查找数据
二. 创建单项列表
-
观察项链，会发现链的特点是一环扣一环，上一环尾部扣着下一环头部。其中的连接点，即上一环尾部扣着下一环头部的点，称其为结点。
-
链表的结构与此类似。编程语言中，链表是由一组称为结点的数据元素组成的数据结构。例如，创建一个“学生”链表，其中包括多个学生的姓名、性别、学号等基本信息。
-
学生一的尾结点next指向了学生二的头结点（学号那栏），这就是链表的特性，即上一个信息的尾结点next会指向下一个结点的内存地址。由于每个结点都包含了可以链接起来的地址信息，所以用一个变量就能够访问整个结点序列。
-
在以上的描述中出现了两个词“指向”和“地址”，学习过C语言的读者可能会知道，这是典型的指针术语。
-
在C语言中，可以使用指针来创建链表，但是在Python中并没有指针的概念，应该怎样创建链表呢？
-
我们先来看一下Python中是如何交换两个值的。首先是定义两个变量，代码如下：
x = 1
y = 2
Python中交换两个变量的代码如下：
x, y = y, x
注意，在Python中交换值可以这样写，在别的语言中却不可以。这是因为在Python中，定义x=1时，系统除了会开辟一块内存给1这个值，还会开辟一块内存用于存储1的地址，这块称之为x。类似地，定义y=2时，除了会开辟一块内存以保存2的值之外，还会开辟一块内存用于存储2的地址，这块称之为y。所以说，在Python中交换两个数的值时，其实是地址的指向发生了转换，类似于C语言中的指针。
- 接下来用Python代码创建一个单项列表
class Node():
def __init__(self):
self.item = '' # 元素
self.next = None # 指针
2.1 实例：创建学生列表
class Node():
def __init__(self):
self.name = '' # 姓名
self.sex = '' # 性别
self.index = '' # 学号
self.next = None # 指针
student = Node() # 初始化表头
key = student # key相当于“指针”
flag = 'y'
while flag == 'y': # 循环输入一些学生数据
name = input('Please input name:')
sex = input('Please input sex(man:1;woman:2):')
index = input('Please input index:')
key.name = name # 将数据放入
key.sex = sex
key.index = index
new_data = Node()
key.next = new_data # 末尾指针指向新的空间
key = key.next # 将指针向后移
flag = input('if continue,input"y".')
# 将列表内容输出
key = student
while key.next != None:
print(f'name:{key.name}\tsex:{key.sex}\tindex:{key.index}')
key = key.next
Please input name:aaa
Please input sex(man:1;woman:2):1
Please input index:01
if continue,input"y".y
Please input name:bbb
Please input sex(man:1;woman:2):2
Please input index:02
if continue,input"y".y
Please input name:ccc
Please input sex(man:1;woman:2):1
Please input index:03
if continue,input"y".y
Please input name:ddd
Please input sex(man:1;woman:2):1
Please input index:04
if continue,input"y".n
name:aaa sex:1 index:01
name:bbb sex:2 index:02
name:ccc sex:1 index:03
name:ddd sex:1 index:04
三. 单项列表的操作
3.1 链表的基本操作
- 创建链表
class Node():
def __init__(self, elem):
self.elem = elem
self.next = None
- 创建链表类，并定义一些链表操作功能
class LinkList():
def __init__(self, node=None):
self.__head = node # 标明头结点的位置
# 判断链表是否为空
def is_empty(self):
return self.__head == None
# 计算链表长度
def LinkList_length(self):
key = self.__head # key为“指针”
count = 0 # count记录数量
while key != None:
count += 1
key = key.next
return count
# 遍历整个列表
def LinkList_travel(self):
key = self.__head
while key != None:
print(key.elem, end='\t')
key = key.next
3.2 单项列表中的结点添加
- 在单向链表中添加结点，包括在头结点处添加结点（头插法）、在尾结点处添加结点（尾插法），以及在中间位置添加结点3种方式。
3.2.1 在头结点处添加结点
- 要想在学生一结点前添加一个新的学生结点，需将头结点变成新添加的学生结点，新添加学生结点的next指针指向学生一结点的地址。
def add(self, item):
new = Node(item) # 添加新数据
new.next = self.__head # 将新数据的末尾指向原链表头
self.__head = new # 将头结点指向新数据节点
3.2.2 在尾结点处添加结点
- 要想在尾结点处添加一个新结点，需将学生四结点的next指针指向新添加的学生结点，将新添加学生结点指向none。
def append(self, item):
new = Node(item) # 添加新数据
if self.is_empty(): # 若原先链表为空，则直接将头结点改为新数据
self.__head = new
else: # 否则先遍历链表，找到最后一个，将新数据加入
key = self.__head
while key.next != None:
key = key.next
key.next = new
3.2.3 在中间位置添加结点
- 要想在学生二和学生三之间添加一个新结点，需将学生二结点指向新学生结点，然后将新学生结点指向学生三结点。
def insert(self, pos, item):
"""
pos:插入位置
item:数据
"""
if pos <= 0: # 若插入的位置索引小于0，则按头结点插入法进行添加；
self.add(item)
elif pos >self.LinkList_length() - 1: # 若插入的位置索引大于，则按尾结点插入法进行添加；
self.append(item)
else: # 否则按照中间插入法
new = Node(item)
key = self.__head
count = 0
while count < (pos - 1):
key = key.next
count += 1
new.next = key.next # 遍历到该插入的位置后，使新数据的next指向后方链表；同时改变指针指向新元素
key.next = new
3.2.4 案例测试（添加结点）
# 定义结点类
class Node():
def __init__(self, elem):
self.elem = elem
self.next = None
# 定义链表类
class LinkList():
def __init__(self, node=None):
self.__head = node # 标明头结点的位置
# 判断链表是否为空
def is_empty(self):
return self.__head == None
# 计算链表长度
def LinkList_length(self):
key = self.__head # key为“指针”
count = 0 # count记录数量
while key != None:
count += 1
key = key.next
return count
# 遍历整个列表
def LinkList_travel(self):
key = self.__head
while key != None:
print(key.elem, end='\t')
key = key.next
# 在头结点处添加结点
def add(self, item):
new = Node(item) # 添加新数据
new.next = self.__head # 将新数据的末尾指向原链表头
self.__head = new # 将头结点指向新数据节点
# 在尾结点处添加结点
def append(self, item):
new = Node(item) # 添加新数据
if self.is_empty(): # 若原先链表为空，则直接将头结点改为新数据
self.__head = new
else: # 否则先遍历链表，找到最后一个，将新数据加入
key = self.__head
while key.next != None:
key = key.next
key.next = new
# 在中间位置添加结点
def insert(self, pos, item):
"""
pos:插入位置
item:数据
"""
if pos <= 0: # 若插入的位置索引小于0，则按头结点插入法进行添加；
self.add(item)
elif pos >self.LinkList_length() - 1: # 若插入的位置索引大于，则按尾结点插入法进行添加；
self.append(item)
else: # 否则按照中间插入法
new = Node(item)
key = self.__head
count = 0
while count < (pos - 1):
key = key.next
count += 1
new.next = key.next # 遍历到该插入的位置后，使新数据的next指向后方链表；同时改变指针指向新元素
key.next = new
LinkList_demo = LinkList() # 初始化
LinkList_demo.add(25) # 在头结点处添加结点
LinkList_demo.add(10) # 在头结点处添加结点
LinkList_demo.append(39) # 在尾结点处添加结点
LinkList_demo.insert(2, 49) # 在第2个结点处添加结点
LinkList_demo.insert(4, 54) # 在第4个结点处添加结点
# 调用函数，分别输出链表长度和链表的数据
print(f'the length of the link:{LinkList_demo.LinkList_length()}')
LinkList_demo.LinkList_travel()
the length of the link:5
10 25 49 39 54
3.3 单项列表中结点的删除
- 在单项列表类型的数据结构中，删除结点和添加结点相同，也分为3中不同情况
3.3.1 删除头结点
- 要想把学生一结点删除，只需把学生二结点变成头结点（head）。
3.3.2 删除尾结点
- 要想删除学生四结点，只需把倒数第二个结点（即学生三结点）指向None。
3.3.3 删除中间结点
- 要想删除学生三结点，需要将其前一个结点p（即学生二结点）指向学生四结点。
3.3.4 案例测试（删除结点）
# 定义结点类
class Node():
def __init__(self):
self.name = ''
self.sex = ''
self.index = ''
self.next = None
# 定义链表类
class LinkList():
def __init__(self):
self.__head = None
# 添加结点
def append(self, item_lst):
new_data = Node()
new_data.name = item_lst[1]
new_data.sex = item_lst[2]
new_data.index = item_lst[0]
if self.__head == None:
self.__head = new_data
else:
p = self.__head
while p.next != None:
p = p.next
p.next = new_data
# 遍历整个列表
def LinkList_travel(self):
key = self.__head
while key != None:
print(key.index, key.name, key.sex)
key = key.next
# 删除结点
def del_ptr(self, ptr):
# 在头部新加一个结点
none = Node()
none.next = self.__head
self.__head = none
p = self.__head # 增加指针
while p != None:
q = p.next # q用来标记p的下一个结点。当q是要删除的，则让p原先链接q的指针指向q的后一个结点
if q.index == ptr:
p.next = q.next
# q.next = None
break
p = p.next
p = self.__head # 将先前后加的结点删除
self.__head = p.next
# 初始化案例
LinkList_demo = LinkList()
LinkList_demo.append(['01', 'Luca1', 'man'])
LinkList_demo.append(['02', 'Luca2', 'woman'])
LinkList_demo.append(['03', 'Luca3', 'man'])
LinkList_demo.append(['04', 'Luca4', 'man'])
LinkList_demo.append(['05', 'Luca5', 'woman'])
LinkList_demo.append(['06', 'Luca6', 'man'])
LinkList_demo.append(['07', 'Luca7', 'man'])
LinkList_demo.append(['08', 'Luca8', 'woman'])
# 调用函数，输出链表的数据
LinkList_demo.LinkList_travel()
LinkList_demo.del_ptr('01') # 删除头结点
LinkList_demo.del_ptr('04') # 删除尾结点
LinkList_demo.del_ptr('08') # 删除中间结点
print('-' * 10 + 'After' + '-' * 10)
# 输出处理后的链表的数据
LinkList_demo.LinkList_travel()
01 Luca1 man
02 Luca2 woman
03 Luca3 man
04 Luca4 man
05 Luca5 woman
06 Luca6 man
07 Luca7 man
08 Luca8 woman
----------After----------
02 Luca2 woman
03 Luca3 man
05 Luca5 woman
06 Luca6 man
07 Luca7 man
3.4 单向链表链接
- 连接两个链表，类似于连接两个字符串。
- 找到第一个链表的尾结点，使其链接到第二个链表的头结点
def connect_list(self, head2):
p = self.head
while p.next != None:
p = p.next
p.next = head2
3.4.1 案例测试（链表链接）
# 定义结点类
class Node():
def __init__(self):
self.name = ''
self.sex = ''
self.index = ''
self.next = None
# 定义链表类
class LinkList():
def __init__(self):
self.head = None
# 添加结点
def append(self, item_lst):
new_data = Node()
new_data.name = item_lst[1]
new_data.sex = item_lst[2]
new_data.index = item_lst[0]
if self.head == None:
self.head = new_data
else:
p = self.head
while p.next != None:
p = p.next
p.next = new_data
# 遍历整个列表
def LinkList_travel(self):
key = self.head
while key != None:
print(key.index, key.name, key.sex)
key = key.next
# 将另一个链表链接至原链表后面
def connect_list(self, head2):
p = self.head
while p.next != None:
p = p.next
p.next = head2
# 初始化案例
LinkList_demo1 = LinkList()
LinkList_demo1.append(['01', 'Luca1', 'man'])
LinkList_demo1.append(['02', 'Luca2', 'woman'])
LinkList_demo1.append(['03', 'Luca3', 'man'])
LinkList_demo1.append(['04', 'Luca4', 'man'])
LinkList_demo2 = LinkList()
LinkList_demo2.append(['05', 'Luca5', 'woman'])
LinkList_demo2.append(['06', 'Luca6', 'man'])
LinkList_demo2.append(['07', 'Luca7', 'man'])
LinkList_demo2.append(['08', 'Luca8', 'woman'])
# 调用函数，输出链表的数据
print('-' * 10 + 'list1' + '-' * 10)
LinkList_demo1.LinkList_travel()
print('-' * 10 + 'list2' + '-' * 10)
LinkList_demo2.LinkList_travel()
print('-' * 10 + 'After' + '-' * 10)
LinkList_demo1.connect_list(LinkList_demo2.head)
# 输出处理后的链表的数据
LinkList_demo1.LinkList_travel()
----------list1----------
01 Luca1 man
02 Luca2 woman
03 Luca3 man
04 Luca4 man
----------list2----------
05 Luca5 woman
06 Luca6 man
07 Luca7 man
08 Luca8 woman
----------After----------
01 Luca1 man
02 Luca2 woman
03 Luca3 man
04 Luca4 man
05 Luca5 woman
06 Luca6 man
07 Luca7 man
08 Luca8 woman
3.5 单向链表的反转
-
当我们需要反转输出列表，即从后往前输入，我们知道链表中某个结点的位置，却不知道此结点的上一个结点位置。该如何处理呢？
-
实现单向链表反转需要用到3个变量p、q和a，通过循环实现
- 执行while语句前，p指向头结点，q为空
- 执行第一次while循环，借助变量a，将a接到q后，q接到p后，p向下一个结点移动，再将q连接到之前的结点
- 执行第二次while循环，将q的位置交接给a，p的位置交接给q，p再向下一个结点前进，最后将q连接到之前的结点a上
- 执行第三次循环，将q交接给a，p交接给q，p向下一个结点移动，然后q连接到之前结点a上
- 直到p=None时，整个单向链表就反转过来了
def reverse(self):
p = self.__head
q = None
r = None
while p != None:
r = q
q = p
p = p.next
q.next = r
self.__head = q
3.5.1 案例测试（链表反转）
# 定义结点类
class Node():
def __init__(self):
self.name = ''
self.sex = ''
self.index = ''
self.next = None
# 定义链表类
class LinkList():
def __init__(self):
self.__head = None
# 添加结点
def append(self, item_lst):
new_data = Node()
new_data.name = item_lst[1]
new_data.sex = item_lst[2]
new_data.index = item_lst[0]
if self.__head == None:
self.__head = new_data
else:
p = self.__head
while p.next != None:
p = p.next
p.next = new_data
# 遍历整个列表
def LinkList_travel(self):
key = self.__head
while key != None:
print(key.index, key.name, key.sex)
key = key.next
# 链表反转
def reverse(self):
p = self.__head
q = None
r = None
while p != None:
r = q
q = p
p = p.next
q.next = r
self.__head = q
# 初始化案例
LinkList_demo = LinkList()
LinkList_demo.append(['01', 'Luca1', 'man'])
LinkList_demo.append(['02', 'Luca2', 'woman'])
LinkList_demo.append(['03', 'Luca3', 'man'])
LinkList_demo.append(['04', 'Luca4', 'man'])
# 调用函数，输出链表的数据
LinkList_demo.LinkList_travel()
# 输出处理后的链表的数据
print('-' * 10 + 'After' + '-' * 10)
LinkList_demo.reverse()
LinkList_demo.LinkList_travel()
01 Luca1 man
02 Luca2 woman
03 Luca3 man
04 Luca4 man
----------After----------
04 Luca4 man
03 Luca3 man
02 Luca2 woman
01 Luca1 man
四. 堆栈、队列
- 堆栈是典型的“后进先出型”数据结构，多用于递归调用。其存取过程类似于装卸货车，装载货物时，从内到外一层层装；卸载货物时，从外到内一层层卸。即读取数据时，后堆进去的数据先取出，先堆进去的数据后取出。
- 队列是典型的“先进先出型”数据结构。其存取数据过程类似于排队，先来的人排在队伍前，后来的人排在队伍后。需要出队时，从排在队首的人开始出。
4.1 用链表实现堆栈
# 定义链表结点类
class Node():
def __init__(self):
self.data = ''
self.next = None
# 定义判断空字符串
def is_empty():
global top
if top == None: # 当前链表为空时，返回1；否则返回0
return 1
else:
return 0
# 将数据压入堆栈
def push(data):
global top
new_data = Node() # 创建新结点
new_data.data = data # 传入数据
new_data.next = top # 使新结点链接至原链表的后面
top = new_data # 头结点往后移
# 将数据弹出
def pop():
global top
p = top
if is_empty(): # 空链表，则返回-1
print('The link is empty!')
return -1
else:
result = p.data # 拿到数据
p = p.next # 指针移动
top = p # 将第一个结点删除
return result
【实例】
data_list = [str(i) for i in range(1, 11)] # 即将压入堆栈的数据列表
top = None
for data in data_list: # 将数据依次压入堆栈
push(data)
for i in range(1, 6): # 弹出前五个数据
re = pop()
print(f'pop data {i}:{re}')
pop data 1:10
pop data 2:9
pop data 3:8
pop data 4:7
pop data 5:6
4.2 用链表实现队列
- 队列是“先进先出”，本身就符合链表的特性，从头结点开始依次向后读取。
