从零开始学习嵌入式----数据结构之链表

目录

一、单向链表

二、双向链表

三、循环链表

四、 链表的操作

 五、 链表的优缺点

 六、图解

       链表是一种常见的数据结构，它由一系列节点组成，每个节点包含两部分：数据部分和指向下一个节点的指针。链表可以是单向的，也可以是双向的，甚至可以是循环的。

一、单向链表

       单向链表的每个节点包含一个数据字段和一个指向下一个节点的指针字段。单向链表的最后一个节点的指针通常指向`null`。

二、双向链表

       双向链表的每个节点包含一个数据字段和两个指针字段，分别指向前一个节点和后一个节点。双向链表的首尾节点的前一个指针和后一个指针都指向`null`。     

三、循环链表

       循环链表是一种特殊的链表，其最后一个节点的指针指向链表的第一个节点，形成一个闭环。 

四、 链表的操作

链表的基本操作包括：
1. **插入**：在链表的指定位置插入一个新节点。
2. **删除**：从链表中删除一个节点。
3. **查找**：查找链表中是否存在某个值的节点。
4. **遍历**：从头节点开始，依次访问链表中的每个节点。 

 
五、 链表的优缺点

（一）优点：
  - 插入和删除操作灵活，不需要移动其他元素。
  - 可以动态地增加节点。
  - 内存利用率高，不需要预先分配大块内存。

（二）缺点：
  - 访问某个元素的时间复杂度为T(n)=O(f(n))，因为需要从头节点开始遍历。
  - 需要额外的内存空间来存储指针。

       链表是数据结构中非常重要的一部分，广泛应用于各种算法和程序设计中。

 六、图解

       当然，让我们通过一些简单的图示来理解不同类型的链表。

（一） 单向链表（Singly Linked List）

单向链表的每个节点包含数据和指向下一个节点的指针。最后一个节点的指针指向`null`。

```
+----+------>+----+------>+----+------>+----+
|    |      |    |      |    |      |    |
| 1  |      | 2  |      | 3  |      | 4  |
+----+      +----+      +----+      +----+
```

在这个链表中：
       - 节点1的指针指向节点2。
       - 节点2的指针指向节点3。
       - 节点3的指针指向节点4。
       - 节点4的指针指向`null`。

（二） 双向链表（Doubly Linked List）

双向链表的每个节点包含数据和两个指针，分别指向前一个节点和后一个节点。

```
<----+----+------>+----+------>+----+------>+----+
      |    |      |    |      |    |      |    |
      | 1  |      | 2  |      | 3  |      | 4  |
      +----+      +----+      +----+      +----+
```

在这个链表中：
       - 节点1的前指针指向`null`，后指针指向节点2。
       - 节点2的前指针指向节点1，后指针指向节点3。
       - 节点3的前指针指向节点2，后指针指向节点4。
       - 节点4的前指针指向节点3，后指针指向`null`。

（三）循环链表（Circular Linked List）

循环链表的最后一个节点的指针指向链表的第一个节点，形成一个闭环。

```
+----+------>+----+------>+----+------>+----+
|    |      |    |      |    |      |    |
| 1  |      | 2  |      | 3  |      | 4  |
+----+      +----+      +----+      +----+
   ^                          |
   |                          v
```

在这个链表中：
      - 节点1的指针指向节点2。
      - 节点2的指针指向节点3。
      - 节点3的指针指向节点4。
      - 节点4的指针指向节点1，形成一个循环。

（四） 双向循环链表（Doubly Circular Linked List）

双向循环链表的每个节点包含数据和两个指针，分别指向前一个节点和后一个节点，并且首尾相连。

```
<----+----+------>+----+------>+----+------>+----+
      |    |      |    |      |    |      |    |
      | 1  |      | 2  |      | 3  |      | 4  |
      +----+      +----+      +----+      +----+
      ^                          |     ^
      |                          |     |
      +----+------>+----+------>+----+      +----+
         |    |      |    |      |    |      |
         | 4  |      | 1  |      | 2  |      | 3  |
         +----+      +----+      +----+      +----+
```

在这个链表中：
     - 节点1的前指针指向节点4，后指针指向节点2。
     - 节点2的前指针指向节点1，后指针指向节点3。
     - 节点3的前指针指向节点2，后指针指向节点4。
     - 节点4的前指针指向节点3，后指针指向节点1。

这些图示可以帮助你直观地理解链表的结构和节点之间的关系。