当前位置: 开发笔记 > 编程语言 > 正文

数据第11课双向链表

作者：田文萍 | 来源：互联网 | 2023-10-10 13:33

第11课-双向链表 1.单链表的局限(1) 单链表的结点都只有一个指向下一个结点的指针。(2) 单链表的数据元素无法直接访问其前驱元素。l 逆序访问单链表中的元素是

第11课-双向链表

1. 单链表的局限

(1) 单链表的结点都只有一个指向下一个结点的指针。

(2) 单链表的数据元素无法直接访问其前驱元素。

l 逆序访问单链表中的元素是极其耗时的操作！

len = LinkList_Length(list);

for(i=len-1; len>=0; i--)

{

LinkListNode* p = LinkList_Get(list,i);

//访问数据元素p中的元素

}

2. 双向链表的定义

在单链表的结点中增加一个指向其前驱的pre指针。

3. 双向链表拥有单链表的所有操作

(1) 创建链表。

(2) 销毁链表。

(3) 获取链表长度。

(4) 清空链表。

(5) 获取第pos个元素操作。

(6) 插入元素到位置pos。

(7) 删除位置p。

4. 双向链表的插入操作

current->next = node;

node->next =next;

next->pre = node;

node->pre = current;

5. 双向链表的删除操作

current->next = next;

next-> = current;

6. 双向链表的新操作

(1) 获取当前游标指向的数据元素。

(2) 将游标重置指向链表中的第一个数据元素。

(3) 将游标移动指向到链表中的下一个数据元素。

(4) 将游标移动指向到链表中的上一个数据元素。

(5) 直接指定删除链表中的某个数据元素。

DLinkListNode* DLinkList_DeleteNode(DLinkList* list, DLinkListNode* node);

DLinkListNode* DLinkList_Reset(DLinkList* list);

DLinkListNode* DLinkList_Current(DLinkList* list);

DLinkListNode* DLinkList_Next(DLinkList* list);

DLinkListNode* DLinkList_Pre(DLinkList* list);

DLinkList.h

#ifndef _DLINKLIST_H_

#define _DLINKLIST_H_

typedef void DLinkList;

typedef struct _tag_DLinkListNode DLinkListNode;

struct _tag_DLinkListNode

{

DLinkListNode* next;

DLinkListNode* pre;

};

DLinkList* DLinkList_Create();

void DLinkList_Destroy(DLinkList* list);

void DLinkList_Clear(DLinkList* list);

int DLinkList_Length(DLinkList* list);

int DLinkList_Insert(DLinkList* list, DLinkListNode* node, int pos);

DLinkListNode* DLinkList_Get(DLinkList* list, int pos);

DLinkListNode* DLinkList_Delete(DLinkList* list, int pos);

DLinkListNode* DLinkList_DeleteNode(DLinkList* list, DLinkListNode* node);

DLinkListNode* DLinkList_Reset(DLinkList* list);

DLinkListNode* DLinkList_Current(DLinkList* list);

DLinkListNode* DLinkList_Next(DLinkList* list);

DLinkListNode* DLinkList_Pre(DLinkList* list);

#endif

DLinkList.c

#include

#include "DLinkList.h"

typedef struct _tag_DLinkList

{

DLinkListNode header;

DLinkListNode* slider;

int length;

} TDLinkList;

DLinkList* DLinkList_Create() // O(1)

{

TDLinkList* ret = (TDLinkList*)malloc(sizeof(TDLinkList));

if( ret != NULL )

{

ret->length = 0;

ret->header.next = NULL;

ret->header.pre = NULL;

ret->slider = NULL;

}

return ret;

}

void DLinkList_Destroy(DLinkList* list) // O(1)

{

free(list);

}

void DLinkList_Clear(DLinkList* list) // O(1)

