Python实现单项链表的最全教程
作者:Thank?CAT 时间:2021-12-21 09:45:26
单向链表
单向链表也叫单链表,是链表中最简单的一种形式,它的每个节点包含两个域,一个信息域(元素域)和一个链接域。这个链接指向链表中的下一个节点,而最后一个节点的链接域则指向一个空值。
表元素域elem用来存放具体的数据。
链接域next用来存放下一个节点的位置(python中的标识)
变量p指向链表的头节点(首节点)的位置,从p出发能找到表中的任意节点。
节点实现
class Node(object):
"""节点"""
def __init__(self, elem):
self.elem = elem
self.next = None
单链表的操作
is_empty() 链表是否为空
length() 链表长度
travel() 遍历整个链表
add(item) 链表头部添加元素
append(item) 链表尾部添加元素
insert(pos, item) 指定位置添加元素
remove(item) 删除节点
search(item) 查找节点是否存在
单链表的实现
class SingleLinkList(object):
"""单链表"""
def __init__(self, node=None):
self.__head = node
单链表 判断链表是否为空(is_empty)
def is_empty(self):
"""链表是否为空"""
return self.__head == None
单链表 链表长度(length)
def length(self):
"""链表长度"""
# cur游标,用来移动遍历节点
cur = self.__head
# count记录数量
count = 0
while cur != None:
count += 1
cur = cur.next
return count
单链表 遍历整个链表(travel)
def travel(self):
"""遍历整个链表"""
cur = self.__head
while cur != None:
print(cur.elem, end=" ")
cur = cur.next
print("")
单链表 链表尾部添加元素,尾插法(append)
def append(self, item):
"""链表尾部添加元素, 尾插法"""
node = Node(item)
if self.is_empty():
self.__head = node
else:
cur = self.__head
while cur.next != None:
cur = cur.next
cur.next = node
单链表 链表头部插入元素,头插法(add)
def add(self, item):
"""链表头部添加元素,头插法"""
node = Node(item)
node.next = self.__head
self.__head = node
单链表 指定位置插入元素(insert)
def insert(self, pos, item):
"""指定位置添加元素
:param pos 从0开始
"""
if pos <= 0:
self.add(item)
elif pos > (self.length()-1):
self.append(item)
else:
pre = self.__head
count = 0
while count < (pos-1):
count += 1
pre = pre.next
# 当循环退出后,pre指向pos-1位置
node = Node(item)
node.next = pre.next
pre.next = node
单链表 删除节点(remove)
def remove(self, item):
"""删除节点"""
cur = self.__head
pre = None
while cur != None:
if cur.elem == item:
# 先判断此结点是否是头节点
# 头节点
if cur == self.__head:
self.__head = cur.next
else:
pre.next = cur.next
break
else:
pre = cur
cur = cur.next
单链表 查找节点是否存在(search)
def search(self, item):
"""查找节点是否存在"""
cur = self.__head
while cur != None:
if cur.elem == item:
return True
else:
cur = cur.next
return False
单链表 完整代码及测试
# coding:utf-8
class Node(object):
"""节点"""
def __init__(self, elem):
self.elem = elem
self.next = None
class SingleLinkList(object):
"""单链表"""
def __init__(self, node=None):
self.__head = node
def is_empty(self):
"""链表是否为空"""
return self.__head == None
def length(self):
"""链表长度"""
# cur游标,用来移动遍历节点
cur = self.__head
# count记录数量
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
def append(self, item):
"""链表尾部添加元素, 尾插法"""
node = Node(item)
if self.is_empty():
self.__head = node
else:
cur = self.__head
while cur.next != None:
cur = cur.next
cur.next = node
def insert(self, pos, item):
"""指定位置添加元素
:param pos 从0开始
"""
if pos <= 0:
self.add(item)
elif pos > (self.length()-1):
self.append(item)
else:
pre = self.__head
count = 0
while count < (pos-1):
count += 1
pre = pre.next
# 当循环退出后,pre指向pos-1位置
node = Node(item)
node.next = pre.next
pre.next = node
def remove(self, item):
"""删除节点"""
cur = self.__head
pre = None
while cur != None:
if cur.elem == item:
# 先判断此结点是否是头节点
# 头节点
if cur == self.__head:
self.__head = cur.next
else:
pre.next = cur.next
break
else:
pre = cur
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 = SingleLinkList()
print(ll.is_empty())
print(ll.length())
ll.append(1)
print(ll.is_empty())
print(ll.length())
ll.append(2)
ll.add(8)
ll.append(3)
ll.append(4)
ll.append(5)
ll.append(6)
# 8 1 2 3 4 5 6
ll.insert(-1, 9) # 9 8 1 23456
ll.travel()
ll.insert(3, 100) # 9 8 1 100 2 3456
ll.travel()
ll.insert(10, 200) # 9 8 1 100 23456 200
ll.travel()
ll.remove(100)
ll.travel()
ll.remove(9)
ll.travel()
ll.remove(200)
ll.travel()
"""
result:
True
0
False
1
9 8 1 2 3 4 5 6
9 8 1 100 2 3 4 5 6
9 8 1 100 2 3 4 5 6 200
9 8 1 2 3 4 5 6 200
8 1 2 3 4 5 6 200
8 1 2 3 4 5 6
"""
链表与顺序表的对比
链表失去了顺序表随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大,但对存储空间的使用要相对灵活。
链表与顺序表的各种操作复杂度如下所示:
操作 | 链表 | 顺序表 |
---|---|---|
访问元素 | O(n) | O(1) |
在头部插入/删除 | O(1) | O(n) |
在尾部插入/删除 | O(n) | O(1) |
在中间插入/删除 | O(n) | O(n) |
注意虽然表面看起来复杂度都是 O(n),但是链表和顺序表在插入和删除时进行的是完全不同的操作。链表的主要耗时操作是遍历查找,删除和插入操作本身的复杂度是O(1)。顺序表查找很快,主要耗时的操作是拷贝覆盖。因为除了目标元素在尾部的特殊情况,顺序表进行插入和删除时需要对操作点之后的所有元素进行前后移位操作,只能通过拷贝和覆盖的方法进行。
来源:https://www.cnblogs.com/thankcat/p/17032027.html
标签:Python,单项链表
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
PyCharm配置KBEngine快速处理代码提示冲突、配置命令问题
2023-08-12 09:14:28
![](https://img.aspxhome.com/file/2023/4/64654_0s.png)
SQL Server导入导出数据方法
2007-08-17 09:50:00
Python中每次处理一个字符的5种方法
2023-09-26 02:49:13
Python pywifi ERROR Open handle failed问题及解决
2021-01-16 03:54:28
Python计算矩阵的和积的实例详解
2021-06-06 10:09:34
你喜欢篮球吗?Python实现篮球游戏
2023-10-26 00:28:36
![](https://img.aspxhome.com/file/2023/6/68456_0s.png)
php中session_id()函数详细介绍,会话id生成过程及session id长度
2023-11-24 08:01:00
如何定义记录集打开的游标类型?
2009-11-15 20:19:00
使用Python爬取最好大学网大学排名
2023-09-17 09:24:45
使用go求幂的几种方法小结
2023-09-23 05:07:45
![](https://img.aspxhome.com/file/2023/6/99066_0s.jpg)
asp无组件上传并插入到数据库里
2008-10-24 10:04:00
Python 统计列表中重复元素的个数并返回其索引值的实现方法
2023-07-15 12:31:24
![](https://img.aspxhome.com/file/2023/9/77679_0s.png)
通过Python实现控制手机详解
2021-04-21 12:10:37
![](https://img.aspxhome.com/file/2023/2/69552_0s.png)
Mootools 1.2教程(18)——Class 类(第一部分)
2008-12-19 12:45:00
sql ntext数据类型字符替换实现代码
2011-09-30 11:08:00
从SNS看社会化界面设计(一)
2009-02-23 12:21:00
![](https://img.aspxhome.com/file/UploadPic/20092/23/1-73s.jpg)
SQLServer与服务器连接时出错的解决方案
2009-06-28 14:35:00
SQL Server 2005 内置工具建审查系统
2009-01-19 14:24:00
Oracle数据库安全策略分析 (三)
2010-07-31 13:24:00
python Matplotlib基础--如何添加文本和标注
2022-09-17 15:51:05
![](https://img.aspxhome.com/file/2023/4/75114_0s.png)