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

数据第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 遍历链表中的所有元素。

推荐阅读

client
使用多进程实现TCP服务端的优势和注意事项

本文介绍了为什么要使用多进程处理TCP服务端，多进程的好处包括可靠性高和处理大量数据时速度快。然而，多进程不能共享进程空间，因此有一些变量不能共享。文章还提供了使用多进程实现TCP服务端的代码，并对代码进行了详细注释。 ... [详细]

蜡笔小新 2023-12-13 18:25:30
char
eclipse学习（第三章：ssh中的Hibernate）——11.Hibernate的缓存（2级缓存，get和load）

本文介绍了eclipse学习中的第三章内容，主要讲解了ssh中的Hibernate的缓存，包括2级缓存和get方法、load方法的区别。文章还涉及了项目实践和相关知识点的讲解。 ... [详细]

蜡笔小新 2023-12-14 00:31:35
char
c语言\n不换行,c语言printf不换行

$c语言\n不换行,c语言printf不换行$

本文目录一览：1、C语言不换行输入2、c语言的 ... [详细]

蜡笔小新 2023-12-14 11:05:35
char
二叉树层序创建问题的解决方法

本文介绍了解决二叉树层序创建问题的方法。通过使用队列结构体和二叉树结构体，实现了入队和出队操作，并提供了判断队列是否为空的函数。详细介绍了解决该问题的步骤和流程。 ... [详细]

蜡笔小新 2023-12-13 18:20:50
char
PE总结9PE文件结构之解析导出表

本文介绍了PE文件结构中的导出表的解析方法，包括获取区段头表、遍历查找所在的区段等步骤。通过该方法可以准确地解析PE文件中的导出表信息。 ... [详细]

蜡笔小新 2023-12-13 11:47:24
char
李逍遥寻找仙药的迷阵之旅

本文讲述了少年李逍遥为了救治婶婶的病情，前往仙灵岛寻找仙药的故事。他需要穿越一个由M×N个方格组成的迷阵，有些方格内有怪物，有些方格是安全的。李逍遥需要避开有怪物的方格，并经过最少的方格，找到仙药。在寻找的过程中，他还会遇到神秘人物。本文提供了一个迷阵样例及李逍遥找到仙药的路线。 ... [详细]

蜡笔小新 2023-12-12 13:59:33
string
如何自行分析定位SAP BSP错误

The“BSPtag”Imentionedintheblogtitlemeansforexamplethetagchtmlb:configCelleratorbelowwhichi ... [详细]

蜡笔小新 2023-12-14 19:58:05
format
VScode格式化文档换行或不换行的设置方法

本文介绍了在VScode中设置格式化文档换行或不换行的方法，包括使用插件和修改settings.json文件的内容。详细步骤为：找到settings.json文件，将其中的代码替换为指定的代码。 ... [详细]

蜡笔小新 2023-12-14 17:15:38
char
Nginx使用（server参数配置）

本文介绍了Nginx的使用，重点讲解了server参数配置，包括端口号、主机名、根目录等内容。同时，还介绍了Nginx的反向代理功能。 ... [详细]

蜡笔小新 2023-12-14 17:08:34
sum
C++省略号类型和参数个数不确定函数参数范例

本文介绍了C++中省略号类型和参数个数不确定函数参数的使用方法，并提供了一个范例。通过宏定义的方式，可以方便地处理不定参数的情况。文章中给出了具体的代码实现，并对代码进行了解释和说明。这对于需要处理不定参数的情况的程序员来说，是一个很有用的参考资料。 ... [详细]

蜡笔小新 2023-12-14 12:36:28
string
差分约束系统求解House Man跳跃问题的思路与方法

本文讨论了使用差分约束系统求解House Man跳跃问题的思路与方法。给定一组不同高度，要求从最低点跳跃到最高点，每次跳跃的距离不超过D，并且不能改变给定的顺序。通过建立差分约束系统，将问题转化为图的建立和查询距离的问题。文章详细介绍了建立约束条件的方法，并使用SPFA算法判环并输出结果。同时还讨论了建边方向和跳跃顺序的关系。 ... [详细]

蜡笔小新 2023-12-14 11:49:51
char
C函数ispunct()的用法及示例代码

本文介绍了C函数ispunct()的用法及示例代码。ispunct()函数用于检查传递的字符是否是标点符号，如果是标点符号则返回非零值，否则返回零。示例代码演示了如何使用ispunct()函数来判断字符是否为标点符号。 ... [详细]

蜡笔小新 2023-12-13 18:13:34
char
Linux环境变量函数getenv、putenv、setenv和unsetenv详解

本文详细解释了Linux中的环境变量函数getenv、putenv、setenv和unsetenv的用法和功能。通过使用这些函数，可以获取、设置和删除环境变量的值。同时给出了相应的函数原型、参数说明和返回值。通过示例代码演示了如何使用getenv函数获取环境变量的值，并打印出来。 ... [详细]

蜡笔小新 2023-12-13 12:01:03
char
clone的fork与pthread_create创建线程有何不同

本文讨论了clone的fork与pthread_create创建线程的不同之处。进程是一个指令执行流及其执行环境，其执行环境是一个系统资源的集合。在调用系统调用fork创建一个进程时，子进程只是完全复制父进程的资源，这样得到的子进程独立于父进程，具有良好的并发性。但是二者之间的通讯需要通过专门的通讯机制，另外通过fork创建子进程系统开销很大。因此，在某些情况下，使用clone或pthread_create创建线程可能更加高效。 ... [详细]

蜡笔小新 2023-12-12 20:00:06
char
欢乐的票圈重构之旅——RecyclerView的头尾布局增加

项目重构的Git地址：https:github.comrazerdpFriendCircletreemain-dev项目同步更新的文集：http:www.jianshu.comno ... [详细]

蜡笔小新 2023-12-11 19:09:56

田文萍

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

Tags | 热门标签

RankList | 热门文章