数据结构从入门到精通：链表的分类

链表的分类

一、链表整体分类（8 种组合，重点掌握 3 类）

分类维度：单向 / 双向 + 带头结点 / 不带头结点 + 循环 / 非循环

💡考试 & 工程重点：带头单链表、不带头单链表、带头双向循环链表（掌握后剩余 5 种可快速举一反三）

二、单向链表 vs 双向链表

1. 单向链表局限

结点仅存data+next后继指针：

• 找后继：O(1)；找前驱：必须从头遍历O(n)
• 仅知道当前结点pos时，无法在pos前插入 / 删除结点

2. 双向链表结构

结点定义：

typedef int DLDataType;
typedef struct DLListNode {
DLDataType data;
struct DLListNode* prev; // 前驱指针
struct DLListNode* next; // 后继指针
}DNode, *DLinkList;

• 每个结点多prev前驱指针，前驱 / 后继访问均(O(1))，可就地前插、就地删除
• 短板：尾结点查找仍(O(n))，头尾增删边界处理繁琐（循环链表优化此问题）

三、循环链表（单向循环 / 双向循环）

1. 单向循环链表

尾结点next不再指向NULL，而是指向头结点； 短板：查找尾结点仍需遍历(O(n))。

2. 带头双向循环链表（工程首选，STL::list 底层）

• 尾结点next = 头结点，头结点prev = 尾结点
• 核心优势：头插、尾插、任意位置插入删除全为(O(1))，不需要尾指针

✅C++ STL 容器std::list底层就是带头双向循环链表

四、三种重点链表核心对比

💡补充考点

2. 单链表 + 单向循环链表 + 带头双向循环链表 

一、普通带头单链表

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int SLDataType;
// 结点结构体
typedef struct SListNode
{
SLDataType data;
struct SListNode* next;
}SNode, *SLList;

