双向链表的实现与操作(C语言实现)

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› C++›C++教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

双向链表也叫双链表，是链表的一种，它的每一个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的随意一个结点開始，都能够非常方便地訪问它的前驱结点和后继结点。

单链表的局限

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

2，单链表的数据元素无法直接訪问其前驱元素

3。逆序訪问单链表中的元素是极其耗时的操作

双向链表的操作

双向链表的新操作

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

头文件：

#ifndef _DDLinkList_H_
#define _DDLinkList_H_
typedef void DLinkList;
typedef struct DLinkListNode   //声明指针域
{
	DLinkListNode * pre;
	DLinkListNode * next;
}DLinkListNode;

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

源文件：

// 双向链表.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include "DLinkList.h"
#include <stdlib.h>
#include <malloc.h>

typedef struct 
{
	DLinkListNode header;
	DLinkListNode * slider; //游标
	int len;
}TDLinkList;


struct Value
{
    DLinkListNode header; //指针域
    int v; //数据域
};

int _tmain(int argc, _TCHAR* 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;
    //插入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<DLinkList_Length(list); 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);
    printf("删除头尾结点后：\n");
    for(i=0; i<DLinkList_Length(list); i++)
    {
		pv = (struct Value*)DLinkList_Next(list);
        
        printf("%d\n", pv->v);
    }
    
    printf("\n");
    
    DLinkList_Reset(list);//游标指向第一个结点   2
    DLinkList_Next(list);//游标指向第二个结点    3 
    
    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);
	system("pause");
	return 0;
}

//创建
DLinkList * DLinkList_Create()
{
	TDLinkList* list = NULL;
	list = (TDLinkList*)malloc(sizeof(TDLinkList));
	if(NULL != list)
	{
		list->len = 0;
		list->header.next = NULL;
		list->header.pre = NULL;
		list->slider = NULL;
	}
	return list;
}

//销毁
void DLinkList_DesTroy(DLinkList * list)
{
	free(list);
}

//清空
void DLinkList_Clear(DLinkList* list)
{
	TDLinkList* sList = (TDLinkList*)list;
	if(NULL != sList)
	{
		sList->len = 0;
		sList->header.next = NULL;
		sList->header.pre = NULL;
		sList->slider = NULL;
	}
}

//获得长度
int DLinkList_Length(DLinkList* list)
{
	TDLinkList* sList = (TDLinkList*)list;
	int len = -1;
	if(NULL != sList)
	{
		len = sList->len;
	}
	return len;
}

//插入
int DLinkList_Insert(DLinkList* list, DLinkListNode* node, int pos)
{
	TDLinkList* sList = (TDLinkList*)list;
	
	int i = 0;
	int ret = 0;
	if((NULL != sList) && (pos >= 0) && (NULL != node))
	{
		DLinkListNode* current = (DLinkListNode*)sList;
		DLinkListNode* next = NULL;
		for( i=0; (i<pos) && (current->next != NULL); i++)
		{
			current = current->next;
		}
		next = current->next;
		current->next = node;
		node->next = next;
		if(NULL != next)
		{
			next->pre = node;
		}
		node->pre = current;

		if(sList->len == 0)
		{
			node->pre = NULL;
			sList->slider = node;
		}
		sList->len++;
		ret = 1;
	}
	return ret;
}

//获得结点
DLinkListNode* DLinkList_Get(DLinkList* list, int pos)
{
	TDLinkList* sList = (TDLinkList*)list;
	int i = 0;
	DLinkListNode * resnode  = NULL;
	if((pos >= 0) && (pos < sList->len) && (NULL != sList))
	{
		DLinkListNode * current = (DLinkListNode*)sList;
		for ( i=0; i<pos; i++)
		{
			current = current->next;
		}
		resnode = current->next;
	}
	return resnode;
}


