数据结构：线性表链式存储结构（双向链表） C语言版

程序员文章站 2022-05-06 12:42:12

...

双向链表：

在单链表中，有了 next 指针，这使得查找下一结点的时间复杂度为 $O(1)$ ，可是如果我们查找上一结点的话，那最坏的时间复杂度就是 $O(n)$ 了，因为每次都要从头开始遍历查找。
双向链表就克服了这一缺陷。双向链表 ( Double Linked List ) 是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。 所以，在双向链表中的结点都有两个指针域，一个指向直接后继，了另一个指向直接前驱。

typedef struct _Tag_D_LinkList_Node
{
	struct _Tag_D_LinkList_Node* next; //后继
	struct _Tag_D_LinkList_Node* prec; //前驱
}DLTNode;							   //双向链表节点

既然单链表有循环链表，双向链表也可以有循环双向链表。
包含头节点的双向循环空链表，其结构如下图：
数据结构：线性表链式存储结构（双向链表） C语言版
非空的双向循环链表带头结点的结构如下图：

双向链表的代码设置与实现：

数据结构：线性表链式存储结构（双向链表） C语言版

基于 liunx 内核链表模型

1：头文件，定义数据结构和操作函数

#ifndef  _D_LINK_LIST_H_
#define  _D_LINK_LIST_H_


#define  DLINK_LIST_ERR_POS   (DLINK_LIST_ERROR-2)    //位置下标超出范围 
#define  DLINK_LIST_ERR_NULL  (DLINK_LIST_ERROR-1)    //数据或参数为空
#define  DLINK_LIST_ERROR     (-1)                    //错误
#define  DLINK_LIST_VALID     (DLINK_LIST_ERROR+1)    //正确



typedef void DLinkList;

typedef struct _Tag_D_LinkList_Node
{
	struct _Tag_D_LinkList_Node* next; //后继
	struct _Tag_D_LinkList_Node* prec; //前驱
}DLTNode;							   //双向链表节点

//创建链表
DLinkList* DLinkList_Create();

//释放链表指针空间
void DLinkList_Destroy(DLinkList* list);

//清空链表
void DLinkList_Clear(DLinkList* list);

//获取链表元素个数
int DLinkList_Length(DLinkList* list);

//根据给定位置下标插入元素
int DLinkList_Insert(DLinkList* list, DLTNode* node, int pos);

//根据给定位置获取元素节点
DLTNode* DLinkList_Get(DLinkList* list, int pos);

//根据给定位置删除元素节点
DLTNode* DLinkList_Delete(DLinkList* list, int pos);

//删除指定的元素节点
DLTNode* DLinkList_DeleteNode(DLinkList* list, DLTNode* node);

//重置链表
DLTNode* DLinkList_Reset(DLinkList* list);

//获取当前链表游标指向元素
DLTNode* DLinkList_Current(DLinkList* list);

//获取当前链表游标指向元素的下一个元素
DLTNode* DLinkList_Next(DLinkList* list);

//获取当前链表游标指向元素的上一个元素
DLTNode* DLinkList_Pre(DLinkList* list);

#endif //_D_LINK_LIST_H_

2：函数实现：

#include "DLinkList.h"
#include <stdlib.h>
#include<memory.h>

typedef struct _Tag_DLink_List
{
	DLTNode 	pHeader;     //链表头指针
	DLTNode*	slider;      //链表游标
	int			length;      //链表数据长度
}TDList;					 //链表内部数据结构	


//创建链表
DLinkList* DLinkList_Create()
{
	TDList* pdList = (TDList*)malloc(sizeof(TDList));
	if (pdList!=NULL)
	{
		memset(pdList, 0x00, sizeof(TDList));
		pdList->length = 0;
		pdList->pHeader.next = NULL;
		pdList->pHeader.prec = NULL;
		pdList->slider = NULL;
	}
	return pdList;
}

//释放链表指针空间
void DLinkList_Destroy(DLinkList* list)
{
	if (list!=NULL)
	{
		free(list);
	}
}

//清空链表
void DLinkList_Clear(DLinkList* list)
{
	TDList* pdList = (TDList*)list;
	if (pdList!=NULL)
	{
		pdList->length = 0;
		pdList->slider = NULL;
		pdList->pHeader.next = NULL;
		pdList->pHeader.prec = NULL;
	}
	return ;
}

