绵阳建设招投标在哪个网站,桂阳网站制作,请牢记此域名,搜狗收录查询链表是计算机科学中最基础的数据结构之一#xff0c;也是许多高级数据结构和算法的基础。本文将带你从零开始#xff0c;逐步掌握链表的概念、实现和应用。通过丰富的案例和通俗易懂的解释#xff0c;你将能够轻松理解并应用链表。
什么是链表#xff1f;
链表是一种线性…链表是计算机科学中最基础的数据结构之一也是许多高级数据结构和算法的基础。本文将带你从零开始逐步掌握链表的概念、实现和应用。通过丰富的案例和通俗易懂的解释你将能够轻松理解并应用链表。
什么是链表
链表是一种线性数据结构由一系列节点Node组成。每个节点包含两个部分数据域和指针域。数据域用于存储数据指针域用于指向下一个节点。链表中的节点通过指针连接在一起形成一个链式结构。
与数组不同链表的内存空间不需要连续分配。这意味着链表可以更灵活地利用内存空间但也意味着访问链表中的元素需要从头节点开始逐个遍历。
链表的类型
链表有多种类型常见的有
单链表Singly Linked List每个节点只有一个指针指向下一个节点。双链表Doubly Linked List每个节点有两个指针一个指向前一个节点一个指向下一个节点。循环链表Circular Linked List尾节点的指针指向头节点形成一个环。
本文将重点介绍单链表因为它是最基础且最常用的链表类型。
单链表的实现
在Python中我们可以通过定义一个Node类和一个LinkedList类来实现单链表。
1. 定义节点类
首先我们需要定义一个节点类Node它包含数据域和指针域。
class Node:def __init__(self, data):self.data data # 数据域self.next None # 指针域初始化为None2. 定义链表类
接下来我们定义一个链表类LinkedList它包含对链表的各种操作如插入、删除、遍历等。
class LinkedList:def __init__(self):self.head None # 头节点初始化为None# 在链表末尾插入节点def append(self, data):new_node Node(data)if self.head is None: # 如果链表为空新节点为头节点self.head new_nodereturnlast_node self.headwhile last_node.next: # 遍历到链表末尾last_node last_node.nextlast_node.next new_node # 将新节点插入到末尾# 在链表头部插入节点def prepend(self, data):new_node Node(data)new_node.next self.head # 新节点的指针指向当前头节点self.head new_node # 更新头节点为新节点# 删除指定数据的节点def delete(self, data):current_node self.headif current_node and current_node.data data: # 如果头节点就是要删除的节点self.head current_node.nextcurrent_node Nonereturnprev_node Nonewhile current_node and current_node.data ! data: # 遍历查找要删除的节点prev_node current_nodecurrent_node current_node.nextif current_node is None: # 如果没找到要删除的节点returnprev_node.next current_node.next # 跳过要删除的节点current_node None# 打印链表def print_list(self):current_node self.headwhile current_node:print(current_node.data, end - )current_node current_node.nextprint(None)3. 使用链表
现在我们可以使用LinkedList类来创建和操作链表。
# 创建一个链表
llist LinkedList()# 在链表末尾插入节点
llist.append(1)
llist.append(2)
llist.append(3)# 在链表头部插入节点
llist.prepend(0)# 打印链表
llist.print_list() # 输出: 0 - 1 - 2 - 3 - None# 删除节点
llist.delete(2)# 打印链表
llist.print_list() # 输出: 0 - 1 - 3 - None链表的应用案例
链表在实际应用中有很多用途以下是几个常见的案例
1. 实现队列
队列是一种先进先出FIFO的数据结构链表可以很方便地实现队列。
class Queue:def __init__(self):self.linked_list LinkedList()# 入队def enqueue(self, data):self.linked_list.append(data)# 出队def dequeue(self):if self.linked_list.head is None:return Nonedata self.linked_list.head.dataself.linked_list.delete(data)return data# 打印队列def print_queue(self):self.linked_list.print_list()# 使用队列
queue Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
queue.print_queue() # 输出: 1 - 2 - 3 - None
print(queue.dequeue()) # 输出: 1
queue.print_queue() # 输出: 2 - 3 - None2. 实现栈
栈是一种后进先出LIFO的数据结构链表也可以很方便地实现栈。
class Stack:def __init__(self):self.linked_list LinkedList()# 入栈def push(self, data):self.linked_list.prepend(data)# 出栈def pop(self):if self.linked_list.head is None:return Nonedata self.linked_list.head.dataself.linked_list.delete(data)return data# 打印栈def print_stack(self):self.linked_list.print_list()# 使用栈
stack Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.print_stack() # 输出: 3 - 2 - 1 - None
print(stack.pop()) # 输出: 3
stack.print_stack() # 输出: 2 - 1 - None3. 反转链表
反转链表是一个经典的面试题我们可以通过修改指针的方向来实现。
def reverse_linked_list(llist):prev_node Nonecurrent_node llist.headwhile current_node:next_node current_node.next # 保存下一个节点current_node.next prev_node # 反转指针prev_node current_node # 移动prev_nodecurrent_node next_node # 移动current_nodellist.head prev_node # 更新头节点# 反转链表
llist LinkedList()
llist.append(1)
llist.append(2)
llist.append(3)
llist.print_list() # 输出: 1 - 2 - 3 - None
reverse_linked_list(llist)
llist.print_list() # 输出: 3 - 2 - 1 - None4. 链表实现LRU缓存
LRULeast Recently Used缓存是一种常见的缓存淘汰策略它会优先淘汰最近最少使用的数据。链表可以很好地支持LRU缓存的实现。
案例浏览器缓存
假设你正在浏览网页浏览器会将你最近访问的网页缓存起来。当你访问一个新网页时如果缓存已满浏览器会淘汰最久未访问的网页缓存。这个过程可以用链表来实现。
class LRUCache:def __init__(self, capacity):self.capacity capacity # 缓存容量self.cache {} # 存储缓存数据self.linked_list LinkedList() # 使用链表记录访问顺序# 获取缓存数据def get(self, key):if key in self.cache:# 如果缓存中有该数据将其移到链表头部表示最近使用self.linked_list.delete(key)self.linked_list.prepend(key)return self.cache[key]return -1 # 如果缓存中没有该数据返回-1# 插入缓存数据def put(self, key, value):if key in self.cache:# 如果缓存中已有该数据更新其值并移到链表头部self.linked_list.delete(key)elif len(self.cache) self.capacity:# 如果缓存已满淘汰链表尾部的数据最久未使用last_key self.linked_list.headwhile last_key.next:last_key last_key.nextself.linked_list.delete(last_key.data)del self.cache[last_key.data]# 将新数据插入链表头部self.linked_list.prepend(key)self.cache[key] value# 使用LRU缓存
cache LRUCache(2)
cache.put(1, 网页1)
cache.put(2, 网页2)
print(cache.get(1)) # 输出: 网页1
cache.put(3, 网页3) # 缓存已满淘汰网页2
print(cache.get(2)) # 输出: -1网页2已被淘汰通俗解释
链表记录了数据的访问顺序最近访问的数据在链表头部最久未访问的数据在链表尾部。当缓存满时直接淘汰链表尾部的数据确保缓存中始终保留最近使用的数据。
5. 链表实现多项式相加
多项式相加是数学中常见的操作链表可以用来表示多项式并实现相加功能。
案例多项式计算
假设有两个多项式
多项式A3x^2 2x 5多项式B4x^3 2x^2 1
我们可以用链表表示这两个多项式并实现它们的相加。
class PolynomialTerm:def __init__(self, coefficient, exponent):self.coefficient coefficient # 系数self.exponent exponent # 指数self.next None # 指向下一个项的指针class Polynomial:def __init__(self):self.head None # 多项式的头节点# 添加项def add_term(self, coefficient, exponent):new_term PolynomialTerm(coefficient, exponent)if self.head is None:self.head new_termelse:current self.headwhile current.next:current current.nextcurrent.next new_term# 打印多项式def print_polynomial(self):current self.headwhile current:print(f{current.coefficient}x^{current.exponent}, end if current.next else \n)current current.next# 多项式相加def add_polynomials(poly1, poly2):result Polynomial()current1 poly1.headcurrent2 poly2.headwhile current1 and current2:if current1.exponent current2.exponent:result.add_term(current1.coefficient, current1.exponent)current1 current1.nextelif current1.exponent current2.exponent:result.add_term(current2.coefficient, current2.exponent)current2 current2.nextelse:result.add_term(current1.coefficient current2.coefficient, current1.exponent)current1 current1.nextcurrent2 current2.next# 将剩余项加入结果while current1:result.add_term(current1.coefficient, current1.exponent)current1 current1.nextwhile current2:result.add_term(current2.coefficient, current2.exponent)current2 current2.nextreturn result# 创建多项式A3x^2 2x 5
polyA Polynomial()
polyA.add_term(3, 2)
polyA.add_term(2, 1)
polyA.add_term(5, 0)# 创建多项式B4x^3 2x^2 1
polyB Polynomial()
polyB.add_term(4, 3)
polyB.add_term(2, 2)
polyB.add_term(1, 0)# 相加并打印结果
result Polynomial.add_polynomials(polyA, polyB)
result.print_polynomial() # 输出: 4x^3 5x^2 2x 6通俗解释
每个链表节点表示多项式的一个项包含系数和指数。通过遍历两个链表将相同指数的项相加最终得到一个新的多项式。
6. 链表实现约瑟夫问题
约瑟夫问题是一个经典的数学问题描述如下n个人围成一圈从第k个人开始报数数到m的人出列直到所有人出列。链表可以很好地模拟这个过程。
案例游戏中的淘汰机制
假设你和朋友们围成一圈玩“数到3就淘汰”的游戏链表可以模拟这个过程。
def josephus(n, k, m):# 创建循环链表class Node:def __init__(self, data):self.data dataself.next Nonehead Node(1)prev headfor i in range(2, n 1):new_node Node(i)prev.next new_nodeprev new_nodeprev.next head # 形成环# 找到第k个人current headfor _ in range(k - 1):current current.next# 开始报数并淘汰while current.next ! current:# 报数到m-1for _ in range(m - 1):current current.next# 淘汰第m个人print(f淘汰{current.next.data})current.next current.next.nextcurrent current.nextprint(f最后剩下{current.data})# 使用约瑟夫问题
josephus(5, 1, 3) # 输出: 淘汰3 - 淘汰1 - 淘汰5 - 淘汰2 - 最后剩下4通俗解释
链表模拟了一个圆圈每个人是一个节点节点的指针指向下一个人。从第k个人开始报数数到m的人被淘汰从链表中移除直到最后剩下一个人。 总结
通过以上案例我们可以看到链表在实际问题中的广泛应用。无论是缓存管理、数学计算还是游戏模拟链表都能提供高效的解决方案。希望这些案例能帮助你更好地理解链表的应用场景并激发你进一步探索数据结构的兴趣
