循环链表与双向链表

目前我所接触到的内容大多是单链表的一些代码，顾此处只重点介绍演示单链表，其他链表包括循环链表和双链表此处不做过多介绍，此处就让通义代笔了

循环链表(Circular Linked List)

循环链表是一种特殊的线性表，其最后一个节点的指针不是指向NULL，而是指向链表的第一个节点或者头节点，从而构成一个环状结构。

特点

1. 无明确终点：最后一个节点指向链表的第一个节点，形成闭环
2. 可以从任一节点开始遍历整个链表：无需从头节点开始
3. 适用于需要循环访问数据的场景：如约瑟夫问题等

结构示意图

普通单链表:

┌─────┬─────┐    ┌─────┬─────┐    ┌─────┬─────┐
│ data│ next│    │ data│ next│    │ data│ next│
│  1  │  ───┼───▶│  2  │  ───┼───▶│  3  │ NULL│
└─────┴─────┘    └─────┴─────┘    └─────┴─────┘
    ▲                                 
    │                                 
  HEAD                              

循环链表:

┌─────┬─────┐    ┌─────┬─────┐    ┌─────┬─────┐
│ data│ next│    │ data│ next│    │ data│ next│
│  1  │  ───┼───▶│  2  │  ───┼───▶│  3  │  ───┼───▶
└─────┴─────┘    └─────┴─────┘    └─────┴─────┘   │
     ▲                                            │
     │                                            │
   HEAD                                          │
     │                                            │
     └────────────────────────────────────────────┘

循环链表的优势

1. 操作统一性：插入和删除操作在任何位置都具有一致性
2. 遍历灵活性：可以从任意节点开始遍历整个链表
3. 适合循环问题：特别适用于需要循环处理的问题

双向链表(Doubly Linked List)

双向链表是每个节点都有两个指针域的链表，分别指向前驱节点和后继节点，使得链表可以从两个方向进行遍历。

特点

1. 双向遍历：可以从任一节点向前或向后遍历
2. 操作便利：插入和删除操作更容易实现
3. 额外开销：每个节点需要多一个指针域，占用更多内存

结构示意图

双向链表结构:
        NULL                            NULL
          ▲                               ▲
          │                               │
┌─────────┼─────────┐    ┌─────────┐    ┌─┼─────────┐
│  prev   │   data  │    │  prev   │    │ │   data  │    │  prev   │   data  │
│   NULL  │    1    │◀───│         │◀───┤ │    2    │◀───┤         │    3    │
├─────────┼─────────┤    ├─────────┤    ├─┼─────────┤    ├─────────┼─────────┤
│  next   │         │───▶│  next   │───▶│ │  next   │───▶│  next   │  NULL   │
└─────────┴─────────┘    └─────────┘    └───────────┘    └─────────┴─────────┘
          ▲                               ▲
          │                               │
        HEAD                            TAIL

双向链表的优势

1. 双向访问：可以从前向后或从后向前遍历链表
2. 操作简化：在已知节点位置的情况下，插入和删除操作更加简便
3. 反向遍历：可以轻松实现反向遍历功能

循环双向链表

循环双向链表是将循环链表和双向链表结合形成的链表结构，既具备双向链表的双向遍历特性，又具备循环链表的闭环特性。

结构示意图

循环双向链表:
┌─────────┬─────────┬─────────┐    ┌─────────┬─────────┬─────────┐
│  prev   │   data  │  next   │    │  prev   │   data  │  next   │
│         │    1    │         │◀──▶│         │    2    │         │
├─────────┼─────────┼─────────┤    ├─────────┼─────────┼─────────┤
│         │         │         │    │         │         │         │
└─────────┴─────────┴─────────┘    └─────────┴─────────┴─────────┘
  ▲                                   ▲
  │                                   │
  └───────────────────────────────────┘

各种链表结构对比总结

这些链表结构各有特点，可以根据具体应用场景选择合适的链表类型。