//获取链表元素个数
int DLinkList_Length(DLinkList* list)
{
	TDList* pdList = (TDList*)list;
	if (pdList==NULL)
	{
		return DLINK_LIST_ERROR;
	}
	return pdList->length;
}

//根据给定位置下标插入元素
int DLinkList_Insert(DLinkList* list, DLTNode* node, int pos)
{
	int		i = 0;
	TDList* pdList = (TDList*)list;
	if (pdList == NULL || node == NULL)
	{
		return DLINK_LIST_ERR_NULL;
	}
	if (pos < 0)
	{
		return DLINK_LIST_ERR_POS;
	}

	//声明辅助指针变量
	DLTNode* currNode = (DLTNode*)pdList; //指针指向链表头部
	DLTNode* nextNode = NULL;
	{
		
		for (i = 0; i < pos && (currNode->next != NULL); i++)
		{
			currNode = currNode->next;//指针移动到指定位置
		}
		nextNode = currNode->next;//当前位置的元素
		//交换位置
		currNode->next = node;//插入当前节点
		node->next = nextNode;//要插入的元素节点的后继指针指向原来位置的节点 

		//nextNode==NULL表示当前链表插入第一个元素 要特殊处理,如果不是则让后续元素的前驱指针指向当前插入元素
		if (nextNode !=NULL)
		{
			nextNode->prec = node;//前驱指向要插入的元素
		}

		if (pdList->length == 0)
		{
			pdList->slider = node;
		}

		if (currNode == (DLTNode*)pdList)//当前在0号位置插入元素
		{
			node->prec = NULL;
		}
		else
		{
			node->prec = currNode;
		}
		pdList->length++;
	}
	return DLINK_LIST_VALID;
}

//根据给定下标位置获取元素节点
DLTNode* DLinkList_Get(DLinkList* list, int pos)
{
	TDList* pdList = (TDList*)list;
	DLTNode* ret = NULL;
	int i = 0;
	if (pdList != NULL && 0 <= pos&&pos < pdList->length);
	{
		DLTNode* currTmp = (DLTNode*)pdList;
		for (i = 0; i < pos;i++)
		{
			currTmp = currTmp->next;
		}
		ret = currTmp->next;
	}
	return ret;
}

//根据给定位置删除元素节点
DLTNode* DLinkList_Delete(DLinkList* list, int pos)
{
	TDList  *pdList = (TDList*)list;
	DLTNode *ret = NULL, *next = NULL;
	int i = 0;
	if (pdList==NULL||pos<0)
	{
		return NULL;
	}

	DLTNode* currTmp = (DLTNode*)pdList;
	for (i = 0; i < pos;i++)
	{
		currTmp = currTmp->next;
	}
	ret = currTmp->next;//要删除的节点
	next = ret->next;//删除节点的下一节点

	currTmp->next = next;//1：跳过删除的节点，后驱指针进行链表连接
	if (next!=NULL)//2:前驱指针进行连接
	{
		next->prec = currTmp;
		if (currTmp == (DLTNode*)pdList)//如果是头节点，前驱指针指向NULL
		{
			next->prec = NULL;
		}
	}

	if (pdList->slider==ret)
	{
		pdList->slider = next;
	}
	pdList->length--;

	return ret;
}

//删除指定的元素节点
DLTNode* DLinkList_DeleteNode(DLinkList* list, DLTNode* node)
{
	TDList* pdList = (TDList*)list;
	DLTNode* ret = NULL;
	int i = 0;
	if (pdList!=NULL&&node!=NULL)
	{
		DLTNode *currTmp = (DLTNode*)pdList;
		for (i = 0; i < pdList->length; i++)
		{
			if (currTmp->next=node)
			{
				ret = currTmp->next;
				break;
			}
			currTmp = currTmp->next;
		}
		if (ret!=NULL)
		{
			DLinkList_Delete(pdList, i);
		}
	}

	return ret;
}

//重置链表游标
DLTNode* DLinkList_Reset(DLinkList* list)
{
	TDList* pdList = (TDList*)list;
	DLTNode* ret = NULL;
	if (pdList!=NULL)
	{
		pdList->slider = pdList->pHeader.next;
		ret = pdList->slider;
	}
	return ret;
}