// 创建新结点
SNode* BuyListNode(SLDataType x)
{
SNode* newnode = (SNode*)malloc(sizeof(SNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}

// 初始化：带头结点，头结点next=NULL
void InitList(SLList* L)
{
*L = BuyListNode(-1);
(*L)->next = NULL;
}

// 求链表有效结点个数
int ListSize(SLList L)
{
assert(L);
int size = 0;
SNode* cur = L->next;
while (cur) // 单链表：cur!=NULL结束
{
size++;
cur = cur->next;
}
return size;
}

// 头插
void SLPushFront(SLList L, SLDataType x)
{
assert(L);
SNode* newnode = BuyListNode(x);
newnode->next = L->next;
L->next = newnode;
}

// 尾插
void SLPushBack(SLList L, SLDataType x)
{
assert(L);
SNode* cur = L;
while (cur->next != NULL)
cur = cur->next;
cur->next = BuyListNode(x);
}

// 遍历打印
void SLPrint(SLList L)
{
assert(L);
SNode* cur = L->next;
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\\n");
}

// 销毁
void SLDestroy(SLList L)
{
assert(L);
SNode* cur = L;
while (cur)
{
SNode* next = cur->next;
free(cur);
cur = next;
}
}

二、带头单向循环链表（对照讲义初始化 / 遍历区别）

typedef int CLDataType;
typedef struct CListNode
{
CLDataType data;
struct CListNode* next;
}CNode, *CLinkList;

CNode* BuyCListNode(CLDataType x)
{
CNode* newnode = (CNode*)malloc(sizeof(CNode));
newnode->data = x;
newnode->next = NULL;
return newnode;
}

// 循环链表初始化：头结点自环 next指向自己
void InitCList(CLinkList* L)
{
*L = BuyCListNode(-1);
(*L)->next = *L;
}

// 统计结点：循环链表结束条件 cur != L(头结点)
int CListSize(CLinkList L)
{
assert(L);
int size = 0;
CNode* cur = L->next;
while (cur != L)
{
size++;
cur = cur->next;
}
return size;
}

// 尾插 O(n)
void CLPushBack(CLinkList L, CLDataType x)
{
assert(L);
CNode* cur = L;
while (cur->next != L)
cur = cur->next;
CNode* newnode = BuyCListNode(x);
cur->next = newnode;
newnode->next = L;
}

// 遍历
void CLPrint(CLinkList L)
{
assert(L);
CNode* cur = L->next;
while (cur != L)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("(回到头)\\n");
}

// 销毁
void CLDestroy(CLinkList L)
{
assert(L);
CNode* cur = L->next;
while (cur != L)
{
CNode* next = cur->next;
free(cur);
cur = next;
}
free(L);
}

💡单链表与循环单链表核心区别（讲义考点）

三、带头双向循环链表

头文件 DCLList.h

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int DCLDataType;
typedef struct DCListNode
{
DCLDataType data;
struct DCListNode* prev;
struct DCListNode* next;
}DCListNode;

// 接口声明
DCListNode* DCListInit(); // 初始化
void DCListDestroy(DCListNode* L); // 销毁
DCListNode* DCListGetElem(DCListNode* L, int i); // 取第i个结点
void DCListInsert(DCListNode* pos, DCLDataType x); // pos前插入
void DCListErase(DCListNode* pos); // 删除pos结点
void DCListPushFront(DCListNode* L, DCLDataType x); // 头插
void DCListPushBack(DCListNode* L, DCLDataType x); // 尾插
void DCListPopFront(DCListNode* L); // 头删
void DCListPopBack(DCListNode* L); // 尾删
void DCListPrint(DCListNode* L); // 打印

源文件实现

#include "DCLList.h"

DCListNode* BuyDCNode(DCLDataType x)
{
DCListNode* newnode = (DCListNode*)malloc(sizeof(DCListNode));
newnode->data = x;
newnode->prev = NULL;
newnode->next = NULL;
return newnode;
}

// 初始化：头结点自环 prev=next=自己
DCListNode* DCListInit()
{
DCListNode* L = BuyDCNode(-1);
L->prev = L;
L->next = L;
return L;
}

// 销毁
void DCListDestroy(DCListNode* L)
{
assert(L);
DCListNode* cur = L->next;
while (cur != L)
{
DCListNode* next = cur->next;
free(cur);
cur = next;
}
free(L);
}

// 查找第i个下标结点(i从0开始)
DCListNode* DCListGetElem(DCListNode* L, int i)
{
assert(L && i >= 0);
DCListNode* cur = L->next;
int j = 0;
while (cur != L && j < i)
{
j++;
cur = cur->next;
}
if (j < i) return NULL; // 下标越界
return cur;
}

// 在pos结点前插入x O(1)
void DCListInsert(DCListNode* pos, DCLDataType x)
{
assert(pos);
DCListNode* prev = pos->prev;
DCListNode* newnode = BuyDCNode(x);

prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
}

// 删除pos结点 O(1)
void DCListErase(DCListNode* pos)
{
assert(pos);
DCListNode* p = pos->prev;
DCListNode* n = pos->next;
p->next = n;
n->prev = p;
free(pos);
}

// 头插：在头结点后面插入
void DCListPushFront(DCListNode* L, DCLDataType x)
{
DCListInsert(L->next, x);
}

// 尾插：在头结点前插入
void DCListPushBack(DCListNode* L, DCLDataType x)
{
DCListInsert(L, x);
}

// 头删
void DCListPopFront(DCListNode* L)
{
assert(L && L->next != L);
DCListErase(L->next);
}

// 尾删
void DCListPopBack(DCListNode* L)
{
assert(L && L->next != L);
DCListErase(L->prev);
}

// 遍历打印
void DCListPrint(DCListNode* L)
{
assert(L);
DCListNode* cur = L->next;
printf("头结点->");
while (cur != L)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("(回到头)\\n");
}

main 测试示例

int main()
{
DCListNode* dcl = DCListInit();
DCListPushBack(dcl,1);
DCListPushBack(dcl,2);
DCListPushFront(dcl,0);
DCListPrint(dcl); //头结点->0->1->2->(回到头)

DCListNode* pos = DCListGetElem(dcl,2);
DCListInsert(pos,99);
DCListPrint(dcl); //头结点->0->1->99->2->(回到头)

DCListPopBack(dcl);
DCListPrint(dcl);

DCListDestroy(dcl);
return 0;
}

💡核心考点总结