数据结构3——双向链表-阿里云开发者社区

数据结构3——双向链表

2024-10-10 112

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 数据结构3——双向链表

在上篇文章数据结构2——单链表中，我们了解了什么是链表，以及单链表的实现，接着上篇文章，本篇文章介绍一下比单链表更常用的链表——双向循环链表。

1.双向链表的实现

1.1节点

单链表的节点存的有数据域和一个指向下一个节点后继指针，因此单链表只能单向遍历。

要想实现双向遍历，就需要在节点里增加一个指向前一个节点的前驱指针。

typedef int DLTDataType;
typedef struct DListNode
{
  DLTDataType data;
  struct DListNode* prev;//前继指针
  struct DListNode* next;//后继指针
}DLTNode;

1.2 初始化节点

//初始化节点函数实现
DLTNode* DLTInit()
{
  DLTNode* phead = BuyDLTNode(-1);
  phead->next = phead;
  phead->prev = phead;
 
  return phead;
}

1.3 动态开辟新节点

//开辟新节点函数实现
DLTNode* BuyDLTNode(DLTDataType x)
{
  DLTNode* node = (DLTNode*)malloc(sizeof(DLTNode));
  if (node == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
 
  node->data = x;
  node->next = NULL;
  node->prev = NULL;
 
  return node;
}

1.4 遍历链表

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

1.5 查找

//查找
DLTNode* DLTFind(DLTNode* phead, DLTDataType x)
{
  assert(phead);
 
  DLTNode* cur = phead->next;
  while (cur != phead)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
 
  return NULL;
}

1.6 插入

1.尾插

//尾插函数实现
void DLTPushBack(DLTNode* phead, DLTDataType x)
{
  assert(phead);
  //①常规写法
  DLTNode* tail = phead->prev;
  DLTNode* newnode = BuyDLTNode(x);
 
  newnode->prev = tail;
  tail->next = newnode;
 
  newnode->next = phead;
  phead->prev = newnode;
  //②复用 DLTInsert
  //DLTInsert(phead, x);
}

2. 头插

//头插函数实现
void DLTPushFront(DLTNode* phead, DLTDataType x)
{
  assert(phead);
  //①常规写法
  DLTNode* newnode = BuyDLTNode(x);
 
  newnode->next = phead->next;
  phead->next->prev = newnode;
 
  phead->next = newnode;
  newnode->prev = phead;
  //②复用DLTInsert
  //DLTInsert(phead->next, x);
}

3.在pos之前插入

//在pos之前插入
void DLTInsert(DLTNode* pos, DLTDataType x)
{
  assert(pos);
 
  DLTNode* posPrev = pos->prev;
  DLTNode* newnode = BuyDLTNode(x);
 
  posPrev->next = newnode;
  newnode->prev = posPrev;
  newnode->next = pos;
  pos->prev = newnode; 
}

1.7 删除

1. 尾删

//尾删函数实现
void DLTPopBack(DLTNode* phead)
{
  assert(phead);
  assert(phead->next != phead);//检查链表是否为空
 
  //①常规写法
  DLTNode* tail = phead->prev;
  DLTNode* tailPrev = tail->prev;
  free(tail);
 
  tailPrev->next = phead;
  phead->prev = tailPrev;
  //②复用DLTErase
  //DLTErase(phead->prev);
}

2. 头删

//头删函数实现
void DLTPopFront(DLTNode* phead)
{
  assert(phead);
  assert(phead->next != phead);
 
  //①常规写法
  DLTNode* first = phead->next;
  DLTNode* second = first->next;
 
  free(first);
 
  phead->next = second;
  second->prev = phead;
  //②复用DLTErase
  //DLTErase(phead->next);
}

3.删除pos位置

//删除pos位置
void DLTErase(DLTNode* pos)
{
  assert(pos);
  DLTNode* posPrev = pos->prev;
  DLTNode* posNext = pos->next;
 
  free(pos);
 
  posPrev->next = posNext;
  posNext->prev = posPrev;
}

1.8 其他函数

1. 链表长度

//链表长度
int DLTSize(DLTNode* phead)
{
  assert(phead);
 
  int size = 0;
  DLTNode* cur = phead->next;
  while (cur != phead)
  {
    ++size;
    cur = cur->next;
  }
 
  return size;
}

2. 销毁链表

//销毁函数
void DLTDestory(DLTNode* phead)
{
  assert(phead);
 
  DLTNode* cur = phead->next;
  while (cur != phead)
  {
    DLTNode* next = cur->next;
    free(cur);
 
    cur = next;
  }
 
  free(phead);
 
}

1.9 测试

int main()
{
  DLTNode* plist = DLTInit();
  DLTPushBack(plist, 1);
  DLTPushBack(plist, 2);
  DLTPushBack(plist, 3);
  DLTPushBack(plist, 4);
  DLTPushBack(plist, 5);
  DLTPrint(plist);
  DLTPushFront(plist, 10);
  DLTPushFront(plist, 11);
  DLTPushFront(plist, 12);
  DLTPrint(plist);
  DLTDestory(plist);
  plist = NULL;
  return 0;
}

2.顺序表和链表的比较

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

*源代码

DLish.h

#pragma once
 
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
 
typedef int DLTDataType;
typedef struct DListNode
{
  DLTDataType data;
  struct DListNode* prev;//前继指针
  struct DListNode* next;//后继指针
}DLTNode;
 
//开辟新节点函数声明
DLTNode* BuyDLTNode(DLTDataType x);
 
//初始化节点函数声明
DLTNode* DLTInit();
 
//遍历函数声明
void DLTPrint(DLTNode* phead);
 
//尾插函数声明
void DLTPushBack(DLTNode* phead, DLTDataType x);
//头插函数声明
void DLTPushFront(DLTNode* phead, DLTDataType x);
 
//尾删函数声明
void DLTPopBack(DLTNode* phead);
//头删函数声明
void DLTPopFront(DLTNode* phead);
 
//链表长度
int DLTSize(DLTNode* phead);
 
//查找
DLTNode* DLTFind(DLTNode* phead, DLTDataType x);
 
//在pos之前插入 
void DLTInsert(DLTNode* pos, DLTDataType x);
//删除pos位置
void DLTErase(DLTNode* pos);
 
//销毁函数
void DLTDestory(DLTNode* phead);

DLish.c

#define _CRT_SECURE_NO_WARNINGS 1
 
#include "DList.h"
 
//开辟新节点函数实现
DLTNode* BuyDLTNode(DLTDataType x)
{
  DLTNode* node = (DLTNode*)malloc(sizeof(DLTNode));
  if (node == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
 
  node->data = x;
  node->next = NULL;
  node->prev = NULL;
 
  return node;
}
 
//初始化节点函数实现
DLTNode* DLTInit()
{
  DLTNode* phead = BuyDLTNode(-1);
  phead->next = phead;
  phead->prev = phead;
 
  return phead;
}
 
//遍历函数实现
void DLTPrint(DLTNode* phead)
{
  assert(phead);
 
  printf("phead <-> ");
  DLTNode* cur = phead->next;
  while (cur != phead)
  {
    printf("%d <-> ", cur->data);
    cur = cur->next;
  }
  printf("\n");
}
 
 
//尾插函数实现
void DLTPushBack(DLTNode* phead, DLTDataType x)
{
  assert(phead);
  //①常规写法
  DLTNode* tail = phead->prev;
  DLTNode* newnode = BuyDLTNode(x);
 
  newnode->prev = tail;
  tail->next = newnode;
 
  newnode->next = phead;
  phead->prev = newnode;
  //②复用 DLTInsert
  //DLTInsert(phead, x);
}
//头插函数实现
void DLTPushFront(DLTNode* phead, DLTDataType x)
{
  assert(phead);
  //①常规写法
  DLTNode* newnode = BuyDLTNode(x);
 
  newnode->next = phead->next;
  phead->next->prev = newnode;
 
  phead->next = newnode;
  newnode->prev = phead;
  //②复用DLTInsert
  //DLTInsert(phead->next, x);
}
 
 
 
//尾删函数实现
void DLTPopBack(DLTNode* phead)
{
  assert(phead);
  assert(phead->next != phead);//检查链表是否为空
 
  //①常规写法
  DLTNode* tail = phead->prev;
  DLTNode* tailPrev = tail->prev;
  free(tail);
 
  tailPrev->next = phead;
  phead->prev = tailPrev;
  //②复用DLTErase
  //DLTErase(phead->prev);
}
//头删函数实现
void DLTPopFront(DLTNode* phead)
{
  assert(phead);
  assert(phead->next != phead);
 
  //①常规写法
  DLTNode* first = phead->next;
  DLTNode* second = first->next;
 
  free(first);
 
  phead->next = second;
  second->prev = phead;
  //②复用DLTErase
  //DLTErase(phead->next);
}
 
//链表长度
int DLTSize(DLTNode* phead)
{
  assert(phead);
 
  int size = 0;
  DLTNode* cur = phead->next;
  while (cur != phead)
  {
    ++size;
    cur = cur->next;
  }
 
  return size;
}
 
//查找
DLTNode* DLTFind(DLTNode* phead, DLTDataType x)
{
  assert(phead);
 
  DLTNode* cur = phead->next;
  while (cur != phead)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
 
  return NULL;
}
 
//在pos之前插入
void DLTInsert(DLTNode* pos, DLTDataType x)
{
  assert(pos);
 
  DLTNode* posPrev = pos->prev;
  DLTNode* newnode = BuyDLTNode(x);
 
  posPrev->next = newnode;
  newnode->prev = posPrev;
  newnode->next = pos;
  pos->prev = newnode; 
}
//删除pos位置
void DLTErase(DLTNode* pos)
{
  assert(pos);
  DLTNode* posPrev = pos->prev;
  DLTNode* posNext = pos->next;
 
  free(pos);
 
  posPrev->next = posNext;
  posNext->prev = posPrev;
}
 
//销毁函数
void DLTDestory(DLTNode* phead)
{
  assert(phead);
 
  DLTNode* cur = phead->next;
  while (cur != phead)
  {
    DLTNode* next = cur->next;
    free(cur);
 
    cur = next;
  }
 
  free(phead);
 
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
 
#include "DList.h"
 
int main()
{
  DLTNode* plist = DLTInit();
  DLTPushBack(plist, 1);
  DLTPushBack(plist, 2);
  DLTPushBack(plist, 3);
  DLTPushBack(plist, 4);
  DLTPushBack(plist, 5);
  DLTPrint(plist);
  DLTPushFront(plist, 10);
  DLTPushFront(plist, 11);
  DLTPushFront(plist, 12);
  DLTPrint(plist);
  DLTDestory(plist);
  plist = NULL;
  DLTPrint(plist);
  return 0;
}

数据结构3——双向链表

1.双向链表的实现

1.1节点

1.2 初始化节点

1.3 动态开辟新节点

1.4 遍历链表

1.5 查找

1.6 插入

1.尾插

2. 头插

3.在pos之前插入

1.7 删除

1. 尾删

2. 头删

3.删除pos位置

1.8 其他函数

1. 链表长度

2. 销毁链表

1.9 测试

2.顺序表和链表的比较

*源代码

DLish.h

DLish.c

test.c

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

数据结构3——双向链表

1.双向链表的实现

1.1节点

1.2 初始化节点

1.3 动态开辟新节点

1.4 遍历链表

1.5 查找

1.6 插入

1.尾插

2. 头插

3.在pos之前插入

1.7 删除

1. 尾删

2. 头删

3.删除pos位置

1.8 其他函数

1. 链表长度

2. 销毁链表

1.9 测试

2.顺序表和链表的比较

*源代码

DLish.h

DLish.c

test.c

热门文章

最新文章

相关课程

相关电子书