链表结构（广义表是一种单链表结构）

### 简介链表是一种常见的数据结构，用于存储一系列的元素。与数组不同，链表中的每个元素不仅包含数据本身，还包含指向列表中下一个元素的指针。这种结构使得链表在插入和删除操作上具有很高的效率，但访问特定元素的时间复杂度相对较高。链表分为单向链表、双向链表和循环链表等多种形式，每种形式都有其独特的应用场景。### 链表的基本概念#### 1. 节点(Node) -

定义

：链表的基本组成单元，通常由两部分构成：数据域（Data）和指针域（Next）。 -

作用

：存储实际的数据以及指向下一个节点的引用。#### 2. 头指针(Head Pointer) -

定义

：指向链表中第一个节点的指针。 -

作用

：作为访问整个链表的入口点。#### 3. 尾指针(Tail Pointer) -

定义

：指向链表中最后一个节点的指针。 -

作用

：在某些情况下，如在尾部插入元素时，尾指针可以提高效率。### 单向链表#### 1. 定义 -

单向链表

：每个节点只有一个指向下一个节点的指针，不支持反向遍历。#### 2. 结构 ```plaintext Node 1 -> Node 2 -> Node 3 -> ... -> Node n -> None ```#### 3. 操作 -

插入

- 在头部插入：新节点成为新的头节点。- 在中间插入：找到要插入的位置的前一个节点，修改其`next`指针。- 在尾部插入：找到尾节点，修改其`next`指针。 -

删除

- 删除头节点：将头指针指向当前头节点的下一个节点。- 删除中间节点：找到要删除节点的前一个节点，修改其`next`指针。- 删除尾节点：需要从头开始遍历到倒数第二个节点，修改其`next`指针。 -

查找

- 从头节点开始遍历，直到找到目标节点或遍历到链表末尾。### 双向链表#### 1. 定义 -

双向链表

：每个节点有两个指针，一个指向下一个节点，另一个指向前一个节点。#### 2. 结构 ```plaintext None <- Node 1 <-> Node 2 <-> Node 3 <-> ... <-> Node n -> None ```#### 3. 操作 -

插入

- 在头部插入：新节点成为新的头节点，并更新头节点的`prev`指针。- 在中间插入：找到要插入的位置的前后节点，修改它们的`next`和`prev`指针。- 在尾部插入：找到尾节点，修改其`next`指针，并更新新节点的`prev`指针。 -

删除

- 删除头节点：更新头节点的`next`指针，并修改新的头节点的`prev`指针。- 删除中间节点：找到要删除节点的前后节点，修改它们的`next`和`prev`指针。- 删除尾节点：找到倒数第二个节点，修改其`next`指针，并更新新尾节点的`prev`指针。 -

查找

- 从头节点开始正向遍历，也可以从尾节点开始反向遍历。### 循环链表#### 1. 定义 -

循环链表

：链表的最后一个节点指向第一个节点，形成一个闭环。#### 2. 结构 ```plaintext Node 1 -> Node 2 -> Node 3 -> ... -> Node n -> Node 1 ```#### 3. 操作 -

插入

- 在头部插入：新节点成为新的头节点，并将其`next`指针指向原头节点。- 在中间插入：找到要插入的位置的前一个节点，修改其`next`指针，并更新新节点的`next`指针。- 在尾部插入：找到尾节点，修改其`next`指针。 -

删除

- 删除头节点：将头指针指向当前头节点的下一个节点。- 删除中间节点：找到要删除节点的前一个节点，修改其`next`指针。- 删除尾节点：需要从头开始遍历到倒数第二个节点，修改其`next`指针。 -

查找

- 从头节点开始遍历，直到找到目标节点或再次回到头节点。### 总结链表作为一种基本的数据结构，在计算机科学中有着广泛的应用。不同的链表类型（单向链表、双向链表和循环链表）适用于不同的场景。理解这些链表的特点和操作方式对于选择合适的算法和数据结构至关重要。

