双向链表专题-阿里云开发者社区

1. 双向链表的结构

注意：

这⾥的“带头”跟前面我们说的“头节点”是两个概念，带头链表里的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这里“放哨的”。

“哨兵位”存在的意义：遍历循环链表避免死循环。

2. 双向链表的实现

定义双向链表中节点的结构

//定义双向链表中节点的结构
typedef int LTDataType;
typedef struct ListNode
{
  LTDataType data;
  struct ListNode* prev;
  struct ListNode* next;
}LTNode;

初始化

注意，双向链表是带有哨兵位的，插入数据之前链表中必须要先初始化一个哨兵位

void LTInit(LTNode** pphead)
{
  *pphead = (LTNode*)malloc(sizeof(LTNode));
  if (NULL == *pphead)
  {
    perror("malloc fail!");
    exit(1);
  }
  (*pphead)->data = -1;
  (*pphead)->next = (*pphead)->prev = *pphead;
}

也可以这样写：

LTNode* LTInit()
{
  LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
  if (NULL == phead)
  {
    perror("malloc fail!");
    exit(1);
  }
  phead->data = -1;
  phead->next = phead->prev = phead;
  return phead;
}

尾插

概念： 当链表中只有哨兵位节点的时候，我们称该链表为空链表；即哨兵位是不能删除的。

不需要改变哨兵位，则不需要传二级指针；如果需要修改哨兵位的话，则传二级指针。

LTNode* LTBuyNode(LTDataType x)
{
  LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
  if (NULL == newnode)
  {
    perror("malloc fail!");
    exit(1);
  }
  newnode->data = x;
  newnode->next = newnode->prev = newnode;
  return newnode;
}
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* newnode = LTBuyNode(x);
  //phead phead->prev(ptail) newnode
  newnode->next = phead;
  newnode->prev = phead->prev;
  phead->prev->next = newnode;
  phead->prev = newnode;
}

因为写了申请新节点的函数，所以上面的初始化代码可以优化：

LTNode* LTInit()
{
  LTNode* phead = LTBuyNode(-1);
  return phead;
}

打印

void LTPrint(LTNode* phead)
{
  //phead不能为空
  assert(phead);
  LTNode* pcur = phead->next;
  while (pcur != phead)
  {
    printf("%d->", pcur->data);
    pcur = pcur->next;
  }
  printf("\n");
}

头插

//头插
void LTPushFront(LTNode* phead, LTDataType 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;
}

尾删

//尾删
void LTPopBack(LTNode* phead)
{
  assert(phead);
  //链表为空：只有一个哨兵位节点
  assert(phead->next != phead);//若哨兵位节点的next指针或者prev指针指向的是自己，说明当前链表为空
  LTNode* del = phead->prev;
  LTNode* prev = del->prev;
  prev->next = phead;
  phead->prev = prev;
  free(del);
  del = NULL;
}

头删

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

查找

LTNode* LTFind(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* pcur = phead->next;
  while (pcur != phead)
  {
    if (x == pcur->data)
    {
      return pcur;
    }
    pcur = pcur->next;
  }
  return NULL;
}

在pos位置之后插入数据

//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{
  assert(pos);
  LTNode* newnode = LTBuyNode(x);
  //pos newnode pos->next
  newnode->next = pos->next;
  newnode->prev = pos;
  pos->next->prev = newnode;
  pos->next = newnode;
}

删除pos位置的数据

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

销毁

void LTDesTroy(LTNode** pphead)
{
  assert(pphead);
  //哨兵位不能为空
  assert(*pphead);
  LTNode* pcur = (*pphead)->next;
  while (pcur != *pphead)
  {
    LTNode* next = pcur->next;
    free(pcur);
    pcur = next;
  }
  //链表中只有一个哨兵位
  free(*pphead);
  *pphead = NULL;
}

也可以这样写：

void LTDesTroy(LTNode* phead)
{
  //哨兵位不能为空
  assert(phead);
  LTNode* pcur = phead->next;
  while (pcur != phead)
  {
    LTNode* next = pcur->next;
    free(pcur);
    pcur = next;
  }
  //链表中只有一个哨兵位
  free(phead);
  phead = NULL;
}

但是要注意：这样写要在调用完函数后再写一句 plist = NULL;

这两种写法我们更推荐第二种：推荐传一级指针**（保持接口一致性）**

完整代码：

//List.h
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//定义双向链表中节点的结构
typedef int LTDataType;
typedef struct ListNode
{
  LTDataType data;
  struct ListNode* prev;
  struct ListNode* next;
}LTNode;
//注意，双向链表是带有哨兵位的，插入数据之前链表中必须要先初始化一个哨兵位
//void LTInit(LTNode** pphead);
LTNode* LTInit();
//void LTDesTroy(LTNode** pphead);
void LTDesTroy(LTNode* phead);//推荐传一级指针（保持接口一致性）
void LTPrint(LTNode* phead);
//概念：当链表中只有哨兵位节点的时候，我们称该链表为空链表；即哨兵位是不能删除的
//不需要改变哨兵位，则不需要传二级指针
//如果需要修改哨兵位的话，则传二级指针
void LTPushBack(LTNode* phead, LTDataType x);
void LTPushFront(LTNode* phead, LTDataType x);
//头删、尾删
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);
//删除pos位置的数据
void LTErase(LTNode* pos);

