双向链表的操作-阿里云开发者社区

前言

在前面的单链表专题中，我们了解到了链表的一共有八种结构，但是最常用的链表结构还是单链表中的不带头单向不循环链表和双链表中的带头双向循环链表。

带头双向循环链表

每个结点有三个内容：

1、保存的数据data

2、保存下一个结点的地址next指针

3、保存前一个结点的地址的prev指针

双向链表的结构定义

//定义双向链表结点的结构
typedef int LTDataType;
struct ListNode {
  LTDataType data;//保存的数据
  struct ListNode* next;  //指向下一个结点的指针next
  struct ListNode* prev;  //指向上一个结点的指针prev
};
typedef struct ListNode LTNode;

链表的初始化

在这里我们进行插入和删除等操作时函数传参时是一个一级指针而非二级，这是因为我们的带头双向不循环链表在开始时便已经有了一个哨兵位，我们只需要使用指向该哨兵位的指针就可以实现对其它有效结点的操作，至于为什么有了哨兵位就能这样是因为创建哨兵位的过程导致的，听我给你细细道来：

我们使用的函数是LTInit()，它不需要传入指针啊地址之类的实参，我们只是想用它来获取一个我们创建好的内存空间的地址（哨兵位的地址）而已，这样就避免了之前传递指针时出现的”形参是实参的拷贝“的问题，现在我们只要一个地址，然后用一个链表结构体类型（LTNode*）的指针变量plist来接收该地址，而该地址所对应的内存空间是用malloc开辟的所以即使出了函数也不会被释放，此时plist就是指向哨兵位的指针，在后续插入操作时就可以直接使用plist了，虽然插入和删除等函数中还会有一级指针的存在不过它们都是作为plist的替身替我们完成对链表的插入和删除操作罢了......

带头的链表传参时使用的是二级指针，不带头的链表传参时使用的是一级指针

至于使用哨兵位后到底简不简单请往下看：

//test.c文件：
#include "List.h"
void ListTest()
{ 
  LTNode* plist = LTInit();
}
int main()
{
  ListTest();
  return 0;
}
//SList.c文件：
#include "List.h" 
LTNode* LTInit()
{
    //用phead指针指向为哨兵位申请的内存空间
  LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
    //如果不存在哨兵位
  if (phead == NULL)
  {
    perror("malloc error");
    return;
  }
    //哨兵位中不存储有效数据，我们这里给它存一个-1表示无效数据就行
  phead->data = -1;
    //对哨兵位的前驱和后继指针实现一个循环效果
  phead->next = phead->prev = phead;
  //返回新创建的哨兵位
  return phead;
}

（这里的应该是phead忘记改了┭┮﹏┭┮）

通过调试可以发现两种方法都实现了循环效果

尾插

//申请新结点node，并为其存储数据x
LTNode* ListByNode(LTDataType x)
{
  LTNode* node = (LTNode*)malloc(sizeof(LTNode));
  node->data = x;
  node->next = node->prev = NULL;
  return node;
}
//尾插
void LTPushBack(LTNode* phead,LTDataType x)
{
    //必须要有哨兵位
  assert(phead);
  LTNode* node = ListByNode(x);
  //先处理新节点node的前驱和后继指针
  node->prev = phead->prev;
  node->next = phead;
  //再处理哨兵位的上一个结点的的后继指针（相当于图里的d3）和哨兵位的前驱指针
  phead->prev->next = node;
  phead->prev = node;
}

（关于成功演示，这里只看一个结果，具体代码会一起放在test.c文件中）

头插

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
  //必须要有哨兵位
  assert(phead);
  LTNode* node = ListByNode(x);
  //先处理新节点node的前驱和后继指针
  node->prev = phead;
  node->next = phead->next;
  //再处理phead->prev(之前的尾结点)和phead
  phead->next->prev = node;
  phead->next = node;
}

尾删

