初阶数据结构 带头双链表

简介: 初阶数据结构 带头双链表

. 结构图和哨兵

我们先来看它的结构图

这里的结构大体如上

我们可以发现的是 这里其实是有一个哨兵位

那么什么是哨兵位呢?

之前的一期我们讲过,可以看我的往期文章



二. 代码实现

我们还是跟以前一样 先创建三个工程文件

创建一个节点所需要的指针和值

typedef int LTDateType;
 
typedef struct ListNode
{
  struct ListNode* next;
  struct ListNode* prev;
  LTDateType date;
}LTNode;

这样子如果我们想要改变双链表存储的值的话只需要改变typedef的类型就可以了


三. 初始化双链表

这里很简单 我们只需要创建一个哨兵位就可以

这个哨兵位的头尾指针都要指向自身

代码表示如下

LTNode* BuyListNode(LTDateType x)
{
  LTNode* node = (LTNode*)malloc(sizeof(LTNode));
  if (node == NULL)
  {
    perror("malloc fail");
    //return NULL;
    exit(-1);
  }
  node->next = NULL;
  node->prev = NULL;
  node->date = x;
  return node;
}
LTNode* LTInit()
{
  LTNode* phead = BuyListNode(-1);
  phead->next = phead;
  phead->prev = phead;
 
  return phead;
}


四. 尾插数据

我们来看图

首先我们需要通过tail找到一个尾

之后通过这个尾来向后插入一个新的数据

一共有四个箭头需要链接(尾2 新节点2)

之后我们开始找尾 插入数据

代码表示如下

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


五. 打印数据

没有什么难度

代码表示如下

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

接下来我们试试看打印尾插的数据

我们发现没有问题


六. 尾删数据

首先我们需要找到tail之前的一个数据 我们将这个数据称之为prev

然后按照上图链接就可以

但是又一种特殊情况 如果说 head 既是头又是尾 我们这里就需要报错

因为哨兵位不可以删除

代码表示如下

void LTPopBack(LTNode* phead)
{
  assert(phead);
  assert(!LTEmpty(phead));
  LTNode* tail = phead->prev;
  LTNode* tailPrev = tail->prev;
  tailPrev->next = phead;
  phead->prev = tailPrev;
  free(tail);
  tail = NULL;
}

然后效果表示如下


七. 头插数据

还是一样 我们先看图

代码表示如下

void LTPustFront(LTNode* phead, LTDateType x)
{
  assert(phead);
  LTNode* newnode = BuyListNode(x);
  LTNode* first = phead->next;
  phead->next = newnode;
  newnode->prev = phead;
 
  newnode->next = first;
  first->prev = newnode;
  //不能随便换顺序
  //newnode->next = phead->next;
  //phead->next->prev = newnode;
  // 
  //phead->next = newnode;
  //newnode->prev = phead;
  /*LTInsert(phead->next, x);*/
}

显示效果如下



八. 头删数据

我们发现要头删除数据的话要使用三个指针

哨兵位指针

头指针

头指针的下一位

开始写代码

void LTPopFront(LTNode* phead)
{
  assert(phead);
  assert(!LTEmpty(phead));
  LTNode* first = phead->next;
  phead->next = first->next;
  first->next->prev = phead;
  free(first);
  first = NULL;
}

显示效果如下


九. 查找指定位置

这个实现起来也很简单 跟打印的思路差不多

LTFind(LTNode* phead, LTDateType x)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur!=phead)
  {
    if (cur->date == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}

如果找到return pos的位置

如果找不到我们就返回一个空指针


十. 指定位置前插入数

如图

看图敲代码

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

我们来看看效果



十一. 删除指定位置的数

还是一样 先看图

这里我们需要三个指针 一个前面的一个后面的

但是这里我们需要注意

Pos指针不能为空

并且Pos指针不能指向头节点

我们来看看代码

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

我们再看看效果图怎么样


以上便是本文所有内容了,如有错误请各位大佬不吝赐教,感谢留言

目录
相关文章
|
19天前
|
存储 缓存 前端开发
【数据结构/C语言】深入理解 双向链表
【数据结构/C语言】深入理解 双向链表
|
19天前
|
存储 算法 C语言
【数据结构与算法 刷题系列】合并两个有序链表
【数据结构与算法 刷题系列】合并两个有序链表
|
4天前
【数据结构OJ题】合并两个有序链表
力扣题目——合并两个有序链表
24 8
【数据结构OJ题】合并两个有序链表
|
6天前
【数据结构OJ题】移除链表元素
力扣题目——移除链表元素
10 2
【数据结构OJ题】移除链表元素
|
6天前
【数据结构OJ题】链表中倒数第k个结点
牛客题目——链表中倒数第k个结点
9 1
【数据结构OJ题】链表中倒数第k个结点
|
6天前
|
存储 DataX C语言
【数据结构】双链表
数据结构中的双链表
14 1
【数据结构】双链表
|
3天前
【数据结构OJ题】链表分割
牛客题目——链表分割
3 0
【数据结构OJ题】链表分割
|
4天前
【数据结构OJ题】链表的回文结构
牛客题目——链表的回文结构
6 0
【数据结构OJ题】链表的回文结构
|
6天前
【数据结构OJ题】链表的中间结点
力扣题目——链表的中间结点
9 0
【数据结构OJ题】链表的中间结点
|
6天前
【数据结构OJ题】反转链表
力扣题目——反转链表
10 0
【数据结构OJ题】反转链表