链表实现（链表实现电子相册）

## 链表实现### 简介链表是一种线性数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。与数组不同，链表中的节点可以在内存中非连续地存储，这使得它们在动态内存分配方面具有优势。链表广泛应用于各种数据结构和算法中，例如栈、队列、图和哈希表。### 链表类型常见的链表类型包括：#### 1. 单链表单链表是最基本类型的链表，每个节点只包含数据和指向下一个节点的指针。

结构:

```python class Node:def __init__(self, data):self.data = dataself.next = None ```

操作:

插入节点：在指定位置插入新节点，例如在头节点、尾节点或其他节点之前或之后插入。

删除节点：删除指定节点，包括头节点、尾节点或其他节点。

遍历链表：从头节点开始，依次访问每个节点，直到到达尾节点。#### 2. 双链表双链表与单链表类似，但每个节点除了指向下一个节点的指针外，还包含指向前一个节点的指针。

结构:

```python class Node:def __init__(self, data):self.data = dataself.prev = Noneself.next = None ```

操作:

插入节点：在指定位置插入新节点，操作类似于单链表，但需要更新前后节点的指针。

删除节点：删除指定节点，操作类似于单链表，但需要更新前后节点的指针。

双向遍历：可以从头节点或尾节点开始，向两个方向遍历链表。#### 3. 循环链表循环链表是单链表或双链表的一种特殊形式，其中尾节点的指针指向头节点，形成一个闭环。

结构:

```python # 单循环链表 class Node:def __init__(self, data):self.data = dataself.next = None# 双循环链表 class Node:def __init__(self, data):self.data = dataself.prev = Noneself.next = None ```

操作:

插入节点：插入节点操作类似于单链表或双链表，但需要更新尾节点的指针。

删除节点：删除节点操作类似于单链表或双链表，但需要更新尾节点的指针。

循环遍历：可以从任意节点开始，循环遍历链表。### 链表实现以下是用 Python 代码实现单链表和双链表的示例：#### 1. 单链表实现```python class Node:def __init__(self, data):self.data = dataself.next = Noneclass LinkedList:def __init__(self):self.head = Nonedef append(self, data):new_node = Node(data)if self.head is None:self.head = new_nodereturncurrent = self.headwhile current.next:current = current.nextcurrent.next = new_nodedef insert(self, data, index):new_node = Node(data)if index == 0:new_node.next = self.headself.head = new_nodereturncurrent = self.headcount = 0while current and count < index - 1:current = current.nextcount += 1if current is None:returnnew_node.next = current.nextcurrent.next = new_nodedef delete(self, data):if self.head is None:returncurrent = self.headprevious = Nonewhile current:if current.data == data:if previous is None:self.head = current.nextelse:previous.next = current.nextreturnprevious = currentcurrent = current.nextdef print_list(self):current = self.headwhile current:print(current.data, end=" ")current = current.nextprint()# 示例 linked_list = LinkedList() linked_list.append(1) linked_list.append(2) linked_list.append(3) linked_list.insert(4, 2) linked_list.delete(2) linked_list.print_list() # 输出: 1 4 3 ```#### 2. 双链表实现```python class Node:def __init__(self, data):self.data = dataself.prev = Noneself.next = Noneclass DoublyLinkedList:def __init__(self):self.head = Nonedef append(self, data):new_node = Node(data)if self.head is None:self.head = new_nodereturncurrent = self.headwhile current.next:current = current.nextcurrent.next = new_nodenew_node.prev = currentdef insert(self, data, index):new_node = Node(data)if index == 0:new_node.next = self.headif self.head:self.head.prev = new_nodeself.head = new_nodereturncurrent = self.headcount = 0while current and count < index - 1:current = current.nextcount += 1if current is None:returnnew_node.next = current.nextif current.next:current.next.prev = new_nodecurrent.next = new_nodenew_node.prev = currentdef delete(self, data):if self.head is None:returncurrent = self.headwhile current:if current.data == data:if current.prev is None:self.head = current.nextif self.head:self.head.prev = Noneelse:current.prev.next = current.nextif current.next:current.next.prev = current.prevreturncurrent = current.nextdef print_list(self):current = self.headwhile current:print(current.data, end=" ")current = current.nextprint()# 示例 doubly_linked_list = DoublyLinkedList() doubly_linked_list.append(1) doubly_linked_list.append(2) doubly_linked_list.append(3) doubly_linked_list.insert(4, 2) doubly_linked_list.delete(2) doubly_linked_list.print_list() # 输出: 1 4 3 ```### 链表的优缺点#### 优点：

动态内存分配：

链表的节点可以在运行时动态分配内存，无需预先知道数据的大小。

灵活插入和删除：

在链表中插入和删除节点比数组更容易，只需修改指针即可，无需移动其他节点。

存储不连续数据：

链表中的节点可以在内存中非连续地存储，适用于存储具有不规则结构的数据。#### 缺点：

随机访问困难：

要访问链表中的某个节点，需要从头节点开始遍历，无法直接访问特定索引的节点。

额外空间开销：

每个节点都需要额外的空间来存储指针，这会增加空间开销。

指针操作复杂：

链表的操作需要处理指针，比数组操作更复杂。### 应用场景链表适用于以下场景：

需要动态分配内存，数据大小未知。

需要频繁插入和删除节点。

需要存储具有不规则结构的数据。

栈、队列、图和哈希表等数据结构的实现。### 总结链表是一种灵活、高效的数据结构，它在各种数据结构和算法中扮演着重要角色。通过选择合适的链表类型，我们可以根据实际需求设计出满足特定需求的数据结构。