//尾删
void LTPopBack(LTNode* phead)
{
  //必须要有哨兵位
  assert(phead);
    //除了保证有哨兵位之外，还需要保证链表必须要有有效结点，只有哨兵位时不能执行删除操作
  assert(phead->next != phead);
    //这里的del就相当于d2
  LTNode* del = phead->prev;
  //先处理del的prev结点
  del->prev->next = phead;
  //处理phead
  phead->prev = del->prev;
  free(del);
  del = NULL;
}

字体懒得再写一遍改成蓝色的了，将就着看吧┭┮﹏┭┮

头删

//头删
void LTPopFront(LTNode* phead)
{
  //除了保证有哨兵位之外，还需要保证链表必须要有有效结点，只有哨兵位时不能执行删除操作
  assert(phead->next != phead);
  LTNode* del = phead->next;
  //phead del->next
  del->next->prev = phead;
  phead->next = del->next;
  free(del);
  del = NULL;
}

结点的查找

//查找结点
LTNode* LTFind(LTNode* phead, LTDataType x)
{
    //保证有哨兵位
  assert(phead);
  LTNode* cur = phead->next;
    //遍历链表
  while (cur != phead)//不能等于哨兵位
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}

在指定位置后插入

//在pos位置后插入数据
void LTInsert(LTNode* pos, LTDataType x) 
{
  assert(pos);
  LTNode* node = ListByNode(x);
  //node的prev和next
  node->next = pos->next;
  node->prev = pos;
  //pos的next职责和pos->next的prev
  pos->next = node;
  node->next->prev = node;
}

删除指定位置结点

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

链表的销毁

//销毁链表
void LTDestory(LTNode* phead)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    LTNode* next = cur->next;
    free(cur);
    cur = next;
  }
  //除了循环之后，哨兵位还未释放
  free(phead);
  phead = NULL;
}

接下来是我们在链表销毁时开启的监视窗口，虽然可能有点长但是还请看完：

程序结束后：

我们会发现即使程序结束后，phea的值已经被置空但是plist的值并未被置空......

这是因为我们用于接收plist的是一个一级指针phead，对于一级指针phead的改变并不会影响plist（前面单链表中我们了解到对二级指针一次解引用后才能修改plist） ,所以当我们传递一级指针时需要手动在test.c文件中的销毁链表函数后添加一个free(plist)

最终结果：

SList.h文件：

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
//定义双向链表结点的结构
typedef int LTDataType;
struct ListNode {
  LTDataType data;//保存的数据
  struct ListNode* next;
  struct ListNode* prev;
};
typedef struct ListNode LTNode;
//链表的初始化
LTNode* LTInit(); //不需要传入参数，调用该方法后直接返回一个头结点
//因为这是带头双向循环链表，在初始状态时，双向链表为空（只有一个哨兵位），哨兵位结点是不能被操作，
//即哨兵位不能被改变的，所以我们就不需要像之前的不带头单向不循环链表一样需要修改头结点
//哨兵位的下一个结点是链表的第一个结点（头结点），而哨兵位下一个结点是链表的最后一个结点（尾结点） 
//我们在这里规定：称后续的链表的第一个有效结点为链表的头结点，链表的最后一个结点叫做尾结点，原来的头结点现在我们称之为哨兵位
//尾部插入操作（往哨兵位的前一个位置插入也叫尾插）
void LTPushBack(LTNode* phead, LTDataType x);
//打印
void LTPrint(LTNode* phead);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//尾删
void LTPopBack(LTNode* phead);
//头删
void LTPopFront(LTNode* phead);
//在指定位置后插入
void LTInsert(LTNode* pos, LTDataType x);
//删除指定位置
void LTErase(LTNode* pos);
//查找结点
LTNode* LTFind(LTNode* phead, LTDataType x);
//销毁链表
void LTDestory(LTNode* phead);

SList.c文件：

