数据结构与算法（Python）第三天

3&＃xff1a;链表

为什么需要链表

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

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

链表的定义

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

3.1 单向链表

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

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

Python 中赋值的实际意义&＃xff1a;

变量a,b是一块内存&＃xff0c;里面存的是10,20的地址。

变量a是一块内存&＃xff0c;可以任意赋值&＃xff0c;&＃xff08;把a指向函数的地址&＃xff09;

节点实现

创建一个类&＃xff0c;elem&＃xff08;item&＃xff09;&＃61;值&＃xff0c;next&＃61;下一节点的地址。

#节点实现
class SingleNode(object):"""单链表的节点"""def __init__(self,item):#_item存放数据元素self.item&＃61;item#_next是下一节点的标识self.next&＃61;None


单链表的操作

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

单链表的实现

链表的实现方式&＃xff1a;

#单链表的操作class SingleLinkList(object):"""单链表"""def __init__(self,node&＃61;None):self.__head&＃61;nodedef is_empty(self):"""判断链表是否为空"""return self.__head &＃61;&＃61; Nonedef length(self):"""链表长度"""# cur初始时指向头节点cur&＃61;self.__headcount&＃61;0# 尾节点指向None&＃xff0c;当未到达尾部时while cur !&＃61;None:count &＃43;&＃61;1# 将cur后移一个节点cur&＃61; cur.nextreturn countdef travel(self):"""遍历整个链表"""cur&＃61;self.__headwhile cur !&＃61; None:print(cur.item,end&＃61;" "),cur&＃61;cur.nextprint(end&＃61;"\n")def add(self,item):"""链表头部添加元素,头插法"""node&＃61;SingleNode(item)node.next&＃61;self.__headself.__head&＃61;nodedef append(self,item):"""链表尾部添加元素,尾插法"""node&＃61;SingleNode(item)# 先判断链表是否为空&＃xff0c;若是空链表&＃xff0c;则将_head指向新节点if self.is_empty():self.__head&＃61;node# 若不为空&＃xff0c;则找到尾部&＃xff0c;将尾节点的next指向新节点else:cur&＃61;self.__headwhile cur.next !&＃61;None:cur&＃61;cur.nextcur.next&＃61;nodedef insert(self,pos, item):"""指定位置添加元素:param pos 从0开始"""if pos<&＃61;0:self.add(item)elif pos>self.length()-1:self.append(item)else:pre&＃61; self.__headcount&＃61;0while count < (pos-1):count &＃43;&＃61; 1pre&＃61;pre.next#当循环退出后&＃xff0c;pre指向pos-1的位置node&＃61;SingleNode(item)node.next&＃61;pre.nextpre.next&＃61;nodedef remove(self,item):"""删除节点"""cur&＃61;self.__headpre&＃61;Nonewhile cur!&＃61;None:if cur.item &＃61;&＃61; item:#先判断此节点是否为头节点#头节点if cur&＃61;&＃61;self.__head:self.__head&＃61;cur.nextelse:pre.next&＃61;cur.nextbreakelse:pre&＃61;curcur&＃61;cur.nextdef search(self,item):"""查找节点是否存在"""cur&＃61;self.__headwhile cur !&＃61;None:if cur.item &＃61;&＃61; item:return Trueelse:cur&＃61;cur.nextreturn False

单链表的操作&＃xff1a;

测试

if __name__&＃61;&＃61;"__main__":ll&＃61;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)ll.travel()ll.insert(-1,100) #100,8,1,2,3,4,5,6ll.travel()ll.insert(3,200) #100,8,1,200,2,3,4,5,6ll.travel()ll.insert(10,300) #100,8,1,200,2,3,4,5,6,300ll.travel()ll.remove(200)ll.travel()ll.remove(100)ll.travel()ll.remove(300)ll.travel()


运行结果&＃xff1a;

True
0
False
1
8 1 2 3 4 5 6
100 8 1 2 3 4 5 6
100 8 1 200 2 3 4 5 6
100 8 1 200 2 3 4 5 6 300
100 8 1 2 3 4 5 6 300
8 1 2 3 4 5 6 300
8 1 2 3 4 5 6


链表与顺序表的对比

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

链表与顺序表的各种操作复杂度如下所示&＃xff1a;

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