简介链表是一种常见的数据结构，用于存储一系列的元素。与数组不同，链表中的每个元素不仅包含数据本身，还包含指向列表中下一个元素的指针。这种结构使得链表在插入和删除操作上具有很高的效率，但访问特定元素的时间复杂度相对较高。链表分为单向链表、双向链表和循环链表等多种形式，每种形式都有其独特的应用场景。

链表的基本概念

1. 节点(Node) - **定义**：链表的基本组成单元，通常由两部分构成：数据域（Data）和指针域（Next）。 - **作用**：存储实际的数据以及指向下一个节点的引用。

2. 头指针(Head Pointer) - **定义**：指向链表中第一个节点的指针。 - **作用**：作为访问整个链表的入口点。

3. 尾指针(Tail Pointer) - **定义**：指向链表中最后一个节点的指针。 - **作用**：在某些情况下，如在尾部插入元素时，尾指针可以提高效率。

单向链表

1. 定义 - **单向链表**：每个节点只有一个指向下一个节点的指针，不支持反向遍历。

2. 结构 ```plaintext Node 1 -> Node 2 -> Node 3 -> ... -> Node n -> None ```

3. 操作 - **插入**- 在头部插入：新节点成为新的头节点。- 在中间插入：找到要插入的位置的前一个节点，修改其`next`指针。- 在尾部插入：找到尾节点，修改其`next`指针。 - **删除**- 删除头节点：将头指针指向当前头节点的下一个节点。- 删除中间节点：找到要删除节点的前一个节点，修改其`next`指针。- 删除尾节点：需要从头开始遍历到倒数第二个节点，修改其`next`指针。 - **查找**- 从头节点开始遍历，直到找到目标节点或遍历到链表末尾。

双向链表

1. 定义 - **双向链表**：每个节点有两个指针，一个指向下一个节点，另一个指向前一个节点。

2. 结构 ```plaintext None <- Node 1 <-> Node 2 <-> Node 3 <-> ... <-> Node n -> None ```

3. 操作 - **插入**- 在头部插入：新节点成为新的头节点，并更新头节点的`prev`指针。- 在中间插入：找到要插入的位置的前后节点，修改它们的`next`和`prev`指针。- 在尾部插入：找到尾节点，修改其`next`指针，并更新新节点的`prev`指针。 - **删除**- 删除头节点：更新头节点的`next`指针，并修改新的头节点的`prev`指针。- 删除中间节点：找到要删除节点的前后节点，修改它们的`next`和`prev`指针。- 删除尾节点：找到倒数第二个节点，修改其`next`指针，并更新新尾节点的`prev`指针。 - **查找**- 从头节点开始正向遍历，也可以从尾节点开始反向遍历。

循环链表

1. 定义 - **循环链表**：链表的最后一个节点指向第一个节点，形成一个闭环。

2. 结构 ```plaintext Node 1 -> Node 2 -> Node 3 -> ... -> Node n -> Node 1 ```

3. 操作 - **插入**- 在头部插入：新节点成为新的头节点，并将其`next`指针指向原头节点。- 在中间插入：找到要插入的位置的前一个节点，修改其`next`指针，并更新新节点的`next`指针。- 在尾部插入：找到尾节点，修改其`next`指针。 - **删除**- 删除头节点：将头指针指向当前头节点的下一个节点。- 删除中间节点：找到要删除节点的前一个节点，修改其`next`指针。- 删除尾节点：需要从头开始遍历到倒数第二个节点，修改其`next`指针。 - **查找**- 从头节点开始遍历，直到找到目标节点或再次回到头节点。

总结链表作为一种基本的数据结构，在计算机科学中有着广泛的应用。不同的链表类型（单向链表、双向链表和循环链表）适用于不同的场景。理解这些链表的特点和操作方式对于选择合适的算法和数据结构至关重要。