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

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. 顺序表和双向链表的优缺点分析

热门文章

最新文章

相关电子书