【数据结构与算法】3_python版 _链表

文章目录

• 一、为什么需要链表
• 二、链表的定义
• 三、单向链表
• • 3.1 单链表的操作
  • 3.2 python中变量标识的本质
  • 3.3 节点实现-单链表的实现
  • • 3.3.1 链表长度-图示
    • 3.3.2 链表头部和指定位置添加节点-图示
    • 3.3.3 代码实现
  • 3.4 链表与顺序表的对比
• 四、双向链表
• • 4.1 双向链表的操作
  • 4.2 节点实现-双向链表的实现
  • • 4.2.1 添加节点-图示
    • 4.2.2 删除节点-图示
    • 4.2.3 代码实现
• 五、单向循环链表
• • 5.1 单向循环链表的操作
  • 5.2 单向循环链表的实现
  • • 5.2.1 链表长度和添加元素-图示
    • 5.2.2 代码实现

一、为什么需要链表

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

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

二、链表的定义

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

三、单向链表

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

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

3.1 单链表的操作

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

3.2 python中变量标识的本质

a=10
b=20
a, b = b, a
并不是真正的赋值，而是把a和b引用的地址导向改变一下
把a指向的位置指向存储20的那个空间上
把b指向的位置指向存储10的那个空间上

保存10的地方还保存10，保存20的地方上还保存20，
最终改变的是a和b自己维护的地址

3.3 节点实现-单链表的实现

3.3.1 链表长度-图示

3.3.2 链表头部和指定位置添加节点-图示

3.3.3 代码实现

class Node: # 把节点（elem，next）定义为类
"""单链表的节点"""
def __init__(self, elem):
self.elem = elem # elem存放数据元素
self.next = None # next是下一个节点的标识

class SingleLinkList:
"""单链表，把节点串到链表中"""
def __init__(self, node=None):
self.__head = node # 私有属性

# 判断是否为为空，能接受自己，对象方法，不是类方法
def is_empty(self):
return self.__head is None

# 链表长度，self是对象属性，必传
def length(self):
cur = self.__head # cur游标，用来移动遍历节点，初始时，指向头节点
count = 0 # 记录数量
while cur != None: # 尾节点指向None，当未到达尾部时
count += 1
cur = cur.next # 将cur后移一个节点
return count

# 遍历整个链表
def travel(self):
cur = self.__head # 游标指向起始节点
while cur != None:
print(cur.elem, end=" ")
cur = cur.next # 游标cur后移一个节点
print("") # 换行

# 链表头部添加元素，具体的节点
def add(self, item): # item 具体的数据元素
node = Node(item) # 先创建一个保存item值的节点
node.next = self.__head # 将新节点的链接域next指向头节点，即_head指向的位置
self.__head = node # 将链表的头_head指向新节点

# 链表尾部添加元素，item是一个具体的数据元素，不是节点
def append(self, item): # 尾插法
node = Node(item) # 构造一个节点
cur = self.__head
# 先判断链表是否为空，若是空链表，则将_head指向新节点
if self.__head == None: # 或者 if self.is_empty():
self.__head=node
# # 若不为空，则找到尾部，将尾节点的next指向新节点
else:
while cur.next != None:
cur = cur.next
cur.next = node

# 指定位置添加元素，pos为指定位置（下标），item为往链表中添加那个节点所保存的数据
def insert(self, pos, item):
""""
:param pos 从0开始
：param pre 指定位置的前一个元素
"""
# 若指定位置pos为第一个元素之前，则执行头部插入
if pos <= 0:
self.add(item)
# # 若指定位置超过链表尾部，则执行尾部插入
elif pos > self.length()–1:
self.append(item)
# 找到指定位置
else:
node = Node(item)
count = 0
# pre用来指向指定位置pos的前一个位置pos-1，初始从头节点开始移动到指定位置
pre = self.__head
while count < pos–1:
count += 1
pre = pre.next # 往后移动
# 当循环退出后，pre指向 pos-1位置
node.next = pre.next # 先将新节点node的next指向插入位置的节点
pre.next = node # 将插入位置的前一个节点的next指向新节点

# 查找节点元素是否存在链表当中
def search(self, item):
cur = self.__head # 指向头节点
while cur != None:
if cur.elem == item:
return True
else:
cur = cur.next # 往后移动
return False