链表实现

简介链表是一种线性数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。与数组不同，链表中的节点可以在内存中非连续地存储，这使得它们在动态内存分配方面具有优势。链表广泛应用于各种数据结构和算法中，例如栈、队列、图和哈希表。

链表类型常见的链表类型包括：

1. 单链表单链表是最基本类型的链表，每个节点只包含数据和指向下一个节点的指针。**结构:**```python class Node:def __init__(self, data):self.data = dataself.next = None ```**操作:*** 插入节点：在指定位置插入新节点，例如在头节点、尾节点或其他节点之前或之后插入。 * 删除节点：删除指定节点，包括头节点、尾节点或其他节点。 * 遍历链表：从头节点开始，依次访问每个节点，直到到达尾节点。

2. 双链表双链表与单链表类似，但每个节点除了指向下一个节点的指针外，还包含指向前一个节点的指针。**结构:**```python class Node:def __init__(self, data):self.data = dataself.prev = Noneself.next = None ```**操作:*** 插入节点：在指定位置插入新节点，操作类似于单链表，但需要更新前后节点的指针。 * 删除节点：删除指定节点，操作类似于单链表，但需要更新前后节点的指针。 * 双向遍历：可以从头节点或尾节点开始，向两个方向遍历链表。

3. 循环链表循环链表是单链表或双链表的一种特殊形式，其中尾节点的指针指向头节点，形成一个闭环。**结构:**```python

单循环链表 class Node:def __init__(self, data):self.data = dataself.next = None

双循环链表 class Node:def __init__(self, data):self.data = dataself.prev = Noneself.next = None ```**操作:*** 插入节点：插入节点操作类似于单链表或双链表，但需要更新尾节点的指针。 * 删除节点：删除节点操作类似于单链表或双链表，但需要更新尾节点的指针。 * 循环遍历：可以从任意节点开始，循环遍历链表。

链表实现以下是用 Python 代码实现单链表和双链表的示例：

1. 单链表实现```python class Node:def __init__(self, data):self.data = dataself.next = Noneclass LinkedList:def __init__(self):self.head = Nonedef append(self, data):new_node = Node(data)if self.head is None:self.head = new_nodereturncurrent = self.headwhile current.next:current = current.nextcurrent.next = new_nodedef insert(self, data, index):new_node = Node(data)if index == 0:new_node.next = self.headself.head = new_nodereturncurrent = self.headcount = 0while current and count < index - 1:current = current.nextcount += 1if current is None:returnnew_node.next = current.nextcurrent.next = new_nodedef delete(self, data):if self.head is None:returncurrent = self.headprevious = Nonewhile current:if current.data == data:if previous is None:self.head = current.nextelse:previous.next = current.nextreturnprevious = currentcurrent = current.nextdef print_list(self):current = self.headwhile current:print(current.data, end=" ")current = current.nextprint()

示例 linked_list = LinkedList() linked_list.append(1) linked_list.append(2) linked_list.append(3) linked_list.insert(4, 2) linked_list.delete(2) linked_list.print_list()

输出: 1 4 3 ```

2. 双链表实现```python class Node:def __init__(self, data):self.data = dataself.prev = Noneself.next = Noneclass DoublyLinkedList:def __init__(self):self.head = Nonedef append(self, data):new_node = Node(data)if self.head is None:self.head = new_nodereturncurrent = self.headwhile current.next:current = current.nextcurrent.next = new_nodenew_node.prev = currentdef insert(self, data, index):new_node = Node(data)if index == 0:new_node.next = self.headif self.head:self.head.prev = new_nodeself.head = new_nodereturncurrent = self.headcount = 0while current and count < index - 1:current = current.nextcount += 1if current is None:returnnew_node.next = current.nextif current.next:current.next.prev = new_nodecurrent.next = new_nodenew_node.prev = currentdef delete(self, data):if self.head is None:returncurrent = self.headwhile current:if current.data == data:if current.prev is None:self.head = current.nextif self.head:self.head.prev = Noneelse:current.prev.next = current.nextif current.next:current.next.prev = current.prevreturncurrent = current.nextdef print_list(self):current = self.headwhile current:print(current.data, end=" ")current = current.nextprint()

示例 doubly_linked_list = DoublyLinkedList() doubly_linked_list.append(1) doubly_linked_list.append(2) doubly_linked_list.append(3) doubly_linked_list.insert(4, 2) doubly_linked_list.delete(2) doubly_linked_list.print_list()

输出: 1 4 3 ```

链表的优缺点

优点：* **动态内存分配：**链表的节点可以在运行时动态分配内存，无需预先知道数据的大小。 * **灵活插入和删除：**在链表中插入和删除节点比数组更容易，只需修改指针即可，无需移动其他节点。 * **存储不连续数据：**链表中的节点可以在内存中非连续地存储，适用于存储具有不规则结构的数据。

缺点：* **随机访问困难：**要访问链表中的某个节点，需要从头节点开始遍历，无法直接访问特定索引的节点。 * **额外空间开销：**每个节点都需要额外的空间来存储指针，这会增加空间开销。 * **指针操作复杂：**链表的操作需要处理指针，比数组操作更复杂。

应用场景链表适用于以下场景：* 需要动态分配内存，数据大小未知。 * 需要频繁插入和删除节点。 * 需要存储具有不规则结构的数据。 * 栈、队列、图和哈希表等数据结构的实现。

总结链表是一种灵活、高效的数据结构，它在各种数据结构和算法中扮演着重要角色。通过选择合适的链表类型，我们可以根据实际需求设计出满足特定需求的数据结构。