{

TDLinkList* sList = (TDLinkList*)list;

if( sList != NULL )

{

sList->length = 0;

sList->header.next = NULL;

sList->header.pre = NULL;

sList->slider = NULL;

}

int DLinkList_Length(DLinkList* list) // O(1)

{

TDLinkList* sList = (TDLinkList*)list;

int ret = -1;

if( sList != NULL )

{

ret = sList->length;

}

return ret;

}

int DLinkList_Insert(DLinkList* list, DLinkListNode* node, int pos) // O(n)

{

TDLinkList* sList = (TDLinkList*)list;

int ret = (sList != NULL) && (pos >= 0) && (node != NULL);

int i = 0;

if( ret )

{

DLinkListNode* current = (DLinkListNode*)sList;

DLinkListNode* next = NULL;

for(i=0; (i

next != NULL); i++)

{

current = current->next;

}

next = current->next;

current->next = node;

node->next = next;

if( next != NULL )

{

next->pre = node;

}

node->pre = current;

if( sList->length == 0 )

{

node->pre = NULL;

sList->slider = node;

}

sList->length++;

}

return ret;

}

DLinkListNode* DLinkList_Get(DLinkList* list, int pos) // O(n)

{

TDLinkList* sList = (TDLinkList*)list;

DLinkListNode* ret = NULL;

int i = 0;

if( (sList != NULL) && (0 <= pos) && (pos length) )

{

DLinkListNode* current = (DLinkListNode*)sList;

for(i=0; i

{

current = current->next;

}

ret = current->next;

}

return ret;

}

DLinkListNode* DLinkList_Delete(DLinkList* list, int pos) // O(n)

{

TDLinkList* sList = (TDLinkList*)list;

DLinkListNode* ret = NULL;

int i = 0;

if( (sList != NULL) && (0 <= pos) && (pos length) )

{

DLinkListNode* current = (DLinkListNode*)sList;

DLinkListNode* next = NULL;

for(i=0; i

{

current = current->next;

}

ret = current->next;

next = ret->next;

current->next = next;

if( next != NULL )

{

next->pre = current;

if( current == (DLinkListNode*)sList )

{

next->pre = NULL;

}

if( sList->slider == ret )

{

sList->slider = next;

}

sList->length--;

}

return ret;

}

DLinkListNode* DLinkList_DeleteNode(DLinkList* list, DLinkListNode* node)

{

TDLinkList* sList = (TDLinkList*)list;

DLinkListNode* ret = NULL;

int i = 0;

if( sList != NULL )

{

DLinkListNode* current = (DLinkListNode*)sList;

for(i=0; ilength; i++)

{

if( current->next == node )

{

ret = current->next;

break;

}

current = current->next;

}

if( ret != NULL )

{

DLinkList_Delete(sList, i);

}

return ret;

}

DLinkListNode* DLinkList_Reset(DLinkList* list)

{

TDLinkList* sList = (TDLinkList*)list;

DLinkListNode* ret = NULL;

if( sList != NULL )

{

sList->slider = sList->header.next;

ret = sList->slider;

}

return ret;

}

DLinkListNode* DLinkList_Current(DLinkList* list)

{

TDLinkList* sList = (TDLinkList*)list;

DLinkListNode* ret = NULL;

if( sList != NULL )

{

ret = sList->slider;

}

return ret;

}

DLinkListNode* DLinkList_Next(DLinkList* list)

{

TDLinkList* sList = (TDLinkList*)list;

DLinkListNode* ret = NULL;

if( (sList != NULL) && (sList->slider != NULL) )

{

ret = sList->slider;

sList->slider = ret->next;

}

return ret;

}

DLinkListNode* DLinkList_Pre(DLinkList* list)

{

TDLinkList* sList = (TDLinkList*)list;

DLinkListNode* ret = NULL;

if( (sList != NULL) && (sList->slider != NULL) )

{

ret = sList->slider;

sList->slider = ret->pre;

}

return ret;

}

main.c

#include

#include "DLinkList.h"

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

struct Value

{

DLinkListNode header;

int v;

};

int main(int argc, char *argv[])

{

int i = 0;

DLinkList* list = DLinkList_Create();

struct Value* pv = NULL;

struct Value v1;

struct Value v2;

struct Value v3;

struct Value v4;

struct Value v5;

v1.v = 1;

v2.v = 2;

v3.v = 3;

v4.v = 4;

v5.v = 5;

DLinkList_Insert(list, (DLinkListNode*)&v1, DLinkList_Length(list));

DLinkList_Insert(list, (DLinkListNode*)&v2, DLinkList_Length(list));

DLinkList_Insert(list, (DLinkListNode*)&v3, DLinkList_Length(list));

DLinkList_Insert(list, (DLinkListNode*)&v4, DLinkList_Length(list));

DLinkList_Insert(list, (DLinkListNode*)&v5, DLinkList_Length(list));

for(i=0; i

{

pv = (struct Value*)DLinkList_Get(list, i);

printf("%d\n", pv->v);

}

printf("\n");

DLinkList_Delete(list, DLinkList_Length(list)-1);

DLinkList_Delete(list, 0);

for(i=0; i

{

pv = (struct Value*)DLinkList_Next(list);

printf("%d\n", pv->v);

}

printf("\n");

DLinkList_Reset(list);

DLinkList_Next(list);

pv = (struct Value*)DLinkList_Current(list);

printf("%d\n", pv->v);

DLinkList_DeleteNode(list, (DLinkListNode*)pv);

pv = (struct Value*)DLinkList_Current(list);

printf("%d\n", pv->v);

DLinkList_Pre(list);

pv = (struct Value*)DLinkList_Current(list);

printf("%d\n", pv->v);

printf("Length: %d\n", DLinkList_Length(list));

DLinkList_Destroy(list);

return 0;

}

小结

l 双向链表在单链表的基础上增加了指向前驱的指针。

l 功能上双向链表可以完全取代单链表的使用。

l 循环链表的Next，Pre和Current操作可以高效的。

l 遍历链表中的所有元素。

推荐阅读

copy
CentOS 7 中配置开机自动挂载 NFS 的解决方案

本文详细介绍了在 CentOS 7 系统中配置 fstab 文件以实现开机自动挂载 NFS 共享目录的方法，并解决了常见的配置失败问题。 ... [详细]

蜡笔小新 2024-11-13 12:05:24
tree
com.sun.javadoc.PackageDoc.exceptions()方法的使用及代码示例

com.sun.javadoc.PackageDoc.exceptions()方法的使用及代码示例 ... [详细]

蜡笔小新 2024-11-13 10:47:33
scala
如何在Java中使用DButils类

这期内容当中小编将会给大家带来有关如何在Java中使用DButils类，文章内容丰富且以专业的角度为大家分析和叙述，阅读完这篇文章希望大家可以有所收获。D ... [详细]

蜡笔小新 2024-11-12 13:46:11
replace
检查在所有可能的“？”替换中，给定的二进制字符串中是否出现子字符串“10”带 1 或 0

检查在所有可能的“？”替换中，给定的二进制字符串中是否出现子字符串“10”带 1 或 0 ... [详细]

蜡笔小新 2024-11-12 11:35:01
search
Python基础：使用NLTK和Python构建机器学习应用

本文节选自《NLTK基础教程——用NLTK和Python库构建机器学习应用》一书的第1章第1.2节，作者Nitin Hardeniya。本文将带领读者快速了解Python的基础知识，为后续的机器学习应用打下坚实的基础。 ... [详细]

蜡笔小新 2024-11-13 21:23:34
const
2017.11.26【清华集训2017】模拟

T15483.【清华集训2017模拟11.26】简单路径T25484.【清华集训2017模拟11.26】快乐树T35485.【清华集训2017模拟11.26】字符串T1结论题，结论很 ... [详细]

蜡笔小新 2024-11-13 20:25:28
const
数据结构第三章，栈、队列、数组，期末不挂科指南，第3篇

数据结构第三章，栈、队列、数组，期末不挂科指南，第3篇,Go语言社区,Golang程序员人脉社 ... [详细]

蜡笔小新 2024-11-13 18:49:58
const
Android 自定义 RecycleView 左滑上下分层示例代码

为了满足项目需求，需要在多个场景中实现左滑删除功能，并且后续可能在列表项中增加其他功能。虽然网络上有很多左滑删除的示例，但大多数封装不够完善。因此，我们尝试自己封装一个更加灵活和通用的解决方案。 ... [详细]

蜡笔小新 2024-11-13 17:43:59
数组
【妙】bug称它为数组越界的妙用

1、聊一聊首先跟大家推荐一首非常温柔的歌曲，跑步的常听。本文主要把自己对C语言中柔性数组、零数组等等的理解分享给大家，并聊聊如何构建一种统一化的学习思想 ... [详细]

蜡笔小新 2024-11-13 17:42:24
hook
Spring – Bean Life Cycle

Spring – Bean Life Cycle ... [详细]

蜡笔小新 2024-11-13 13:24:40
const
洛谷 P1531 我讨厌它 —— 线段树实现

本文介绍如何使用线段树解决洛谷 P1531 我讨厌它问题，重点在于单点更新和区间查询最大值。 ... [详细]

蜡笔小新 2024-11-12 21:27:38
const
单片微机原理P3：80C51外部拓展系统

　　外部拓展其实是个相对来说很好玩的章节，可以真正开始用单片机写程序了，比较重要的是外部存储器拓展，81C55拓展，矩阵键盘，动态显示，DAC和ADC。0.IO接口电路概念与存 ... [详细]

蜡笔小新 2024-11-12 19:51:29
php
c/c++常用代码doc,ppt,xls文件格式转PDF格式[转]

[转]doc,ppt,xls文件格式转PDF格式http:blog.csdn.netlee353086articledetails7920355确实好用。需要注意的是#import ... [详细]

蜡笔小新 2024-11-12 16:19:40
replace
javascript分页类支持页码格式

前端时间因为项目需要，要对一个产品下所有的附属图片进行分页显示，没考虑ajax一张张请求，所以干脆一次性全部把图片out，然 ... [详细]

蜡笔小新 2024-11-12 14:58:57
copy
PHP 对象生命周期与内存管理

本文详细介绍了 PHP 中对象的生命周期、内存管理和魔术方法的使用，包括对象的自动销毁、析构函数的作用以及各种魔术方法的具体应用场景。 ... [详细]

蜡笔小新 2024-11-12 13:35:26

田文萍

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章