学习笔记，仅供参考，有错必纠
参考自：单链表头指针、头结点、头元结的辨析
文章目录
算法与数据结构–基于python链表为啥需要链表什么是链表单向链表什么是单向链表单列表的操作节点的实现单链表的实现链表与顺序表的对比算法与数据结构–基于python
链表
为啥需要链表
顺序表的构建需要预先知道数据大小来申请连续的存储空间，而在进行扩充时又需要进行数据的搬迁，所以使用起来不是很灵活；而链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。
什么是链表
链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理，链表是一种常见的基础数据结构，是一种线性表，但是不像顺序表一样连续存储数据，而是在每一个结点（数据存储单元）里存放下一个结点的位置信息（即地址）。
单向链表
什么是单向链表
单向链表也叫单链表，是链表中最简单的一种形式；它的每个结点包含两个域，一个信息域（元素域）和一个链接域；这个链接指向链表中的下一个结点，而最后一个结点的链接域则指向一个空值。
图示
单链表也可以没有头结点，如果没有头结点的话，那么单链表就会变成这样：
关于头结点
头结点是为了操作的统一与方便而设立的，放在第一个元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等），首元结点也就是第一个元素的结点，它是头结点后边的第一个结点，头结点不是链表所必需的。
关于头指针
在线性表的链式存储结构中，头指针是指链表指向第一个结点的指针，若链表有头结点，则头指针就是指向链表头结点的指针；头指针具有标识作用，故常用头指针冠以链表的名字；无论链表是否为空，头指针均不为空，头指针是链表的必要元素。
单列表的操作
is_empty()#链表是否为空length()#链表长度travel()#遍历整个链表append(item)#链表尾部添加元素add(item)#链表头部添加元素insert(pos, item)#指定位置添加元素search(item)#查找结点是否存在remove(item)#删除结点
节点的实现
class Node:def __init__(self, elem):#初始化数据区self.elem = elem#初始化链接区self.next = None
单链表的实现
首先，我们参照下图中的链表形式，来构造我们的单链表：
同时，我们参照下图中的尾插法，在我们的链表末尾插入数据：
参照下图中的头插法，在链表头部添加元素：
参照下图中的插入法，在链表中指定位置插入元素：
参照下图中的删除法，在链表中删除某个指定元素：
定义单链表：
class SingleLinkedList:def __init__(self):#头指针self.__head = None#判断链表是否为空def is_empty(self):return self.__head is None#查询长度def length(self):#判断是否为空if self.is_empty():return 0else:#定义游标cur = self.__head#计数count = 0while cur != None:cur = cur.nextcount += 1return count#遍历链表def travel(self):if self.is_empty():returnelse:#定义游标cur = self.__headwhile cur != None:#打印数据print(cur.elem, " ")cur = cur.nextprint('')#链表尾部添加元素def append(self, item):#定义新节点node = Node(item)#判断链表是否为空if self.is_empty():self.__head = nodeelse:cur = self.__headwhile cur.next!= None:cur = cur.next#while循环结束后，cur到达了最后一个节点cur.next = node#链表开头插入def add(self, item):#新节点node = Node(item)if self.is_empty():self.__head = nodeelse:node.next = self.__headself.__head = node#链表中指定位置插入def insert(self, pos, item):#新节点if pos < 0:self.add(item)elif pos > (self.length() - 1):self.append(item)else:node = Node(item)pre = self.__headcount = 0while count < (pos -1):pre = pre.nextcount += 1#下面的两行代码顺序不可变node.next = pre.nextpre.next = node#查找节点def search(self, item):if self.is_empty():return Falseelse:cur = self.__headwhile cur!= None:if cur.elem == item:return Trueelse:cur = cur.nextreturn False#删除节点def remove(self,item):if self.is_empty():returnelse:# 定义cur游标cur = self.__head# 定义pre游标pre = None# 查找所有的位置有没有要删除的，若有则删while cur != None:# 判断cur指向的数据，是否为要删的数据if cur.elem == item:# 考虑特殊情况，恰好要删的是第一个元素if cur == self.__head:# 头结点指向后一个结点self.__head = cur.nextelse:# 删除pre.next = cur.nextreturnelse:# 移动游标，先移动pre，再移动curpre = curcur = cur.next
测试：
if __name__ == "__main__":sll = SingleLinkedList()print(sll.is_empty())print(sll.length())print('-'*20)sll.travel()print('-'*20)sll.append(1)sll.add(2)sll.append(3)sll.travel()print('-'*20)print(sll.is_empty())print(sll.length())print('-'*20)sll.insert(1,'abc')sll.travel()print(sll.search(2))print('-'*20)sll.remove('abc')sll.travel()
输出：
True0----------------------------------------2 1 3 --------------------False3--------------------2 abc 1 3 True--------------------2 1 3
链表与顺序表的对比
链表与顺序表各种操作的时间复杂度：
