链表：基础概念与代码实现
链表（Linked List）是一种常见的数据结构，其特点是通过一系列的节点（Node）来存储数据，每个节点除了存储数据元素之外，还保存了指向下一个节点的指针。这种结构使得链表在插入和删除元素时具有较高的效率，但同时也带来了访问元素的复杂性。
链表的基本组成部分是节点。每个节点至少包含两部分信息：一是存储的数据元素，二是指向下一个节点的指针。对于单向链表，节点只包含一个指向下一个节点的指针；而对于双向链表，节点则包含两个指针，一个指向下一个节点，另一个指向前一个节点。
链表可以分为以下几种类型：
单向链表：每个节点只有一个指向下一个节点的指针。
双向链表：每个节点有两个指针，一个指向下一个节点，另一个指向前一个节点。
循环链表：链表形成一个环，最后一个节点指向第一个节点。
下面是一个简单的单向链表的Python实现：
python复制代码
|
class Node: |
|
def __init__(self, data=None): |
|
self.data = data |
|
self.next = None |
|
|
|
class LinkedList: |
|
def __init__(self): |
|
self.head = None |
|
|
|
def insert(self, data): |
|
if not self.head: |
|
self.head = Node(data) |
|
else: |
|
cur = self.head |
|
while cur.next: |
|
cur = cur.next |
|
cur.next = Node(data) |
|
|
|
def display(self): |
|
elems = [] |
|
cur_node = self.head |
|
while cur_node: |
|
elems.append(cur_node.data) |
|
cur_node = cur_node.next |
|
print(elems) |
|
|
|
# 使用链表 |
|
linked_list = LinkedList() |
|
linked_list.insert(1) |
|
linked_list.insert(2) |
|
linked_list.insert(3) |
|
linked_list.display() # 输出: [1, 2, 3] |
在上面的代码中，我们首先定义了一个Node类来表示链表的节点，每个节点都有一个data属性来存储数据，以及一个next属性来指向下一个节点。然后，我们定义了一个LinkedList类来表示整个链表，它有一个head属性来指向链表的第一个节点。我们还实现了两个方法：insert用于在链表的末尾插入一个新的节点，display用于打印链表中的所有元素。
链表的一个主要优点是它可以动态地分配内存，并且插入和删除操作的时间复杂度通常较低（在链表的头部或尾部操作时）。然而，链表也有一些缺点，比如访问特定元素的时间复杂度较高（需要从头节点开始遍历），以及需要额外的空间来存储指针。因此，在选择使用链表还是其他数据结构（如数组或树）时，需要根据具体的应用场景和需求进行权衡。