# 删除节点，指明删除谁，删除具体元素，和列表中的remove一样
def remove(self, item):
cur = self.__head # 指向起始节点
pre = None # pre在cur之前，指向为空
while cur != None:
if cur.elem == item: # 找到了指定元素
# 先判断此节点是否为头节点
if cur == self.__head: #如果是首结点
self.__head = cur.next
else:
pre.next = cur.next # pre.next指向None
break # 删除完之后退出
else:
pre = cur
cur = cur.next

if __name__ == '__main__':
ll = SingleLinkList()
# 判断链表是否为空
print(ll.is_empty()) # True
# 判断空链表的长度是否为0
print(ll.length()) # 0

ll.append(1)
print(ll.is_empty()) # False
print(ll.length()) # 1

ll.append(2)
ll.add(8) # 头部添加 8
ll.append(3)
ll.append(4)
ll.append(5)
ll.travel() # 8 1 2 3 4 5

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

3.4 链表与顺序表的对比

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

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

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

四、双向链表

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

4.1 双向链表的操作

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

4.2 节点实现-双向链表的实现

4.2.1 添加节点-图示

4.2.2 删除节点-图示

4.2.3 代码实现

class Node:
def __init__(self, elem):
self.elem = elem
self.next = None
self.prev = None

class DoubleLinkList:
"""双链表"""
def __init__(self, node=None):
self.__head = node

def is_empty(self):
# 链表是否为空
return self.__head is 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.elem, end=" ")
cur = cur.next
print(" ")
# 下面和单链表不一样
def add(self, item):
# 链表头部添加
node = Node(item)
node.next = self.__head
self.__head = node
node.next.prev = node

def append(self, item):
# 链表尾部添加
node = Node(item)
if self.__head is None:
self.__head = node
else:
cur = self.__head
while cur.next is not None:
cur = cur.next
cur.next = node
node.prev = cur

def insert(self, pos, item):
# 指定位置添加
node = Node(item)
if pos <= 0:
self.add(item)
elif pos > (self.length()–1):
self.append(item)
else:
cur = self.__head
count = 0
while count < pos:
count += 1
cur = cur.next
# 当循环退出后，cur指向pos位置
cur.prev.next = node
node.prev = cur.prev
node.next = cur
cur.prev = node

def remove(self, item):
# 删除节点
cur = self.__head
if cur is None:
return
while cur != None:
if cur.elem == item:
# 先判断此节点是否为头节点
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
break
else:
cur = cur.next

def search(self, item):
# 查找节点是否存在
cur = self.__head
while cur != None:
if cur.elem == item:
return True
else:
cur = cur.next
return False

if __name__ == '__main__':
ll = DoubleLinkList()
# 判断链表是否为空
print(ll.is_empty()) # True
# 判断空链表的长度是否为0
print(ll.length()) # 0

ll.append(1)
print(ll.is_empty()) # False
print(ll.length()) # 1

ll.append(2)
ll.add(8) # 头部添加 8
ll.append(3)
ll.append(4)
ll.append(5)
ll.travel() # 8 1 2 3 4 5

ll.insert(–1, 9)
ll.travel() # 9 8 12345
ll.insert(3, 100)
ll.travel() # 9 8 1 100 2345
ll.insert(10, 200)
ll.travel() # 9 8 1 100 2345 200
ll.remove(100)
ll.travel() # 9 8 1 2 3 4 5 200

五、单向循环链表

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

5.1 单向循环链表的操作

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

5.2 单向循环链表的实现

5.2.1 链表长度和添加元素-图示

5.2.2 代码实现

class Node: # 把节点（elem，next）定义为类
"""单链表的节点"""
def __init__(self, elem):
self.elem = elem # elem存放数据元素
self.next = None # next是下一个节点的标识

class SingCycleLinkList:
"""单向循环链表，把节点串到链表中"""
def __init__(self, node=None):
self.__head = node # 私有属性
if node:
node.next = node

# 判断是否为空，能接受自己，对象方法，不是类方法
def is_empty(self):
return self.__head is None

