柚子快报激活码778899分享：【数据结构】双向链表详解
当我们学习完单链表后，双向链表就简单的多了，双向链表中的头插，尾插，头删，尾删，以及任意位置插，任意位置删除比单链表简单，今天就跟着小张一起学习吧！！
双向链表的分类
双向不带头链表
双向带头循环链表
还有双向带头不循环链表，双向不带头循环链表，着重使用双向带头循环链表，带头也就是有哨兵位。
双向带头循环链表
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。
双向循环链表的接口实现
ListNode* ListCreate(int x)//创建新结点
ListNode* createhead()//创建哨兵位
void ListPushBack(ListNode* phead, int x)//尾插
void SListPrint(ListNode* phead)//打印链表
void SListPushFront(ListNode* phead, int x)//头插
void SListPopBack(ListNode* phead)//尾删
void SListPopFront(ListNode* phead)//头删
void SListInsert(ListNode* pos, int x)//pos前插
void SListErase(ListNode* pos)//删除pos;
ListNode* SListFind(ListNode* phead,int x)//查找链表中第一个x
0.结点结构体创建
typedef struct ListNode
{
int data;//数据
struct ListNode* next;//下个结点地址
struct ListNode* prev;//上个结点地址
}ListNode;
1.创建一个新结点
ListNode* ListCreate(int x)//创建新结点
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));//给新结点申请空间
if (newnode == NULL)
{
perror("malloc error");//没申请到，malloc返回NULL给newnode
}
newnode->data = x;//新结点的数据给x
newnode->next = NULL;//新结点的下一个结点地址为空
newnode->prev = NULL;//新结点的上一个结点地址为空
return newnode;//新结点的地址返回回去
}
2.创建哨兵位
该哨兵位作为链表的头结点，不存数据
ListNode* createhead()
{
ListNode* head = ListCreate(-1);//哨兵位结点的数据随便给个-1
head->next = head;
head->prev = head;
return head;//返回哨兵位的头结点地址
}
当没有带数据的新结点时，先让他上一个结点地址，和下一关结点地址都存入head自己的地址
3.尾插
void ListPushBack(ListNode* phead, int x)//尾插
{
ListNode* newnode = ListCreate(int x);
ListNode* tail = phead->prev;//记录尾结点的地址
newnode->prev =tail;//新结点的prev存放尾结点的地址-1
newnode->next = phead;//新结点的next存放头结点哨兵位的地址->2
phead->prev = newnode;//头结点的prev存放新结点的地址->4
tail->next = newnode;//尾结点的next存放新节点的地址->3
}
分析： 由于使用tail记录了尾结点的地址，所以1，2，3，4可以任意切换顺序，如果没有记录，记得先将新结点的prev,next,先保存，然后在修改head->prev, head->prev->next;防止修改过程中，尾结点的地址丢失。 同样适用于在哨兵位后插新结点
4.打印双链表
void SListPrint(ListNode* phead)//打印链表
{
ListNode* cur = phead->next;
while (cur != phead)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("\n");
}
分析：定义一个指针cur遍历整个链表，由于是循环链表，肯定会指向哨兵位，哨兵位结点的数据不使用，所以cur指针从头节点哨兵位的下一个结点开始遍历，直到cur==phead,循环结束，每次打印cur->data,然后移动cur到下一个结点。
5.头插
void SListPushFront(ListNode* phead, int x)//头插
{
ListNode* newnode = ListCreate(x);
newnode->next = phead->next;
phead->next->prev = newnode;
newnode->prev = phead;
phead->next = newnode;
}
分析： 注意：先保存newnode->next;和newnode->prev; 此时如果先进行4的话，phead->next的地址就变成了newnode,之前的phead->next地址丢失掉。 还有一种方法是先保存* next=phead->next;然后1，2，3，4，顺序可以调换。
6.尾删
void SListPopBack(ListNode* phead)//尾删
{
ListNode* last = phead->prev->prev;//记录尾结点的上一个结点的地址
phead->prev = last;//头节点哨兵位的prev存入last的地址
last->next = phead;//last的next存入phead的地址
}
分析：当要删除尾结点，我们可以先记录尾结点的上一个结点的地址，因为要删除尾结点，改变就是将尾结点的上一个结点last的next存phead的地址，phead的prev存入的是last的地址 除哨兵位还有一个结点的尾删剩下一个哨兵位头结点，同样适用上面的代码
7.头删
void SListPopFront(ListNode* phead)//头删
{
ListNode* next = phead->next;
phead->next = next->next;
next->next->prev = phead;
}
分析：先保存哨兵位的下一个结点地址到next,然后将phead的next中存入next->next;将next->next->prev存入phead的首地址
8.pos指针指向的结点前插
void SListInsert(ListNode* pos, int x)//pos前插
{
ListNode* newnode = ListCreate(x);//申请新结点将地址存放在newnode变量中
newnode->next = pos;//新结点的下一个结点保存pos指针指向节点的地址
newnode->prev = pos->prev;//新结点的prev保存pos指针指向的节点的上一个节点的地址
pos->prev->next=newnode;//pos指针指向的节点的前一个结点的next保存newnode指针指向的结点
pos->prev = newnode;//pos指针指向的结点的prev保存newnode指针指向结点的地址
}
分析：
9.删除pos指针指向的结点
void SListErase(ListNode* pos)//删除pos;
{
ListNode* last = pos->prev;//记录pos指针指向结点的前一个结点地址
ListNode* next = pos->next;//记录pos指针指向结点的后一个结点地址
last->next = next;//操作1
next->prev = last;//操作2
}
分析：
10.查找链表第一个出现的x
ListNode* SListFind(ListNode* phead,int x)
{
ListNode* cur = phead->next;//cur指针先指向phead的下一个结点的位置
while (cur != phead)//循环遍历
{
if (cur->data == x)//第一次找到
{
return cur;返回结点数据等于x的地址
}
cur = cur->next;//cur指针指向下一个结点
}
return NULL;
}
分析：类似于打印打印链表，遍历循环，从phead->next开始遍历，当cur不等于phead继续循环，如果cur->datax,就return cur的内容，也就是datax的结点地址，循环结束没有找到的话，就是该链表没有等于x的结点返回NULL;
11.双向链表的销毁
void Destroy(ListNode* phead)
{
ListNode* cur = phead->next;
while (cur != phead)
{
ListNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
}
分析，定义一个指针cur先指向phead的下一个结点，开始遍历，先保存cur指向结点的下一个结点的地址到next,然后释放掉cur指针指向的空间，然后让cur指向已经保存在next中下一个结点的地址，依次循环释放掉所有的结点，循环结束，释放掉哨兵位。
12.完整源码
#include
#include
typedef struct ListNode
{
int data;
struct ListNode* next;
struct ListNode* prev;
}ListNode;
ListNode* ListCreate(int x)//创建新结点
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
if (newnode == NULL)
{
perror("malloc error");
//return;
}
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
ListNode* createhead()
{
ListNode* head = ListCreate(-1);
head->next = head;
head->prev = head;
return head;
}
void ListPushBack(ListNode* phead, int x)//尾插
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
newnode->data = x;
ListNode* tail = phead->prev;
newnode->prev =tail;
phead->prev = newnode;
tail->next = newnode;
newnode->next = phead;
}
void SListPrint(ListNode* phead)//打印链表
{
ListNode* cur = phead->next;
while (cur != phead)
{
printf("%d->",cur->data);
cur = cur->next;
}
printf("\n");
}
void SListPushFront(ListNode* phead, int x)//头插
{
ListNode* newnode = ListCreate(x);
newnode->next = phead->next;
phead->next->prev = newnode;
newnode->prev = phead;
phead->next = newnode;
}
void SListPopBack(ListNode* phead)//尾删
{
ListNode* last = phead->prev->prev;
phead->prev = last;
last->next = phead;
}
void SListPopFront(ListNode* phead)//头删
{
ListNode* next = phead->next;
phead->next = next->next;
next->next->prev = phead;
}
void SListInsert(ListNode* pos, int x)//pos前插
{
ListNode* newnode = ListCreate(x);
newnode->next = pos;
newnode->prev = pos->prev;
pos->prev->next=newnode;
pos->prev = newnode;
}
void SListErase(ListNode* pos)//删除pos;
{
ListNode* last = pos->prev;
ListNode* next = pos->next;
last->next = next;
next->prev = last;
}
ListNode* SListFind(ListNode* phead,int x)
{
ListNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
//双链表的销毁
void Destroy(ListNode* phead)
{
ListNode* cur = phead->next;
while (cur != phead)
{
ListNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
}
int main()
{
ListNode* list;
list = createhead();
printf("尾插:");
ListPushBack(list,1);
ListPushBack(list,2);
ListPushBack(list,3);
ListPushBack(list,4);
SListPrint(list);
printf("头插:");
SListPushFront(list, 8);
SListPushFront(list, 7);
SListPushFront(list, 6);
SListPushFront(list, 5);
SListPrint(list);
printf("尾删:");
SListPopBack(list);
SListPopBack(list);
SListPrint(list);
printf("头删:");
SListPopFront(list);
SListPopFront(list);
SListPopFront(list);
SListPrint(list);
printf("插入pos指向结点前面:");
SListInsert(list->next->next, 1000);
SListPrint(list);
printf("删除pos指向的结点:");
SListErase(list->next->next);
SListPrint(list);
printf("查找第一个x的位置并打印出来:");
ListNode* p=SListFind(list, 8);
printf("%d", p->data);
printf("修改查找到的结点:\n");
p->data = 10000;
SListPrint(list);
printf("销毁打印销毁后哨兵位的下一个结点的数据,如果为随机值说明已经被销毁：");
Destroy(list);
printf("%d",list->data);
}
13.编译运行
柚子快报激活码778899分享：【数据结构】双向链表详解
发表评论