实现双链表的增删查改

简介: 实现双链表的增删查改

1.双向链表概念

双向链表是一种数据结构,它是单链表的扩展,每个节点除了有指向后继节点的指针之外,还有指向前驱节点的指针。

双向链表的节点有三个部分组成:数据域、指向前驱结点的指针和指向后继结点的指针。

双向链表的构建和单链表类似,可以从头部或尾部插入节点,也可以从头部或尾部删除节点,可以在双向链表中任意节点前或后插入节点,也可以删除任意节点。相比于单链表,双向链表的优点在于能够直接访问前驱节点,这在一些场景下非常方便,但相应地,需要额外的空间存储每个节点的前驱指针。同时,由于需要维护前驱指针,双向链表的插入和删除操作比单链表复杂一些。


2.双向链表的结构

直接看图:

d83e9d8537b2417b987a667fa2dcbb30.png

3.双向链表的增删查改

在编写插入时有一个小技巧,我们可以先让新创建的结点的指针先指向链表,然后再去修改链表的头结点和尾结点的指针,这样可以避免在插入新结点过程中造成混乱

fb908551c4a34f16ba9cefd81446c605.png

修改链表头结点和尾结点的指针指向:

8f93a1eb5686462f9052f8ceecbc4ed4.png

这样新结点就插入成功啦!

头文件:

typedef int LTDataType;
//定义双向链表节点的结构
typedef struct ListNode
{
  LTDataType data;
  struct ListNode* next;
  struct ListNode* prev;
}LTNode;
 
 
//声明双向链表中提供的方法
 
//初始化
void LTInit(LTNode** pphead);
//LTNode* LTInit();
//销毁链表
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);
 
 
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);
//删除pos节点
void LTErase(LTNode* pos);
//查找结点
LTNode* LTFind(LTNode* phead, LTDataType x);


代码实现:

初始化:

void LTInit(LTNode** pphead)
{
  LTNode* node = (LTNode*)malloc(sizeof(LTNode));
  if (node == NULL)
    exit(1);
  node->next = node;
  node->prev = node;
  *pphead = node;
}


销毁链表:

void LTDesTroy(LTNode* phead)
{
  LTNode* node = phead->next;
  while (node != phead)
  {
    LTNode* node1 = node->next;
    free(node);
    node = node1;
  }
  free(phead);
  phead = NULL;
}


打印:

void LTPrint(LTNode* phead)
{
  LTNode* node = phead->next;
  while (node!= phead)
  {
    printf("%d->", node->data);
    node = node->next;
  }
}


尾插尾删:

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
  LTNode* node = c_jian(x);
  node->prev = phead->prev;
  node->next = phead;
  phead->prev->next = node;
  phead->prev = node;
}
//尾删
void LTPopBack(LTNode* phead)
{
  LTNode* node = phead->prev;
  phead->prev->prev->next = phead;
  phead->prev = phead->prev->prev;
  free(node);
  node = NULL;
}


头插头删:

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
  LTNode* node = c_jian(x);
  node->next = phead->next;
  node->prev = phead;
  phead->next->prev = node;
  phead->next = node;
}
//头删
void LTPopFront(LTNode* phead)
{
  LTNode* node = phead->next;
  phead->next->next->prev = phead;
  phead->next = phead->next->next;
  free(node);
  node = NULL;
}


在pos位置之后插入数据:

void LTInsert(LTNode* pos, LTDataType x)
{
  
    LTNode* node = c_jian(x);
    node->next = pos->next;
    node->prev = pos;
    pos->next->prev = node;
    pos->next = node;
  
}


查找结点:

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


删除pos节点:

void LTErase(LTNode* pos)
{
  LTNode* node = pos;
  pos->next->prev = pos->prev;
  pos->prev->next = pos->next;
  free(node);
  node = NULL;
}


目录
相关文章
单链表————单链表的构建,增删查改功能的实现
单链表————单链表的构建,增删查改功能的实现
不带头非循环的单向链表的增删查改的实现(代码版)
不带头非循环的单向链表的增删查改的实现(代码版)
|
7月前
|
存储 算法 Java
【数据结构与算法】4.自主实现单链表的增删查改
【数据结构与算法】4.自主实现单链表的增删查改
|
算法 DataX
【数据结构】双向链表的增删查改(C 代码实现)
【数据结构】双向链表的增删查改(C 代码实现)
72 0
|
存储
【双链表增删查改接口的实现】
【双链表增删查改接口的实现】
52 0
带头双向循环链表增删查改实现(C语言)
带头双向循环链表增删查改实现(C语言)
双向带头循环链表(增删查改)
双向带头循环链表(增删查改)
【数据结构】带头+双向+循环链表增删查改实现
【数据结构】带头+双向+循环链表增删查改实现
|
存储 算法 Linux
双向链表增删查改详解及完整代码
双向链表增删查改详解及完整代码
76 0
双向链表增删查改详解及完整代码