数据结构之双向链表与队列

三、双向链表

对比单向链表：新增前驱指针域，支持前后双向遍历。 API：创建、插入、删除、查找、修改、遍历、销毁

双向链表结构体定义

//存储业务数据类型

typedef struct stu

{

    char name[32];

    int age;

    int score;

}Data_t;

//双向链表结点

typedef struct dnode

{

    Data_t data;         // 数据域

    struct dnode *ppre;  // 前驱指针：指向前一个结点

    struct dnode *pnext; // 后继指针：指向后一个结点

}DNode_t;

//双向链表管理对象

typedef struct dlink

{

    DNode_t *phead;

    int clen;

}DLink_t;

四、Linux 内核链表

本质：双向循环链表

与普通链表核心区别

1.普通链表：数据封装在结点内部，一个链表只能存储单一类型数据；

2.内核链表：链表结点嵌入业务结构体内部，同一套链表接口可管理任意自定义数据类型。

核心宏

offsetof：计算结构体成员相对于结构体首地址的偏移量；

container_of：通过链表结点地址 + 偏移量，反向获取外层业务结构体首地址。

五、队列

定义

线性结构，一端插入（队尾，入队）、一端删除（队头，出队），遵循FIFO 先进先出。 应用场景：数据缓冲、任务排队。

队列 API

创建队列、入队、遍历、判空、出队、获取队头元素、销毁队列

链式队列

入队逻辑：尾指针指向新结点，更新尾指针

出队逻辑：释放头结点，更新头指针；若链表清空，头尾指针同步置空。