线性表之链表分类及双链表定义与实现

链表的分类

在了解单链表后，我们进一步分析链表的具体分类。通过属性组合，链表可分为多种类型，如带头单向循环链表、带头单向不循环链表、带头双向循环链表等。

• 带头和不带头：这里的'带头'指创建链表时申请一个不存放数据的头结点（哨兵位），它代表链表头，无论增删操作都指向该节点。不带头则没有这个哨兵位。
• 单向和双向：单向链表只有一个 next 指针指向后节点；双向链表除了 next 指针外，还有 prev 指针指向前节点，支持前后访问。
• 循环和不循环：不循环链表尾结点指向空指针；循环链表尾结点指向头结点，形成闭环。

通常所说的单链表完整名称为'单向不带头不循环链表'。而平常使用的双链表属于'双向带头循环链表'，其每个方法的时间复杂度基本达到 O(1)，效率较高，仅增加少量空间开销。

双链表的实现

双链表即双向带头循环链表，实现思路与单链表类似。

1. 双链表结构的定义

双链表不仅有一个指向下一个节点的 next 指针，还有一个指向上一个节点的 prev 指针。

typedef int LTDataType;
typedef struct ListNode {
  LTDataType data;
  struct ListNode* prev;
  struct ListNode* next;
} LTNode;

2. 双链表的初始化和销毁

双链表需要初始化以申请不保存数据的哨兵位节点。

初始化函数 1

在主函数中创建指针传参，由初始化函数申请哨兵位。注意双向链表是循环的，prev 和 next 需指向自己。

void LTInit1(LTNode** pphead) {
  assert(pphead);
  *pphead = (LTNode*)malloc(sizeof(LTNode));
  if(*pphead == NULL) {
    perror("malloc");
    return;
  }
  (*pphead)->next = (*pphead)->prev = *pphead;
}

初始化函数 2

直接在初始化函数中创建新节点并返回，推荐使用此方式。

LTNode* LTInit2() {
  LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
  if(newnode == NULL) {
    perror();
     ;
  }
  newnode->next = newnode->prev = newnode;
   newnode;
}