【双向链表】数据结构双向链表的实现

简介: 【双向链表】数据结构双向链表的实现


1.概念以及结构

双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

2.双向链表结点结构体

双向链表每个结点除了存储数据data外,还有两个指针记录上一个结点和下一个结点的地址,分别是前驱指针prev和后继指针next,所以双向链表结点定义如下:

typedef int LTDataType;
typedef struct ListNode
{
  struct ListNode* next;
  struct ListNode* prev;
  LTDataType data;
}LTNode;

3.接口实现

我们主要进行以下操作:

//动态申请一个结点
LTNode* BuyListNode(LTDataType x);
//初始化链表
LTNode* LTInit();
//打印链表
void LTPrint(LTNode* phead);
// 双向链表尾插
void LTPushBack(LTNode* phead, LTDataType x);
// 双向链表尾删
void LTPopBack(LTNode* phead);
// 双向链表头插
void LTPushFront(LTNode* phead, LTDataType x);
// 双向链表头删
void LTPopFront(LTNode* phead);
// 双向链表查找
LTNode* LTFind(LTNode* phead, LTDataType x);
// 双向链表在pos的前面进行插入
void LTInsert(LTNode* pos, LTDataType x);
// 双向链表删除pos位置的结点
void LTErase(LTNode* pos);

3.1动态申请一个结点

LTNode* BuyListNode(LTDataType x)
{
  LTNode* node = (LTNode*)malloc(sizeof(LTNode));
  if (node == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  node->data = x;
  node->next = NULL;
  node->prev = NULL;
  return node;
}

思路:

这一步跟之前单链表的操作类似,大家可以看之前的讲解!

3.2初始化链表

LTNode* LTInit()
{
  LTNode* phead = BuyListNode(-1);
  phead->next = phead;
  phead->prev = phead;
  return phead;
}

思路:

我们进行初始化之前需要清楚我们结构的状态,我们这里写的是带头结点的双向循环链表,开始时我们先定义一个phead指针,它的next指向自己,prev也是指向自己,头结点和尾结点指向NULL空的话就不能满足我们循环的需求。

3.3打印链表

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

思路:

原理同单链表的操作基本一致!

3.4双向链表尾插

void LTPushBack(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* newnode = BuyListNode(x);
  LTNode* tail = phead->prev;
  tail->next = newnode;
  newnode->prev = tail;
  newnode->next = phead;
  phead->prev = newnode;
}

思路:

分为两种情况:

链表为空,那插入的结点既是尾结点,也是头结点;

链表不为空,将新结点和链表通过前驱指针prev和后继指针next连接起来,并将尾结点改为新插入的结点,让新节点与最后一个节点进行双层逻辑关系;

3.5 双向链表尾删

void LTPopBack(LTNode* phead)
{
  assert(phead);
  assert(phead->next != phead);  // 判空
  LTNode* tail = phead->prev;
  LTNode* tailPrev = tail->prev;//作为新的尾结点
  tailPrev->next = phead;
  phead->prev = tailPrev;
  free(tail);
}

思路:

链表为空,不操作,先断言:

链表结点大于1,保存尾结点,新尾结点等于原尾结点的上一个结点,然后释放保存的尾结点的内存;

3.6双向链表头插

void LTPushFront(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* newnode = BuyListNode(x);
  newnode->next = phead->next;
  phead->next->prev = newnode;
  phead->next = newnode;
  newnode->prev = phead;
}

思路:

跟尾插一样:

链表为空,那插入的结点既是头结点,也是尾结点;

链表不为空,将新结点和链表通过前驱指针prev和后继指针next连接起来,并将头结点改为新插入的结点,一定要注意链接顺序;

3.7双向链表头删

void LTPopFront(LTNode* phead)
{
  assert(phead);
  assert(phead->next != phead); // 判空
  LTNode* first = phead->next;
  LTNode* second = first->next;
  free(first);
  phead->next = second;
  second->prev = phead;
  
}

思路:

思路跟之前的尾删大差不差,具体对照下图,第二张图就是判断删空的情况:

3.8双向链表查找

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;
}

这跟我们单链表的情况也基本一样,大家可以对照学习!

3.9双向链表在pos的前面进行插入

void LTInsert(LTNode* pos, LTDataType x)
{
  assert(pos);
  LTNode* prev = pos->prev;
  LTNode* newnode = BuyListNode(x);
  // prev newnode pos
  prev->next = newnode;
  newnode->prev = prev;
  newnode->next = pos;
  pos->prev = newnode;

思路:

还是分为两种情况考虑:

当插入的位置为第一个位置时,这时就相当于我们的头插操作:

第二种就是正常的插入的操作,具体结合下图:

3.10双向链表删除pos位置的结点

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

思路:

这需要注意的就是删除之后的链接关系!

结合图进行理解,我相信大家都能明白。

总结:

以上就是关于带头循环双向链表的基本实现过程!大家之前学过单链表理解起来就很轻松。

相关文章
|
4天前
|
存储
数据结构链表详解(不仅顺序表可以,我链表也可以)
数据结构链表详解(不仅顺序表可以,我链表也可以)
12 0
|
5天前
|
存储
数据结构第二课 -----线性表之单向链表
数据结构第二课 -----线性表之单向链表
|
5天前
|
存储 算法 Java
数据结构与算法 数组和链表
数据结构与算法 数组和链表
12 0
|
5天前
|
存储 Java
深入浅出数据结构之链表
深入浅出数据结构之链表
|
5天前
|
C++
数据结构(双链表
数据结构(双链表
11 1
|
5天前
|
存储 缓存
[数据结构]~双向+循环链表从(0~1)
[数据结构]~双向+循环链表从(0~1)
|
5天前
|
存储
数据结构第三课 -----线性表之双向链表
数据结构第三课 -----线性表之双向链表
|
5天前
|
存储 Java
数据结构奇妙旅程之顺序表和链表
数据结构奇妙旅程之顺序表和链表
|
5天前
|
存储 C语言
数据结构基础:双链表结构、实现
数据结构基础:双链表结构、实现
|
5天前
|
存储
数据结构基础:一篇文章教你单链表(头插,尾插,查找,头删等的解析和代码)
数据结构基础:一篇文章教你单链表(头插,尾插,查找,头删等的解析和代码)