当前位置：首页 > article >正文

嵌入式学习（双向链表）

article 2024/12/25 1:28:00

在我们使用链表存储数据时，往往会从堆空间上申请空间。因此在使用完之后需要我们手动释放空间。

valgrind工具可以帮助我们检测在一段进程中申请的空间是否被释放完全。

在使用时：

valgrind + 运行文件：如 valgrind ./a.out

主要结构是由prev、next、data，这三个结构组成，通过prev找到前一个节点，next指向下一个节点。

结构：

在双向链表中同样可以实现单向链表中的头插，尾插，头删等操作。

此外，如用到结构体，结构体可以整体赋值。

比较单向链表和双向链表：

结构：

特点：

单向遍历：单向链表只能从头节点开始，按顺序向下遍历，直到链表的末尾。无法逆向遍历。
内存占用较少：每个节点只需要一个指针（指向下一个节点），因此占用的内存相对较少。
操作复杂度：
- 插入节点：在链表头插入效率较高，但在链表尾部插入需要遍历整个链表。
- 删除节点：如果要删除特定节点，需要从头遍历到目标节点的前一个节点

结构：

节点（Node）：每个节点包含三部分：
- 数据（Data）：存储节点的值。
- 前指针（Prev）：指向链表中前一个节点的指针。
- 后指针（Next）：指向链表中下一个节点的指针。

特点：

双向遍历：可以从链表的头节点向后遍历，也可以从链表的尾节点向前遍历。这种双向遍历特性使得某些操作更加灵活。
内存占用较多：每个节点需要两个指针（指向前一个节点和后一个节点），因此占用的内存比单向链表多。
操作复杂度：
- 插入节点：可以在链表的任意位置高效地插入节点，因为可以通过前后指针直接找到所需位置。
- 删除节点：由于可以通过前指针找到前一个节点，因此删除操作也更加高效。

内存有限：
- 内存占用：单向链表每个节点只包含一个指针，因此占用的内存较少。如果内存资源非常有限，单向链表是更合适的选择。
只需要单向遍历：
- 简单遍历：当只需要从头到尾的单向遍历时，单向链表更简单高效。例如，队列（FIFO）的实现通常使用单向链表，因为只需要从头部插入，从尾部删除。
操作集中在链表的头部：
- 高效插入和删除：如果插入和删除操作主要集中在链表的头部（如栈的实现），单向链表的效率更高，因为只需调整头指针即可。
数据的插入顺序较为简单：
- 顺序存储：如果数据的插入顺序是线性的且不需要复杂的插入操作（例如，追加到链表尾部），单向链表足够满足需求。

需要双向遍历：
- 双向访问：如果需要从任意节点向前或向后遍历链表，双向链表是必要的。例如，双向链表适用于实现双端队列（Deque），其中可以从两端进行插入和删除操作。
频繁插入和删除操作：
- 任意位置的高效操作：双向链表可以在链表的任意位置高效地插入或删除节点，因为可以通过前后指针快速找到前驱和后继节点。例如，某些缓存系统使用双向链表来管理元素的插入和删除，以便在 O(1) 时间内更新链表。
需要从尾部高效操作：
- 尾部插入/删除：如果需要频繁从链表尾部进行插入或删除操作，双向链表是更好的选择，因为你可以直接访问尾节点，而无需遍历整个链表。
实现复杂数据结构：
- 复杂数据结构：某些复杂的数据结构，如自平衡二叉搜索树或图的邻接表，可能需要双向链表来更灵活地管理节点和指针。