#include "List.h" 
//不需要传入参数，调用该方法后我们返回一个头结点
LTNode* LTInit()
{
  LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
  if (phead == NULL)
  {
    perror("malloc error");
    return;
  }
  phead->data = -1;
  phead->next = phead->prev = phead;
  //返回新创建的头结点
  return phead;
}
//申请新结点node，并为其存储数据x
LTNode* ListByNode(LTDataType x)
{
  LTNode* node = (LTNode*)malloc(sizeof(LTNode));
  node->data = x;
  node->next = node->prev = NULL;
  return node;
}
//尾插
void LTPushBack(LTNode* phead,LTDataType x)
{
  assert(phead);
  LTNode* node = ListByNode(x);
  //先处理新节点node的前驱和后继指针
  node->prev = phead->prev;
  node->next = phead;
  //再处理phead->prev(之前的尾结点)和phead
  phead->prev->next = node;
  phead->prev = node;
}
//打印
void LTPrint(LTNode* phead)
{
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("\n");
}
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* node = ListByNode(x);
  //先处理新节点node的前驱和后继指针
  node->prev = phead;
  node->next = phead->next;
  //再处理phead->prev(之前的尾结点)和phead
  phead->next->prev = node;
  phead->next = node;
}
//尾删
void LTPopBack(LTNode* phead)
{
  assert(phead);
  assert(phead->next != phead);
  LTNode* del = phead->prev;
  //先处理del的prev结点
  del->prev->next = phead;
  //处理phead
  phead->prev = del->prev;
  free(del);
  del = NULL;
}
//头删
void LTPopFront(LTNode* phead)
{
  assert(phead && phead->next != phead);
  LTNode* del = phead->next;
  //phead del->next
  del->next->prev = phead;
  phead->next = del->next;
  free(del);
  del = NULL;
}
//在指定位置后插入
void LTInsert(LTNode* pos, LTDataType x) 
{
  assert(pos);
  LTNode* node = ListByNode(x);
  //node的prev和next
  node->next = pos->next;
  node->prev = pos;
  //pos的next职责和pos->next的prev
  pos->next = node;
  node->next->prev = node;
}
//删除指定位置
void LTErase(LTNode* pos)
{
  assert(pos);
  //pos->prev:next pos pos->next:prev
  pos->next->prev = pos->prev;
  pos->prev->next = pos->next;
  free(pos);
  pos = NULL;
}
//查找结点
LTNode* LTFind(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}
//销毁链表
void LTDestory(LTNode* phead)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    LTNode* next = cur->next;
    free(cur);
    cur = next;
  }
  //除了循环之后，哨兵位还未释放
  free(phead);
  phead = NULL;
}

test.c文件：

#include "List.h"
void ListTest()
{ 
  LTNode* plist = LTInit();
  LTPushBack(plist, 1);
  LTPushBack(plist, 2);
  LTPushBack(plist, 3);
  LTPushBack(plist, 4);
  LTPushBack(plist, 5);//1->2->3->4->5->
  //LTPrint(plist);
  //LTPushFront(plist, 6);
  //LTPushFront(plist, 7);
  //LTPushFront(plist, 8);//8->7->6->1->2->3->4->5->
  //LTPrint(plist);
  /*LTPopBack(plist);
  LTPopBack(plist);
  LTPopBack(plist);
  LTPrint(plist);*/
  //LTPopFront(plist);
  //LTPopFront(plist);
  //LTPopFront(plist);
  //LTPopFront(plist);
  //LTPopFront(plist);
  //LTPrint(plist);
  //LTNode* find = LTFind(plist, 2);
  ///*LTInsert(find, 11);*/
  LTErase(find);
  LTPrint(plist);
  LTDestory(plist);
  传递一级指针时需要手动将plist置为空
  //plist = NULL;
}
int main()
{
  ListTest();
  return 0;
}

顺序表和链表的优缺点分析

不同点	顺序表	链表
存储空间上	物理上一定连续	逻辑上连续但物理上不一定连续
随机访问	支持O（1）	不支持：O（N）
任意位置插入或删除元素	可能需要移动元素，效率低O（N）	只需修改指针方向
插入	动态顺序表，空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁

~over~

双向链表的操作

前言