# 链表长度，self是对象属性，必传
def length(self):
if self.is_empty():
return 0
cur = self.__head # cur游标，用来移动遍历节点，初始时，指向头节点
count = 1 # 记录数量
while cur.next != self.__head: # 尾节点指向None，当未到达尾部时
count += 1
cur = cur.next # 将cur后移一个节点
return count

# 遍历整个链表
def travel(self):
if self.is_empty():
return
cur = self.__head # 游标指向起始节点
while cur.next != self.__head:
print(cur.elem, end=" ")
cur = cur.next # 游标cur后移一个节点
# 退出循环，cur指向尾结点，但尾结点的元素未打印
print(cur.elem)

# 链表头部添加元素，具体的节点
def add(self, item):
node = Node(item) # 先创建一个保存item值的节点
if self.is_empty():
self.__head = node
node.next = node
else:
cur = self.__head
while cur.next != self.__head:
cur = cur.next
# 退出循环，cur指向尾节点
node.next = self.__head
self.__head = node # 将链表的头_head指向新节点
cur.next = node # cur.next = self.__head

# 链表尾部添加元素，item是一个具体的数据元素，不是节点
def append(self, item): # 尾插法
node = Node(item) # 构造一个节点
if self.is_empty():
self.__head = node
node.next = node
else:
cur = self.__head
while cur.next != self.__head:
cur = cur.next
# node.next = cur.next
node.next = self.__head
cur.next = node

# 指定位置添加元素，pos为指定位置（下标），item为往链表中添加那个节点所保存的数据
def insert(self, pos, item):
""""
:param pos 从0开始
：param pre 指定位置的前一个元素
"""
# 若指定位置pos为第一个元素之前，则执行头部插入
if pos <= 0:
self.add(item)
# # 若指定位置超过链表尾部，则执行尾部插入
elif pos > self.length()–1:
self.append(item)
# 找到指定位置
else:
node = Node(item)
count = 0
pre = self.__head # pre用来指向指定位置pos的前一个位置pos-1，初始从头节点开始移动到指定位置
while count < pos–1:
count += 1
pre = pre.next # 往后移动
# 当循环退出后，pre指向 pos-1位置
node.next = pre.next # 先将新节点node的next指向插入位置的节点
pre.next = node # 将插入位置的前一个节点的next指向新节点

# 查找节点元素是否存在链表当中
def search(self, item):
if self.is_empty():
return False
cur = self.__head # 指向头节点
while cur.next != self.__head:
if cur.elem == item:
return True
else:
cur = cur.next # 往后移动
# 退出循环，cur指向尾节点
if cur.elem == item:
return True
return False

# 删除节点，指明删除谁，删除具体元素，和列表中的remove一样
def remove(self, item):
if self.is_empty():
return

cur = self.__head # 指向起始节点
pre = None # pre在cur之前，指向为空

while cur.next != self.__head:
if cur.elem == item: # 找到了指定元素
# 先判断此节点是否为头节点
if cur == self.__head: #如果是首结点
# 头节点情况，找尾节点,rear指向尾部
rear = self.__head
while rear.next != self.__head:
rear = rear.next
self.__head = cur.next
rear.next = self.__head
else:
# 中间节点
pre.next = cur.next # pre.next指向None
return
else:
# 两个游标同时往后移动，先移动pre
pre = cur
cur = cur.next
# 退出循环，cur指向尾节点
if cur.elem == item:
if cur == self.__head:
# 链表中只有一个节点
self.__head = None
else:
# pre.next = cur.next
pre.next = cur.next

if __name__ == '__main__':
ll = SingCycleLinkList()
# 判断链表是否为空
print(ll.is_empty()) # True
# 判断空链表的长度是否为0
print(ll.length()) # 0

ll.append(1)
print(ll.is_empty()) # False
print(ll.length()) # 1

ll.append(2)
ll.add(8) # 头部添加 8
ll.append(3)
ll.append(4)
ll.append(5)
ll.travel() # 8 1 2 3 4 5

ll.insert(–1, 9)
ll.travel() # 9 8 12345
ll.insert(3, 100)
ll.travel() # 9 8 1 100 2345
ll.insert(10, 200)
ll.travel() # 9 8 1 100 2345 200
ll.remove(100)
ll.travel() # 9 8 1 2 3 4 5 200