//List.c
#include "List.h"
//void LTInit(LTNode** pphead)
//{
//  *pphead = (LTNode*)malloc(sizeof(LTNode));
//
//  if (NULL == *pphead)
//  {
//    perror("malloc fail!");
//    exit(1);
//  }
//
//  (*pphead)->data = -1;
//  (*pphead)->next = (*pphead)->prev = *pphead;
//}
LTNode* LTBuyNode(LTDataType x)
{
  LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
  if (NULL == newnode)
  {
    perror("malloc fail!");
    exit(1);
  }
  newnode->data = x;
  newnode->next = newnode->prev = newnode;
  return newnode;
}
//LTNode* LTInit()
//{
//  LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
//
//  if (NULL == phead)
//  {
//    perror("malloc fail!");
//    exit(1);
//  }
//
//  phead->data = -1;
//  phead->next = phead->prev = phead;
//
//  return phead;
//}
LTNode* LTInit()
{
  LTNode* phead = LTBuyNode(-1);
  return phead;
}
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* newnode = LTBuyNode(x);
  //phead phead->prev(ptail) newnode
  newnode->next = phead;
  newnode->prev = phead->prev;
  phead->prev->next = newnode;
  phead->prev = newnode;
}
//头插
void LTPushFront(LTNode* phead, LTDataType 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;
}
void LTPrint(LTNode* phead)
{
  //phead不能为空
  assert(phead);
  LTNode* pcur = phead->next;
  while (pcur != phead)
  {
    printf("%d->", pcur->data);
    pcur = pcur->next;
  }
  printf("\n");
}
//尾删
void LTPopBack(LTNode* phead)
{
  assert(phead);
  //链表为空：只有一个哨兵位节点
  assert(phead->next != phead);//若哨兵位节点的next指针或者prev指针指向的是自己，说明当前链表为空
  LTNode* del = phead->prev;
  LTNode* prev = del->prev;
  prev->next = phead;
  phead->prev = prev;
  free(del);
  del = NULL;
}
//头删
void LTPopFront(LTNode* phead)
{
  assert(phead);
  assert(phead->next != phead);
  LTNode* del = phead->next;
  LTNode* next = del->next;
  //phead del next
  next->prev = phead;
  phead->next = next;
  free(del);
  del = NULL;
}
LTNode* LTFind(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* pcur = phead->next;
  while (pcur != phead)
  {
    if (x == pcur->data)
    {
      return pcur;
    }
    pcur = pcur->next;
  }
  return NULL;
}
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{
  assert(pos);
  LTNode* newnode = LTBuyNode(x);
  //pos newnode pos->next
  newnode->next = pos->next;
  newnode->prev = pos;
  pos->next->prev = newnode;
  pos->next = newnode;
}
//删除pos位置的数据
void LTErase(LTNode* pos)
{
  assert(pos);
  //pos->prev pos pos->next
  pos->next->prev = pos->prev;
  pos->prev->next = pos->next;
  free(pos);
  pos = NULL;
}
//void LTDesTroy(LTNode** pphead)
//{
//  assert(pphead);
//  //哨兵位不能为空
//  assert(*pphead);
//
//  LTNode* pcur = (*pphead)->next;
//
//  while (pcur != *pphead)
//  {
//    LTNode* next = pcur->next;
//    free(pcur);
//    pcur = next;
//  }
//
//  //链表中只有一个哨兵位
//  free(*pphead);
//  *pphead = NULL;
//}
void LTDesTroy(LTNode* phead)
{
  //哨兵位不能为空
  assert(phead);
  LTNode* pcur = phead->next;
  while (pcur != phead)
  {
    LTNode* next = pcur->next;
    free(pcur);
    pcur = next;
  }
  //链表中只有一个哨兵位
  free(phead);
  phead = NULL;
}

//Test.c
#include "List.h"
void ListTest01()
{
  //LTNode* plist = NULL;
  //LTInit(&plist);
  LTNode* plist = LTInit();
  //尾插
  //LTPushBack(plist, 1);
  //LTPushBack(plist, 2);
  //LTPushBack(plist, 3);
  //LTPushBack(plist, 4);
  //LTPrint(plist);
  //头插
  LTPushFront(plist, 1);
  LTPushFront(plist, 2);
  LTPushFront(plist, 3);
  LTPushFront(plist, 4);
  LTPrint(plist);
  //LTPopBack(plist);
  //LTPrint(plist);
  //LTPopBack(plist);
  //LTPrint(plist);
  //LTPopBack(plist);
  //LTPrint(plist);
  //LTPopBack(plist);
  //LTPrint(plist);
  LTPopBack(plist);
  LTPrint(plist);
  //头删
  //LTPopFront(plist);
  //LTPrint(plist);
  //LTPopFront(plist);
  //LTPrint(plist);
  //LTPopFront(plist);
  //LTPrint(plist);
  //LTPopFront(plist);
  //LTPrint(plist);
  LTPopFront(plist);
  LTPrint(plist);
  LTNode* findRet = LTFind(plist, 3);
  //if (NULL == findRet)
  //{
  //  printf("未找到！\n");
  //}
  //else
  //{
  //  printf("找到了！\n");
  //}
  //在指定位置之后插入数据
  //LTInsert(findRet, 66);
  //LTPrint(plist);
  //删除pos位置的节点
  LTErase(findRet);
  LTPrint(plist);
  //LTDesTroy(&plist);
  LTDesTroy(plist);
  plist = NULL;
}
int main()
{
  ListTest01();
  return 0;
}

双向链表专题

1. 双向链表的结构

2. 双向链表的实现

3. 顺序表和双向链表的优缺点分析

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

双向链表专题

1. 双向链表的结构

2. 双向链表的实现

3. 顺序表和双向链表的优缺点分析

热门文章

最新文章

相关电子书