荐 python3实现单向链表图文详解
任何复杂的数据结构都是由int、char、float这些基本数据结构组合而成,不同的组合方式在进行不同操作时有着差异巨大的时间或空间复杂度,例如python中的list就是由基本数据类型按照顺序表的方式去排列而实现的新数据结构。但是python中没有用链表结构实现的数据类型,那我们就试着自己来造一下车*。这一节就来实现最简单的单向链表。
文章目录
单向链表
如下图所示,单向链表中每一个数据结点,除了保存当前结点的基本数据值,还要保存后面相邻节点的地址,从而形成从头到尾的一个单向指针结构。而整个单向链表的变量名,存储的是第一个结点的地址。
简单描述下这种结构的特点
-
因为结点的内存地址不需要连续,所以相比顺序表,对于内存的利用更高效
-
同时管理器只需要存储第一个结点的地址即可,对于后续结点,也只需要前一个结点有指针即可
-
根据下标的查询操作只能从第一个结点依次往后进行
-
越靠近头部的操作时间复杂度越低,越靠近尾部的时间复杂度越高
python3实现
下面根据上面的结构特点来实现单向链表类,不过首先得搞定单个结点类。
结点类
单个结点只需要存储两个值,在构造函数中赋值即可。默认情况下一个结点的地址放None
,等有需要时再进行赋值
class Node(object):
def __init__(self, value):
self.value = value
self.next = None
单向链表类
根据上面的分析,该类只需要保存一个对象属性即可
属性 | 说明 | 类型 |
---|---|---|
__head | 指向第一个结点的地址 | 对象属性,仅内部使用 |
该类实现以后,要实现对里面保存数据的增删改查方法,从最基本的开始,先实现如下几个功能
方法 | 说明 | 类型 |
---|---|---|
isEmpty | 链表长度为0返回True,否则返回False | 对象方法 |
length | 返回链表数据的长度 | 对象方法 |
travel | 遍历整个链表,依次打印每个结点的值 | 对象方法 |
append | 在链表尾端添加结点 | 对象方法 |
shift | 在链表头部添加结点 | 对象方法 |
insert | 在指定下标添加结点 | 对象方法 |
remove | 删除第一次出现的某个值 | 对象方法 |
exist | 检查某个值是否在链表中 | 对象方法 |
下面一个个地来。
构造函数
允许用户直接构造空的链表或者传一个后续结点进来
class SingleLinkedList(object):
def __init__(self, node=None):
self.__head = node
不带任何参数就是空链表,self.__head
为None
,否则就是node的地址。
要理解这里的变量赋值以及后面的很多游标和地址的赋值运算,必须要搞清楚python和很多其他语言不一样,其中的变量都不存储具体值,而只是存放值的地址。所以python的变量名表示的就是地址,将变量赋值给另一个变量,就是将另一个变量也指向前一个变量指向的地址。可以参考另一篇博客《python3中各类变量的内存堆栈分配和函数传参区别实例详解》
isEmpty
这个比较容易,只需要判断self.__head
是否为None
即可达到目的
def isEmpty(self):
return self.__head == None
pep8中建议用
is
去和None
做判断,不过用双等号也可以
length
如下图所示
因为是单向链表,只要是遍历都只能从头开始操作。可以创建一个游标cur,或者叫指针,从第一个结点依次找到最后一个结点,每增加一个结点,将中间变量count的值加1,最后count就是结点的总数,也就是链表的长度。当然加一减一的偏差需要慢慢去比对了
def length(self):
# cur is current position
cur = self.__head
count = 0
while cur != None:
cur = cur.next
count += 1
return count
先通用再特殊,下面考虑下特殊情况,就是链表为空的时候,也就是self.__head
为None
,赋值给cur
,无法进入循环,返回0,也能达到目的。
travel
遍历链表和上面求长度思路基本一样,直接看代码
def travel(self):
# cur is current position
cur = self.__head
while cur != None:
print(cur.value, end=" ")
cur = cur.next
print('')
python3中如果要打印不换行,用end=" "
,最后再打印一次是为了换行,因为默认不管打印什么都会换行。
append
前面说过,因为必须要先遍历一遍链表到最后,所以在末尾添加结点的时间复杂度是很高的。
先看看通用情况
def append(self, value):
node = Node(value)
cur = self.__head
while cur.next != None:
cur = cur.next
cur.next = node
注意这里不能等到cur == None
退出循环,而是cur.next == None
,这样才好通过游标对最后一个结点进行操作。
但是这段代码不能满足特殊情况,就是链表为空的情况,因为此时cur
为None
,但是None
没有next
属性,会报错,于是修改下
def append(self, value):
node = Node(value)
if self.isEmpty():
self.__head = node
else:
cur = self.__head
while cur.next != None:
cur = cur.next
cur.next = node
如果链表为空,直接将新的结点赋值给self.__head
即可。
shift
从头添加就比较容易了,但是要注意,在中间插入必须先建立连接再断开原有连接。也就是说先将后一个结点的地址赋值给插入的结点的next,再将原先的前一个结点的next修改为插入的节点地址。因为一旦先断开,后面的所有节点的地址都会找不到了
def shift(self, value):
node = Node(value)
node.next = self.__head
self.__head = node
如果是空链表的特殊情况也是可以达到目的的。
insert
和shift一样,注意先连接再断开,稍微复杂的是这里要进行位置判断。
通用代码如下
def insert(self, pos, value):
node = Node(value)
cur = self.__head
count = 0
while count < pos - 1:
cur = cur.next
count += 1
node.next = cur.next
cur.next = node
但是因为pos参数是用户传递进来的,还需要进行特殊值的判断,这里规定0或负值都是在头部插入,如果大于长度就在尾部插入
def insert(self, pos, value):
if pos <= 0:
self.shift(value)
elif pos > (self.length() - 1):
self.append(value)
else:
node = Node(value)
cur = self.__head
count = 0
while count < pos - 1:
cur = cur.next
count += 1
node.next = cur.next
cur.next = node
remove
删除结点应该算是所有方法中的难点和重点,因为删除以后要将删除结点的前后连接起来,所以游标必须停留在说删除结点的前一个结点,这样才能对前一个结点的next做赋值操作。此时就得考虑很多种特殊情况,例如只有一个结点时,空链表时
通用代码如下
def remove(self, value):
cur = self.__head
while cur.next != None:
if cur.next.value == value:
cur.next = cur.next.next
return value
else:
cur = cur.next
return
如果加上特殊情况,如下
def remove(self, value):
cur = self.__head
if cur.value == value:
self.__head = cur.next
return value
elif self.__head is None:
return
else:
while cur.next != None:
if cur.next.value == value:
cur.next = cur.next.next
return value
else:
cur = cur.next
return
exist
这个也是遍历链表,检查每个结点的值,比较简单,直接给出代码
def exist(self, value):
cur = self.__head
while cur != None:
if cur.value == value:
return True
else:
cur = cur.next
return False
所有的方法实现了,下面开始测试
if __name__ == "__main__":
sll = SingleLinkedList()
print(sll.exist(10)) # False
print(sll.length()) # 0
print(sll.isEmpty()) # True
sll.append(1)
print(sll.length()) # 1
print(sll.isEmpty()) # False
sll.append(2)
sll.append(3)
sll.append(4)
sll.append(5)
sll.append(6)
sll.shift(8) # 8123456
sll.insert(2, 9) # 81923456
sll.insert(-2, 10) # 10 81923456
sll.insert(100, 11) # 10 81923456 11
sll.travel() # 10 8 1 9 2 3 4 5 6 11
print(sll.length()) # 10
print(sll.isEmpty()) # False
print(sll.exist(100)) # False
print(sll.exist(6)) # True
sll.remove(6)
sll.remove(10)
sll.remove(11)
print(sll.exist(6)) # False
sll.travel() # 8 1 9 2 3 4 5
最后打印的结果和上面的一样
False
0
True
1
False
10 8 1 9 2 3 4 5 6 11
10
False
False
True
False
8 1 9 2 3 4 5
完整代码
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time: 2020-Jul-06
# @Author: xiaofu
class Node(object):
def __init__(self, value):
self.value = value
self.next = None
class SingleLinkedList(object):
def __init__(self, node=None):
self.__head = node
def isEmpty(self):
"""check if the list is empty"""
return self.__head == None
def length(self):
"""length of the list"""
# cur is current position
cur = self.__head
count = 0
while cur != None:
cur = cur.next
count += 1
return count
def travel(self):
"""traverse through the list"""
# cur is current position
cur = self.__head
while cur != None:
print(cur.value, end=" ")
cur = cur.next
print('')
def shift(self, value):
"""add a node to the start"""
node = Node(value)
# link before break
node.next = self.__head
self.__head = node
def append(self, value):
"""add a node to the end"""
node = Node(value)
if self.isEmpty():
self.__head = node
else:
cur = self.__head
while cur.next != None:
cur = cur.next
cur.next = node
def insert(self, pos, value):
"""insert a node at specific position"""
if pos <= 0:
self.shift(value)
elif pos > (self.length() - 1):
self.append(value)
else:
node = Node(value)
cur = self.__head
count = 0
while count < pos - 1:
cur = cur.next
count += 1
node.next = cur.next
cur.next = node
def remove(self, value):
"""remove a node from list when a value first appears"""
cur = self.__head
if cur.value == value:
self.__head = cur.next
return value
elif self.__head is None:
return
else:
while cur.next != None:
if cur.next.value == value:
cur.next = cur.next.next
return value
else:
cur = cur.next
return
def exist(self, value):
"""whether a node exists in list"""
cur = self.__head
while cur != None:
if cur.value == value:
return True
else:
cur = cur.next
return False
时间复杂度
最后看看各种操作的时间复杂度
- 访问元素 - 因为必须要遍历,所以时间复杂度为O(n)
- 头部插入/删除元素 - O(1)
- 尾部插入/删除元素 - O(n)
- 中间插入/删除元素 - 最坏情况也是要遍历所有元素,所以是O(n)
我是T型人小付,一位坚持终身学习的互联网从业者。喜欢我的博客欢迎在csdn上关注我,如果有问题欢迎在底下的评论区交流,谢谢。
本文地址:https://blog.csdn.net/Victor2code/article/details/107170807
上一篇: Python中type和isinstance的使用和区别
下一篇: 专家提醒咀嚼片得嚼够五分钟