如何将带头双向循环链表（一）改写为长尾？

本文共计549个文字，预计阅读时间需要3分钟。

一、概念与结构无头单向非循环链表结构简单，一般不会单独用来存数据。实际中更多的是作为其他数据结构的子结构，如哈希桶、图的邻接表等。而带头双向循环链表的结構较为复杂。

一、概念与结构

无头单向非循环链表结构简单，一般不会单独用来存数据。实际中更多的是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。而带头双向循环链表的结构较为复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表，虽然它的结构复杂但是因为结构优势用代码实现起来会变得简单。 </br>

二、基本操作的实现

定义结构体

typedef int ListDataType;//类型重命名 typedef struct ListNode { ListDataType val; //结点数据 struct ListNode* prev;//指向上一个结点的指针 struct ListNode* next;//指向下一个结点的指针 }LTNode;

1.创建结点

LTNode* BuyListNode(ListDataType x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//申请空间 //判断是否为空 if (newnode == NULL) { perror("malloc"); exit(-1); } newnode->val = x; newnode->prev = NULL; newnode->next = NULL; return newnode; }

2.初始化链表

void ListInit(LTNode** pphead)//初始化 { //创建一个头节点 *pphead = (LTNode*)malloc(sizeof(LTNode));//初始化时将头结点置为-1; *pphead = BuyListNode(-1); //头节点 (*pphead)->next = *pphead; (*pphead)->prev = *pphead; } //LTNode* ListInit()//初始化 //{ // LTNode* phead = BuyListNode(-1);//初始化时将头结点置为-1; // phead->next = phead; // phead->prev = phead; // return phead; //}

初始化链表有两种方式，一种是有返回类型（注释部分），另一种是在初始化函数中给结构体开辟空间（不过注意参数要为二级指针）。因为是带头结点的循环链表，所以prev和next指针都指向自己。