手写链表（手写单链表）

# 简介在计算机科学中，链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据部分和指向下一个节点的引用（指针）。与数组不同的是，链表的内存分配是动态的，并且可以在运行时灵活地扩展或缩小。本文将详细介绍如何手写一个单向链表，包括其基本概念、实现细节以及一些常见操作。# 多级标题1. 链表的基本概念 2. 单向链表的结构设计 3. 链表节点的创建与初始化 4. 常见链表操作 - 插入元素 - 删除元素 - 查找元素 5. 示例代码展示 # 内容详细说明## 1. 链表的基本概念链表是一种线性数据结构，其中每个节点由两部分组成：一部分存储数据，另一部分存储指向下一个节点的引用。链表的首节点称为头节点，而最后一个节点的引用通常为null，表示链表的结束。链表的优点在于插入和删除操作非常高效，因为它不需要像数组那样进行大量的数据移动。然而，访问链表中的某个特定位置的元素效率较低，因为需要从头开始遍历。## 2. 单向链表的结构设计在单向链表中，每个节点包含两个主要部分： - 数据域：存储实际的数据。 - 指针域：存储指向下一个节点的引用。```python class ListNode:def __init__(self, data=0):self.data = dataself.next = None ```## 3. 链表节点的创建与初始化创建链表的第一步是初始化头节点。通常情况下，我们可以通过创建一个新的ListNode实例来完成这一任务。```python # 初始化链表 head = ListNode(1) second = ListNode(2) third = ListNode(3)# 连接节点 head.next = second second.next = third ```## 4. 常见链表操作### 插入元素在链表中插入新元素通常涉及更新现有节点的next指针。以下是插入一个新节点到链表中间的例子：```python def insert_node(head, position, data):new_node = ListNode(data)current = headfor _ in range(position - 1):if current is not None:current = current.nextnew_node.next = current.nextcurrent.next = new_node ```### 删除元素删除链表中的节点需要调整前后节点的指针关系。以下是如何删除指定位置的节点：```python def delete_node(head, position):if head is None:returntemp = headif position == 0:head = temp.nexttemp = Nonereturn headfor _ in range(position -1):temp = temp.nextif temp is None:breakif temp is None or temp.next is None:returnnext = temp.next.nexttemp.next = Nonetemp.next = next ```### 查找元素查找链表中的某个元素可以通过遍历链表并比较每个节点的数据来实现：```python def search_node(head, key):current = headwhile current != None:if current.data == key:return Truecurrent = current.nextreturn False ```## 5. 示例代码展示以下是一个完整的链表示例代码，包含了上述提到的所有功能：```python class ListNode:def __init__(self, data=0):self.data = dataself.next = Nonedef print_list(head):current = headwhile current:print(current.data, end=" -> ")current = current.nextprint("None")def main():# 创建链表head = ListNode(1)second = ListNode(2)third = ListNode(3)head.next = secondsecond.next = thirdprint("Original List:")print_list(head)# 插入新节点insert_node(head, 1, 10)print("After Insertion:")print_list(head)# 删除节点delete_node(head, 2)print("After Deletion:")print_list(head)# 查找节点key = 10found = search_node(head, key)print(f"Is {key} present? {'Yes' if found else 'No'}")if __name__ == "__main__":main() ```通过上述代码，我们可以看到如何手写一个简单的单向链表及其基本操作。希望这篇文章能帮助你更好地理解链表的概念和实现方式。

简介在计算机科学中，链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据部分和指向下一个节点的引用（指针）。与数组不同的是，链表的内存分配是动态的，并且可以在运行时灵活地扩展或缩小。本文将详细介绍如何手写一个单向链表，包括其基本概念、实现细节以及一些常见操作。

多级标题1. 链表的基本概念 2. 单向链表的结构设计 3. 链表节点的创建与初始化 4. 常见链表操作 - 插入元素 - 删除元素 - 查找元素 5. 示例代码展示

内容详细说明

1. 链表的基本概念链表是一种线性数据结构，其中每个节点由两部分组成：一部分存储数据，另一部分存储指向下一个节点的引用。链表的首节点称为头节点，而最后一个节点的引用通常为null，表示链表的结束。链表的优点在于插入和删除操作非常高效，因为它不需要像数组那样进行大量的数据移动。然而，访问链表中的某个特定位置的元素效率较低，因为需要从头开始遍历。

2. 单向链表的结构设计在单向链表中，每个节点包含两个主要部分： - 数据域：存储实际的数据。 - 指针域：存储指向下一个节点的引用。```python class ListNode:def __init__(self, data=0):self.data = dataself.next = None ```

3. 链表节点的创建与初始化创建链表的第一步是初始化头节点。通常情况下，我们可以通过创建一个新的ListNode实例来完成这一任务。```python

初始化链表 head = ListNode(1) second = ListNode(2) third = ListNode(3)

连接节点 head.next = second second.next = third ```

4. 常见链表操作

插入元素在链表中插入新元素通常涉及更新现有节点的next指针。以下是插入一个新节点到链表中间的例子：```python def insert_node(head, position, data):new_node = ListNode(data)current = headfor _ in range(position - 1):if current is not None:current = current.nextnew_node.next = current.nextcurrent.next = new_node ```

删除元素删除链表中的节点需要调整前后节点的指针关系。以下是如何删除指定位置的节点：```python def delete_node(head, position):if head is None:returntemp = headif position == 0:head = temp.nexttemp = Nonereturn headfor _ in range(position -1):temp = temp.nextif temp is None:breakif temp is None or temp.next is None:returnnext = temp.next.nexttemp.next = Nonetemp.next = next ```

查找元素查找链表中的某个元素可以通过遍历链表并比较每个节点的数据来实现：```python def search_node(head, key):current = headwhile current != None:if current.data == key:return Truecurrent = current.nextreturn False ```

5. 示例代码展示以下是一个完整的链表示例代码，包含了上述提到的所有功能：```python class ListNode:def __init__(self, data=0):self.data = dataself.next = Nonedef print_list(head):current = headwhile current:print(current.data, end=" -> ")current = current.nextprint("None")def main():

创建链表head = ListNode(1)second = ListNode(2)third = ListNode(3)head.next = secondsecond.next = thirdprint("Original List:")print_list(head)

插入新节点insert_node(head, 1, 10)print("After Insertion:")print_list(head)

删除节点delete_node(head, 2)print("After Deletion:")print_list(head)

查找节点key = 10found = search_node(head, key)print(f"Is {key} present? {'Yes' if found else 'No'}")if __name__ == "__main__":main() ```通过上述代码，我们可以看到如何手写一个简单的单向链表及其基本操作。希望这篇文章能帮助你更好地理解链表的概念和实现方式。