//获取当前链表游标指向元素
DLTNode* DLinkList_Current(DLinkList* list)
{
	TDList* pdList = (TDList*)list;
	DLTNode* ret = NULL;
	if (pdList!=NULL)
	{
		ret = pdList->slider;
	}
	return ret;
}

//获取当前链表游标指向的元素并且游标下移指向下一个元素
DLTNode* DLinkList_Next(DLinkList* list)
{
	TDList* pdList = (TDList*)list;
	DLTNode* ret = NULL;
	if (pdList != NULL&&pdList->slider!=NULL)
	{
		ret = pdList->slider;
		pdList->slider = ret->next;
	}
	return ret;
}

//获取当前链表游标指向的元素并且游标上移指向上一个元素
DLTNode* DLinkList_Pre(DLinkList* list)
{
	TDList* pdList = (TDList*)list;
	DLTNode* ret = NULL;
	if (pdList != NULL&&pdList->slider != NULL)
	{
		ret = pdList->slider;
		pdList->slider = ret->prec;
	}
	return ret;
}

函数重点操作：
插入操作：

数据结构：线性表链式存储结构（双向链表） C语言版
删除操作：

数据结构：线性表链式存储结构（双向链表） C语言版
3：调用示例：

#define  _CRT_SECURE_NO_WARNINGS
#include "DLinkList.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct _User_info
{
	DLTNode node;
	int age;
	char name[16];
}User;

int main(int argc, char *argv[])
{
	int i = 0;
	User *tmp = NULL;
	DLinkList* list = DLinkList_Create();

	User u1, u2, u3, u4, u5, u6;
	{
		u1.age = 11;
		u2.age = 12;
		u3.age = 13;
		u4.age = 14;
		u5.age = 15;
		u6.age = 16;
		strcpy(u1.name, "AAAA");
		strcpy(u2.name, "BBBB");
		strcpy(u3.name, "CCCC");
		strcpy(u4.name, "DDDD");
		strcpy(u5.name, "EEEE");
		strcpy(u6.name, "FFFF");
	}

	//插入数据
	DLinkList_Insert(list, (DLTNode*)&u1, DLinkList_Length(list));
	DLinkList_Insert(list, (DLTNode*)&u2, DLinkList_Length(list));
	DLinkList_Insert(list, (DLTNode*)&u3, DLinkList_Length(list));
	DLinkList_Insert(list, (DLTNode*)&u4, DLinkList_Length(list));
	DLinkList_Insert(list, (DLTNode*)&u5, DLinkList_Length(list));
	DLinkList_Insert(list, (DLTNode*)&u6, DLinkList_Length(list));

	for (i = 0; i < DLinkList_Length(list); i++)
	{
		tmp = (User *)DLinkList_Get(list, i);
		if (tmp==NULL)
		{
			printf("获取元素失败\n");
			break;
		}
		printf("age=%d ; name=%s \n", tmp->age, tmp->name);
	}

	DLinkList_Reset(list); //重置链表游标
	DLinkList_Next(list);//链表游标下移

	tmp =(User*) DLinkList_Current(list);
	printf("age=%d ; name=%s \n", tmp->age, tmp->name);

	DLinkList_Pre(list); //链表游标上移
	tmp = (User*)DLinkList_Current(list);
	printf("age=%d ; name=%s \n", tmp->age, tmp->name);

	printf("list count=%d \n", DLinkList_Length(list));

	DLinkList_Destroy(list);

	system("pause");
}

输出：
数据结构：线性表链式存储结构（双向链表） C语言版

相关标签：算法数据结构双向链表 Linux 内核链表

上一篇：【CODE】CoderPad——单链表

下一篇：数据结构（四）链表

数据结构：线性表链式存储结构（双向链表） C语言版

双向链表：

双向链表的代码设置与实现：

C语言数据结构之线性表的链式存储结构

数据结构——有序链表合并（C语言版）

C#数据结构入门（动态数组、泛型列表、字典、栈、队列、双向链表）

线性表的Java实现--链式存储（双向链表）

C语言数据结构-离散存储链表定义

数据结构之---C语言实现广义表头尾链表存储表示

C#数据结构之双向链表(DbLinkList)实例详解

C语言（数据结构） - 双向链表的基本操作

[C语言] 数据结构-离散存储链表定义

c语言数据结构之线性表的顺序存储结构