小白学算法-数据结构和算法教程:什么链表以及操作

链表是一种线性数据结构，其中元素不存储在连续位置，而是使用指针链接。链表形成一系列相连的节点，每个节点存储数据和下一个节点的地址。

小白学算法-数据结构和算法教程:什么链表以及操作_链表

节点结构：链表中的节点通常由两个组件组成： 数据：它保存与该节点关联的实际值或数据。 下一个指针：它存储序列中下一个节点的内存地址（引用）。 头尾：链表通过头节点访问，头节点指向链表中的第一个节点。链表的最后一个节点指向NULL或nullptr，表示链表的结尾。该节点称为尾节点。

为什么需要链表数据结构？

下面列出了链表的一些优点，它将帮助您理解为什么有必要了解它。

• 动态数据结构：可以在运行时根据操作插入或删除来分配或取消分配内存大小。
• 易于插入/删除：元素的插入和删除比数组简单，因为插入和删除后不需要移动元素，只需更新地址。
• 高效的内存利用：众所周知，链表是一种动态数据结构，其大小根据要求增加或减少，从而避免了内存的浪费。 
• 实现：可以使用链表来实现各种高级数据结构，如堆栈、队列、图、哈希图等。

例子：

在系统中，如果我们在数组 id[] = [1000, 1010, 1050, 2000, 2040] 中维护一个有序的 ID 列表。  如果我们想插入一个新的ID 1005，那么为了保持排序顺序，我们必须移动1000之后的所有元素（不包括1000）。  除非使用一些特殊技术，否则数组的删除成本也很高。例如，要删除 id[] 中的 1010，则必须移动 1010 之后的所有内容，因为要做的工作太多，影响了代码的效率。

链表的类型： 

链表主要有以下三种类型：

1. 单链表
2. 双链表
3. 循环链表

1.单链表：

在单链表中，每个节点都包含对序列中下一个节点的引用。遍历单链表是向前完成的。

小白学算法-数据结构和算法教程:什么链表以及操作_双向链表_02

单链表

Python 实现链表：

# 节点类
class Node: 

	＃初始化节点对象的函数
	def __init__(self, data): 
		self.data = data # 分配数据
		self.next = None # 将 next 初始化为空

# 链接列表类
class LinkedList: 

	＃初始化链表对象的函数
	def __init__(self): 
		self.head = None

2.双链表：

在双向链表中，每个节点都包含对下一个和前一个节点的引用。这允许向前和向后两个方向遍历，但需要额外的内存用于向后引用。

小白学算法-数据结构和算法教程:什么链表以及操作_数据结构_03

双链表

Python 实现双向链表

# 双向链表的节点 
class Node: 
	def __init__(self, next=None, prev=None, data=None): 
		self.next = next # 双向链表中指向下一个节点的引用
		self.prev = prev # 双向链表中的上一个节点引用
		self.data = data

3.循环链表：

 在循环链表中，最后一个节点指向头节点，形成循环结构。它可以是单链或双链。

小白学算法-数据结构和算法教程:什么链表以及操作_数据结构_04

循环链表

链表操作

1. 插入：向链表添加新节点涉及调整现有节点的指针以保持正确的顺序。插入可以在列表的开头、结尾或任意位置执行
2. 删除：从链表中删除节点需要调整相邻节点的指针以弥补删除节点留下的间隙。删除可以在列表的开头、结尾或任意位置执行。
3. 搜索：在链表中搜索特定值涉及从头节点遍历链表，直到找到该值或到达链表末尾。

链表的优点

• 动态大小：链接列表可以动态增长或收缩，因为内存分配是在运行时完成的。
• 插入和删除：从链表中添加或删除元素是高效的，尤其是对于大型列表。
• 灵活性：链表可以轻松地重新组织和修改，而不需要连续的内存块。

链表的缺点

• 随机访问：与数组不同，链表不允许通过索引直接访问元素。需要遍历才能到达特定节点。
• 额外内存：与数组相比，链表需要额外的内存来存储指针。

插入链表

给定一个链表，任务是在这个给定的链表中的以下位置插入一个新节点： 

• 在链表的最前面  
• 在给定节点之后。 
• 位于链表的末尾。

方法：

要在链表的开始/开始/前面插入一个节点，我们需要：

• 使链表的第一个节点链接到新节点
• 从原来的链表第一个节点中删除头
• 将新节点作为链表的头。

小白学算法-数据结构和算法教程:什么链表以及操作_链表_05

下面是该方法的实现：

Python3

＃这个函数在LinkedList类中
＃在开头插入一个新节点的函数
def push(self, new_data):

	＃1和2：分配节点和
	＃放入数据
	new_node = Node(new_data)

	# 3. 将新节点的下一个指向头部
	new_node.next = self.head

	# 4. Move the head to point to new Node
	self.head = new_node