//删除
DLinkListNode* DLinkList_Delete(DLinkList* list, int pos)
{
	TDLinkList* sList = (TDLinkList*)list;
	int i = 0;
	DLinkListNode* ret = NULL;
	if((NULL != sList) && (pos >= 0) && (pos < sList->len))
	{
		DLinkListNode* current = (DLinkListNode*)sList;
		DLinkListNode* next = NULL;
		for ( i=0; i<pos; i++)
		{
			current = current->next;
		}
		ret = current->next;
		next = ret->next;

		current->next = next;
		if(NULL != next)
		{
			next->pre = current;
			//当删除的结点是第一个结点的时候
			if(current == (DLinkListNode*)sList)
			{
				//前驱指针为空
				next->pre = NULL;	
			}
		}
		if(sList->slider == ret)
		{
			sList->slider = next;
		}
		sList->len--;
	}
	return ret;
}

//通过指定结点删除
DLinkListNode* DLinkList_DeleteNode(DLinkList* list, DLinkListNode* node)
{
	TDLinkList* sList = (TDLinkList*)list;
	DLinkListNode* ret = NULL;
	int i = 0;
	if((NULL != sList) && (NULL != node))
	{
		DLinkListNode* current = (DLinkListNode*)sList;
		for ( i=0; i<sList->len; 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((NULL != sList))
	{
		sList->slider = sList->header.next;
		ret = sList->slider;
	}
	return ret;
}

//将游标移至当前结点处
DLinkListNode* DLinkList_Current(DLinkList* list)
{
	TDLinkList* sList = (TDLinkList*)list;
	DLinkListNode* ret = NULL;
	if(NULL != sList)
	{
		ret = sList->slider;
	}
	return ret;
}

//
DLinkListNode* DLinkList_Next(DLinkList* list)
{
	TDLinkList* sList = (TDLinkList*)list;
	DLinkListNode* ret = NULL;
	if((NULL != sList) && (NULL != sList->slider ))
	{
		ret = sList->slider;
		sList->slider = ret->next;
	}
	return ret;
}

DLinkListNode* DLinkList_Pre(DLinkList* list)
{
	TDLinkList* sList = (TDLinkList*)list;
	DLinkListNode* ret = NULL;
	if((NULL != sList) && (NULL != sList->slider ))
	{
		ret = sList->slider;
		sList->slider = ret->pre;
	}
	return ret;
}

执行结果：

插入了：1
插入了：2
插入了：3
插入了：4
插入了：5

删除头尾结点后：
2
3
4

游标移到第二个结点后的值： 3
游标删除第二个结点后的值： 4
游标向前移了一位后的值：2
Length: 2
请按随意键继续. . .

如有错误，望不吝指出。

鲜花

握手

雷人

路过

鸡蛋

该文章已有0人参与评论

请发表评论

全部评论

专题导读

More+

10-27 六六分期app的软件客服如何联系？(六六分期

11-06 可心卡盟:win10系统火狐flash插件崩溃怎么

11-06 亲亲特价:怎么删除回收站图标

11-06 济南大学虚拟社区:鲁大师节能降温的具体办

11-06 xlueops.exe:无线网络安装向导

11-06 女斗合众国:win7系统cf与主机连接不稳定怎

11-06 0xc000022-[cf烟雾头]cf怎么调烟雾头

11-06 qizideyouhuo:应用程序无法正常启动0xc0000

11-06 ipz-185:win7系统vcf文件怎么打开

11-06 傻哥蹦迪:win10系统s4怎么打开usb调试

11-06 八神浩树gtaste:回收站清空了怎么恢复

11-06 妖尾之黑色守护:win10系统电脑没有1440x900

11-06 校园至尊魔王小说:win7系统浏览网页时字体

11-06 女斗合众国:win10系统访问共享文件夹提示请

11-06 tokyo hot n0654:恢复win7系统默认字体一招

11-06 雨酷仙境:设置win7系统转移临时文件夹腾出

11-06 阿穆纳伊之杖:win7系统开始菜单在右边还原

11-06 tunespotting:win10系统火狐flash插件总是

11-06 甘尔葛分析师：计谋网站seo关键词暴涨有什

11-06 蔡贵霖: 计谋网站seo关键词暴涨有什么秘密

11-06 博益网首页:ao3网页版进入不了解决方法

11-06 漏斗子专栏: 网站数据分析小白易懂精华篇

11-06 见证双虹怎么做:win7系统开启telnet命令的

11-06 颾狐蝶蜋:系统资源不足无法完成请求的服务

11-06 国光中学校歌:提交网站到alexa查询详细步骤

11-06 西安有情天:静态网页和动态网页的区别

11-06 红木雅尚斋:外部链接构造对网站的好处

11-06 前官礼遇：防止域名劫持–增强域安全性的10

11-06 密传二转答案: 中文分词算法有哪些

11-06 金泉家园邮编:百度快照劫持的表现及应对方

C#获取局域网ip发布时间：2022-07-14

C#Dapper的简单实用发布时间：2022-07-14

剪的笔顺,诠释剪的笔画,认识剪的部首

六六分期app的软件客服如何联系？(六六分期

2023-10-27

florent37/ViewAnimator: A fluent Android

2022-08-15

florent37/Shrine-MaterialDesign2: implem

2022-08-17

CVE-2020-36276

2022-09-23

SimpleSoftwareIO/simple-sms: Send and re

2022-08-13

阅读排行榜

1 六六分期app的软件客服如何联系？(六六分期

六六分期app的软件客服如何联系？不知道吗？加qq群【895510560】即可！标题：六六分期

阅读：19146|2023-10-27

2 可心卡盟:win10系统火狐flash插件崩溃怎么

今天小编告诉大家如何处理win10系统火狐flash插件总是崩溃的问题，可能很多用户都不知

阅读：9973|2022-11-06

3 亲亲特价:怎么删除回收站图标

今天小编告诉大家如何对win10系统删除桌面回收站图标进行设置，可能很多用户都不知道

阅读：8317|2022-11-06

4 济南大学虚拟社区:鲁大师节能降温的具体办

今天小编告诉大家如何对win10系统电脑设置节能降温的设置方法，想必大家都遇到过需要

阅读：8686|2022-11-06

5 xlueops.exe:无线网络安装向导

我们在使用xp系统的过程中,经常需要对xp系统无线网络安装向导设置进行设置，可能很多

阅读：8628|2022-11-06

6 女斗合众国:win7系统cf与主机连接不稳定怎

今天小编告诉大家如何处理win7系统玩cf老是与主机连接不稳定的问题，可能很多用户都不

阅读：9643|2022-11-06

7 0xc000022-[cf烟雾头]cf怎么调烟雾头

电脑对日常生活的重要性小编就不多说了，可是一旦碰到win7系统设置cf烟雾头的问题，很

阅读：8611|2022-11-06

8 qizideyouhuo:应用程序无法正常启动0xc0000

我们在日常使用电脑的时候，有的小伙伴们可能在打开应用的时候会遇见提示应用程序无法

阅读：7991|2022-11-06

9 ipz-185:win7系统vcf文件怎么打开

今天小编告诉大家如何对win7系统打开vcf文件进行设置，可能很多用户都不知道怎么对win

阅读：8642|2022-11-06

10 傻哥蹦迪:win10系统s4怎么打开usb调试

今天小编告诉大家如何对win10系统s4开启USB调试模式进行设置，可能很多用户都不知道怎

阅读：7527|2022-11-06

客服电话

电子邮件

双向链表的实现与操作(C语言实现)

请发表评论

全部评论

上一篇：

下一篇：

CVE-2022-35373

krishnaik06/Machine-Learning-in-90-days

treesouth/AndroidLibrary: A list of awes

微信小程序返回页面传值

armancodv/building-energy-model-matlab:

剪的笔顺,诠释剪的笔画,认识剪的部首

六六分期app的软件客服如何联系？(六六分期

florent37/ViewAnimator: A fluent Android

florent37/Shrine-MaterialDesign2: implem

CVE-2020-36276

SimpleSoftwareIO/simple-sms: Send and re

关于我们

产品与服务

解决方案

139-2527-9053