算法与数据结构(part6)--单向链表

学习笔记，仅供参考，有错必纠

参考自：单链表头指针、头结点、头元结的辨析

---

文章目录

算法与数据结构–基于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 0 else: #定义游标 cur = self.__head #计数 count = 0 while cur != None: cur = cur.next count += 1 return count #遍历链表 def travel(self): if self.is_empty(): return else: #定义游标 cur = self.__head while cur != None: #打印数据 print(cur.elem, " ") cur = cur.next print('') #链表尾部添加元素 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 #while循环结束后，cur到达了最后一个节点 cur.next = node #链表开头插入 def add(self, item): #新节点 node = Node(item) if self.is_empty(): self.__head = node else: node.next = self.__head self.__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.__head count = 0 while count < (pos -1): pre = pre.next count += 1 #下面的两行代码顺序不可变 node.next = pre.next pre.next = node #查找节点 def search(self, item): if self.is_empty(): return False else: cur = self.__head while cur!= None: if cur.elem == item: return True else: cur = cur.next return False #删除节点 def remove(self,item): if self.is_empty(): return else: # 定义cur游标 cur = self.__head # 定义pre游标 pre = None # 查找所有的位置有没有要删除的，若有则删 while cur != None: # 判断cur指向的数据，是否为要删的数据 if cur.elem == item: # 考虑特殊情况，恰好要删的是第一个元素 if cur == self.__head: # 头结点指向后一个结点 self.__head = cur.next else: # 删除 pre.next = cur.next return else: # 移动游标，先移动pre，再移动cur pre = cur cur = 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()

输出：

True 0 -------------------- -------------------- 2 1 3 -------------------- False 3 -------------------- 2 abc 1 3 True -------------------- 2 1 3

链表与顺序表的对比

链表与顺序表各种操作的时间复杂度：

操作链表顺序表访问元素O(n)O(1)在头部插入/删除O(1)O(n)在尾部插入/删除O(n)O(1)在中间插入/删除O(n)O(n)