数据结构中的双向链表

数据结构中的双向链表

引用

CSDN

1.

https://blog.csdn.net/2401_84421190/article/details/141092571

双向链表是数据结构中一种重要的链式存储结构，它在单链表的基础上增加了指向前一个结点的指针，使得数据元素的访问更加灵活。本文将详细介绍双向链表的基本概念、实现方法以及常见操作的代码实现，帮助读者深入理解这一数据结构。

1.链表的分类

链表的结构非常多样，以下情况组合起来就是8种（2x2x2）链表结构：

在带头链表中，除了头结点，其他结点均存储有效的数据。
头结点是占位子的，也叫做“哨兵位”。head结点就是头结点。
循环的链表尾结点不为NULL， 不循环的链表尾结点为NULL
单链表：不带头单向不循环链表
双向链表：带头双向循环链表
双向链表结构相较于单链表来说要复杂一些，但是接口的实现上要比单链表简单很多
双向链表的结点结构：数据+指向下一个结点的指针+指向前一个结点的指针

  
struct ListNode
{
  int date;
  struct ListNode *next;
  struct ListNode *prev;
}  

2.双向链表的实现

2.1头结点的创建

  
//创建头节点
LTNode* LTBuyNode(LTDateType x)
{
    LTNode* newnode = (LTNode*)malooc(sizeof(LTNode);
    if (newnode == NULL)
    {
        perror("malloc fail");
        exit(1);
    }
    newnode->date = x;
    //因为是双向循环，要循环起来，所以头结点要自己指向自己。
    newnode->next = newnode->prev = newnode;
}
//初始化
void LTInit(LTNode** pphead)
{
    //创建一个头结点
    *pphead = LTBuyNode(-1);
}  

双向链表为空的情况就是只有一个头结点

2.2插入

传的是一级指针还是二级指针要看pphead指向的结点会不会发生改变，也就是头结点会不会发生改变。
如果发生改变，那么pphead的改变要影响实参，传二级
如果不发生改变，pphead不会影响实参，传一级。

2.2.1尾插

尾插影响的是尾插前一个结点和头结点，改变他们的指向就好了。
先修改插入的结点的指向，比较方便

  
//插入
//传的是一级指针还是二级指针要看pphead指向的结点会不会发生改变，也就是头结点会不会发生改变。
//如果发生改变，那么pphead的改变要影响实参，传二级
//如果不发生改变，pphead不会影响实参，传一级。
//尾插
void LTPushBack(LTNode* pphead, LTDateType x)
{
    assert(pphead);
    LTNode* newnode = LTBuyNode(x);
    //pphead pphead->prev newnode
    newnode->next = pphead;
    newnode->prev = pphead->prev;
    pphead->prev->next = newnode;
    pphead->prev = newnode;
}  

2.2.2头插

头插是在哨兵位与第一个有效结点之间插入数据，不是在哨兵位前插入数据，在哨兵位前插入数据是尾插。
受到影响的有哨兵位，第一个有效节点，还是先改插入newnode的指向。

  
void LTPushFront(LTNode* phead, LTDateType x)
{
    assert(phead);
    LTNode* newnode = LTBuyNode(x);
    //phead newnode phead->next
    newnode->next = phead->next;
    newnode->prev = phead;
    phead->next->prev = newnode;
    phead->next = newnode;
}
  

2.3双向链表的打印

双向链表的死循环的，为了让他不死循环，结束条件可以是不等于哨兵位。

  
//打印
void LTprint(LTNode* phead)
{
    LTNode* pcur = phead->next;
    while (pcur!=phead)
    {
        printf("%d->", pcur->date);
        pcur = pcur->next;
    }
    printf("\n");
}  

2.4判断链表是否为空

  
//判断链表是否为空
bool LTEmpty(LTNode* phead)
{
    assert(phead);
    //返回true表示链表为空，返回false表示链表不为空
    //非0表示true，0表示false。
    //如果phead->next == phead，返回1
    //如果phead->next ！= phead，返回0
    return phead->next == phead;
}  

2.5删除

不要把哨兵位删除，不会影响哨兵位，一级指针。
还要判断一下链表不为NULL，不然没东西删。

2.5.1尾删

思路：影响到的有尾结点的前一个结点以及哨兵位的结点，改变他们的指向，然后释放尾结点

  
void LTPopBack(LTNode* phead)
{
    assert(phead);
    //判断链表是否为NULL
    assert(!LTEmpty(phead));
    //phead prev(del->prev) del(phead->prev)
    LTNode* del = phead->prev;
    LTNode* prev = del->prev;
    prev->next = phead;
    phead->prev = prev;
    free(del);
    del = NULL;
}  

2.5.2头删

头删删的是哨兵位后面的结点，

  
//头删
void LTPopFront(LTNode* phead)
{
    assert(phead);
    assert(!LTEmpty(phead));
    //phead del(phead->next) del->next
    LTNode* del = phead->next;
    del->next->prev = phead;
    phead->next = del->next;
     
    free(del);
    del = NULL;
}  

2.6查找

  
//查找
LTNode* LTFind(LTNode* phead, LTDateType x)
{
    assert(phead);
    LTNode* pcur = phead->next;
    while (pcur != phead)
    {
        if (pcur->date == x)
        {
            return pcur;
        }
        pcur = pcur->next;
    }
    return NULL;
}  

2.7在指定位置（pos）之后插入节点

先改变newnode的指向，再改相邻的指向

  
//在指定位置（pos）之后插入节点
void LTInsert(LTNode* pos, LTDateType x)
{
    assert(pos);
    LTNode* newnode = LTBuyNode(x);
    //pos pos->prev pos->next
    newnode->prev = pos;
    newnode->next = pos->next;
    pos->next->prev = newnode;
    pos->next = newnode;
}  

2.8删除指定位置的结点

  
//删除指定位置的结点
void LTErase(LTNode* pos)
{
    assert(pos);
    //pos pos->prev pos->next
    pos->prev->next = pos->next;
    pos->next->prev = pos->prev;
    free(pos);
    pos = NULL;
}  

2.9销毁

二级指针，因为会影响到哨兵位。
从第一个有效的结点开始销毁。

  
//销毁
void LTDesTroy(LTNode** pphead)
{
    assert(pphead && *pphead);
    LTNode* pcur = (*pphead)->next;
    while (pcur!=*pphead)
    {
        LTNode* Next = pcur->next;
        free(pcur);
        pcur = Next;
    }
    free(*pphead);
    *pphead = NULL;
    pcur =	NULL;
}  

2.10初始化和销毁也可以是一级指针

这样做的目的是为了保证接口的一致性

1.销毁的一级指针

要在.h文件中手动置为NULL

  
//销毁
void LTDesTroy2(LTNode* phead)
{
    assert(phead);
    LTNode* pcur = phead->next;
    while (pcur != phead)
    {
        LTNode* Next = pcur->next;
        free(pcur);
        pcur = Next;
    }
    free(phead);
    pcur = phead = NULL;
}  

2.初始化的一级指针

  
//初始化
LTNode* LTInit2()
{
    LTNode* phead = LTBuyNode(-1);
    return phead;
}  

第1种方法要提前弄一个plist变量，传他的地址才能调用
第二种可以直接调用。