作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
在我们的日常生活中，有许多事物和活动都是有序进行的，比如排队购买咖啡，火车车厢的连接，或者是一串珍珠项链。在计算机科学中，我们也有类似的方式来存储和组织数据，这就是我们要介绍的“链表”（Linked List）。
什么是链表？
链表是一种常见的数据结构，它由一系列节点（Node）组成，每个节点包含两部分信息：存储的数据，以及指向列表中下一个节点的引用（通常称为“指针”或“链接”）。
想象一下，链表就像是一列火车。每节车厢都可以载客（存储数据），同时，每节车厢的尾部都有一个钩链（指针）连接着下一节车厢。这种结构让火车可以轻松地增加或减少车厢，而链表也正是因为这种特性，在数据存储方面提供了很大的灵活性。
链表的特点
动态性
链表不需要在内存中占用连续的空间，它可以分散存储。只要知道了第一个节点（我们称之为“头节点”）的位置，我们就可以通过指针找到整个列表的所有元素。这使得链表可以根据需要动态地扩展或收缩，这一点与数组（需要预先指定大小的数据存储方式）形成了对比。
插入与删除
在链表中添加或移除元素非常高效。只需要更改一些指针的指向，就可以轻松地在链表的任何位置插入新的节点或删除现有的节点，而不需要像数组那样移动其他元素。
class ListNode: """定义链表的节点""" def __init__(self, val=0, next=None): self.val = val self.next = next
class LinkedList: """定义链表并实现增删改查功能""" def __init__(self): self.head = None def append(self, val): """在链表末尾添加一个新节点""" new_node = ListNode(val) if not self.head: self.head = new_node else: last_node = self.head while last_node.next: last_node = last_node.next last_node.next = new_node def find(self, val): """查找链表中是否存在指定值的节点""" current_node = self.head while current_node: if current_node.val == val: return True current_node = current_node.next return False def delete(self, val): """删除链表中指定值的节点""" current_node = self.head prev_node = None while current_node and current_node.val != val: prev_node = current_node current_node = current_node.next if current_node: # 找到了要删除的节点 if prev_node: # 不是头节点 prev_node.next = current_node.next else: # 是头节点 self.head = current_node.next def update(self, old_val, new_val): """更新链表中的值""" current_node = self.head while current_node: if current_node.val == old_val: current_node.val = new_val return True current_node = current_node.next return False def display(self): """返回链表中所有节点的值""" values = [] current_node = self.head while current_node: values.append(current_node.val) current_node = current_node.next return values
# 测试链表的功能 if __name__ == "__main__": linked_list = LinkedList() linked_list.append(1) linked_list.append(2) linked_list.append(3) print("Original list:", linked_list.display()) linked_list.delete(2) print("After deleting 2:", linked_list.display()) update_success = linked_list.update(3, 4) print("Update successful:", update_success) print("After updating 3 to 4:", linked_list.display()) print("Find 1:", linked_list.find(1)) print("Find 5:", linked_list.find(5))
输出
链表的类型
链表有几种不同的类型：
单向链表
最简单的链表类型。每个节点只包含数据和指向下一个节点的指针。
双向链表
与单向链表相比，双向链表的每个节点还包含指向前一个节点的指针。这使得我们可以在两个方向上遍历链表。
循环链表
循环链表的最后一个节点会指向头节点，形成一个闭环。
链表 vs. 数组
让我们通过对比来理解链表与数组的区别：
- 数组 是静态的数据结构，需要预先知道数据的大小来分配空间，而且在数组中插入或删除元素通常不如链表高效。
- 链表 提供了动态的数据存储方式，你无需预先知道数据的大小，插入和删除操作更加快捷。
生活中的链表
虽然链表是计算机科学中的概念，但它们的原理也可以在现实生活中找到。比如组织一场活动时的待办事项列表，你可能会发现新的事项需要添加进去，或者完成的事项需要划去。如果你把每项任务写在独立的便签纸上，并用线串联起来，这实际上就是一种链表。
总结
链表是计算机科学中一种基础而重要的数据结构。通过其灵活的节点连接方式，链表在数据存储和处理方面展示了其独特的优势。无论是初学者还是资深开发者，理解链表的原理都是掌握数据结构和算法不可或缺的一部分。
欢迎关注微信公众号 数据分析螺丝钉
