双向链表实现（C语言）_c语言 双链表实现

目录

 

1. 概念

2. 构造与使用

2.1 双链表的结构体

2.2 从头节点添加

2.3 从尾部添加

2.4 从中间添加节点

2.5 添加节点实例：按升序插入一个节点

2.6 从头结点处删除节点

2.7 从尾节点处删除节点

2.8 从中间删除节点

2.9 删除节点的一个实例：删除指定的节点

2.10 清空链表

2.11 完整代码

---

1. 概念

百度百科：双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

2. 构造与使用

2.1 双链表的结构体

struct _d_list
{
	int data;
	struct _d_list *pre;
	struct _d_list *next;
};
 
typedef struct _d_list DL_LINK_LIST;
 
//节点的初始化
 
void init_d_list_node(DL_LINK_LIST * node, const int data)
{
	node->data = data;
	node->pre = NULL;
	node->next = NULL;
}

2.2 从头节点添加

添加至表头 将新数据元素添加到表头，只需要将该元素与表头元素建立双层逻辑关系即可。

换句话说，假设新元素节点为 temp，表头节点为 head，则需要做以下 2 步操作即可：

temp->next = head; head->prior = temp;

将 head 移至 temp，重新指向新的表头；

//从头添加
//添加至表头 将新数据元素添加到表头，只需要将该元素与表头元素建立双层逻辑关系即可。
//
//换句话说，假设新元素节点为 temp，表头节点为 head，则需要做以下 2 步操作即可：
//
//temp->next = head; head->prior = temp;
//将 head 移至 temp，重新指向新的表头；
 
DL_LINK_LIST * _d_list_add_head(DL_LINK_LIST *head, int data)
{
	if (head == NULL)
	{
		printf("@_d_list_add_head, param head is null, can not trans continue!\n");
		return head;
	}
 
	// 创建节点
	DL_LINK_LIST *node = (DL_LINK_LIST *)malloc(sizeof(DL_LINK_LIST));
	if (NULL == node)
	{
		printf("Not enogh memory to get!\n");
		return head;
	}
 
	init_d_list_node(node, data);
 
	printf("@_d_list_add_head---->try to add %d.\n", data);
	// 从头结点添加
	node->next = head;	// 新节点作为头  那么新节next就是目前的head node->next  = head;
	head->pre = node;	// 当前head的上一个节点pre就是新节点
	head = node;	// 链接完成后 记录新的head
 
	return head;
}

2.3 从尾部添加

从尾部添加双向链表节点，较简单。

// 从尾部添加
DL_LINK_LIST * _d_list_add_tail(DL_LINK_LIST *head, int data)
{
	printf("@_d_list_add_tail---->try to add %d.\n", data);
	if (head == NULL)
	{
		printf("@_d_list_add_tail, param head is null, can not trans continue!\n");
		return head;
	}
 
	// 创建节点
	DL_LINK_LIST *node = (DL_LINK_LIST *)malloc(sizeof(DL_LINK_LIST));
	if (NULL == node)
	{
		printf("Not enogh memory to get!");
		return head;
	}
 
	init_d_list_node(node, data);
 
	// 找到链表的最后一个元素
	DL_LINK_LIST *p = head;
	while (p->next != NULL)
	{
		p = p->next;
	}
 
	// add
	p->next = node;
	node->pre = p;
 
	return head;
}

2.4 从中间添加节点

从中间添加节点，头结点不变，代码如下

bool _d_list_insert_mid(DL_LINK_LIST * p, int data)
{
	// p为根据条件找到的p->data >= data 的中间节点  新节点要插入在p之前
	if (p == NULL)
	{
		printf("@_d_list_insert_mid, param in node is NULL, can not do insert\n");
		return false;
	}
 
	// 创建节点
	DL_LINK_LIST *node = (DL_LINK_LIST *)malloc(sizeof(DL_LINK_LIST));
	if (NULL == node)
	{
		printf("Not enogh memory to get!");
		return false;
	}
	init_d_list_node(node, data);
 
	// 如果找到了  p->data >= data    node 在p前面  因此节点关系为  
	/*
		pre	---------> p--------->
			<----------
			left<--node -->right
			node 的pre指向pre
			node的next 指向p
			以p来标识
	*/
 
	printf("@_d_list_insert_mid---->try to insert %d.\n", data);
	node->pre = p->pre;	// 1. 连接前节点pre与新增节点node  以p标识前节点为  p->pre  因此  node->pre = p->pre
	node->pre->next = node;	//  2.前节点的next  连接到node   因此  标识为   node->pre->next = node;
	node->next = p;		// 3.连接 node与p 
	p->pre = node;	// 4.p的前节点为新增node
 
	return true;
}

2.5 添加节点实例：按升序插入一个节点

// 以升序排序的案例为例子 插入到指定节点
// 从尾部添加
DL_LINK_LIST * _d_list_insert_by_data(DL_LINK_LIST *head, int data)
{
	if (head == NULL)
	{
		printf("@_d_list_insert_by_data, param head is null, can not trans continue!\n");
		return head;
	}
	
 
	DL_LINK_LIST *p = head;
	while (p->next != NULL &&(p->data <data))//  要保证p不能为NULL 因此判断条件为p->next != NULL
	{
		p = p->next;
	}
	printf("@_d_list_insert_by_data---->try to insert %d.\n", data);
 
	if (p->data >= data)
	{
		// 如果插入头结点之前
		if (p == head)
		{
			head = _d_list_add_head(head, data);
		}
		else
		{
			// 找到在中间  按照中间法插入   head 不变
			 (void)_d_list_insert_mid(p, data);
		}
	}
	else
	{
		// 未找到比data大的数据  添加在末尾
		printf("@_d_list_insert_by_data---->未找到比data大的数据  添加在末尾 try to insert %d.\n", data);
		head = _d_list_add_tail(head, data);
	}
 
	return head;
}

2.6 从头结点处删除节点

DL_LINK_LIST * _d_list_del_head(DL_LINK_LIST *head)
{
	if (head == NULL)
	{
		printf("@_d_list_del_head, the list head is NULL!\n");
		return head;
	}
 
	// 删除头节点
	DL_LINK_LIST *p = head;
	head = head->next;	// 将head后移
	if (head != NULL)
	{
		head->pre = NULL;
	}
	
 
	free(p);
	p = NULL;
 
	return head;
}

2.7 从尾节点处删除节点

DL_LINK_LIST * _d_list_del_tail(DL_LINK_LIST *head)
{
	if (head == NULL)
	{
		printf("@_d_list_del_tail, the list head is NULL!\n");
		return head;
	}
 
	DL_LINK_LIST *p = head;
	while (p->next != NULL)
	{
		p = p->next;
	}
 
	// 删除尾节点p p为尾结点  上一个可能是头结点 头结点pre 为NULL
	if (p->pre != NULL)
	{
		p->pre->next = NULL;	// 尾节点的上一个节点next指向空
	}
	
	if (p == head)
	{
		//如果当前删除的是head  将head置空
		head = NULL;
	}
 
	free(p);
	p = NULL;
 
	return head;
}

2.8 从中间删除节点

//从中间删除
bool _d_list_del_mid_node(DL_LINK_LIST *p)
{
	if (p == NULL)
	{
		printf("@_d_list_del_mid_node, param in node is NULL, can not do insert\n");
		return false;
	}
 
	p->pre->next = p->next;	// 前节点指向后节点 next
	p->next->pre = p->pre;  // 后节点指向前节点 pre
 
 
	free(p);
	p = NULL;
 
	return true;
}

2.9 删除节点的一个实例：删除指定的节点

// 删除指定节点
DL_LINK_LIST * _d_list_del_by_data(DL_LINK_LIST *head, int data)
{
	if (head == NULL)
	{
		printf("@_d_list_del_by_data, param head is null, can not trans continue!\n");
		return head;
	}
 
	printf("@_d_list_del_by_data---->try to delete %d.\n", data);
 
	DL_LINK_LIST *p = head;
	while (p->next != NULL && (p->data != data))
	{
		p = p->next;
	}
 
	if (p->data == data)
	{
		// 如果是头结点
		if(p == head)
		{
			// 删除头
			head = _d_list_del_head(head);
		}
		else
		{
			if (p->next == NULL)
			{
				// 删除尾节点
				head = _d_list_del_tail(head);
			}
			else
			{
				// head 不变
				(void)_d_list_del_mid_node(p);
			}
		}
	}
	else
	{
		printf("@_d_list_del_by_data, can not find the data %d\n", data);
	}
 
	return head;
}

2.10 清空链表

void _d_list_del_all(DL_LINK_LIST *head)
{
	printf("_d_list_del_all******************\n");
	while (head != NULL)
	{
		//head = _d_list_del_head(head);  //测试通过
		head = _d_list_del_tail(head);
	}
}

2.11 完整代码

代码已在visual 2017编译通过，完整的使用实例代码如下：

// d_list.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
 
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
 
struct _d_list
{
	int data;
	struct _d_list *pre;
	struct _d_list *next;
};
 
typedef struct _d_list DL_LINK_LIST;
 
 
void init_d_list_node(DL_LINK_LIST * node, const int data)
{
	node->data = data;
	node->pre = NULL;
	node->next = NULL;
}
 
 
 
//从头添加
//添加至表头 将新数据元素添加到表头，只需要将该元素与表头元素建立双层逻辑关系即可。
//
//换句话说，假设新元素节点为 temp，表头节点为 head，则需要做以下 2 步操作即可：
//
//temp->next = head; head->prior = temp;
//将 head 移至 temp，重新指向新的表头；
 
DL_LINK_LIST * _d_list_add_head(DL_LINK_LIST *head, int data)
{
	if (head == NULL)
	{
		printf("@_d_list_add_head, param head is null, can not trans continue!\n");
		return head;
	}
 
	// 创建节点
	DL_LINK_LIST *node = (DL_LINK_LIST *)malloc(sizeof(DL_LINK_LIST));
	if (NULL == node)
	{
		printf("Not enogh memory to get!\n");
		return head;
	}
 
	init_d_list_node(node, data);
 
	printf("@_d_list_add_head---->try to add %d.\n", data);
	// 从头结点添加
	node->next = head;	// 新节点作为头  那么新节next就是目前的head node->next  = head;
	head->pre = node;	// 当前head的上一个节点pre就是新节点
	head = node;	// 链接完成后 记录新的head
 
	return head;
}
 
 
 
// 从尾部添加
DL_LINK_LIST * _d_list_add_tail(DL_LINK_LIST *head, int data)
{
	printf("@_d_list_add_tail---->try to add %d.\n", data);
	if (head == NULL)
	{
		printf("@_d_list_add_tail, param head is null, can not trans continue!\n");
		return head;
	}
 
	// 创建节点
	DL_LINK_LIST *node = (DL_LINK_LIST *)malloc(sizeof(DL_LINK_LIST));
	if (NULL == node)
	{
		printf("Not enogh memory to get!");
		return head;
	}
 
	init_d_list_node(node, data);
 
	// 找到链表的最后一个元素
	DL_LINK_LIST *p = head;
	while (p->next != NULL)
	{
		p = p->next;
	}
 
	// add
	p->next = node;
	node->pre = p;
 
	return head;
}
 
 
bool _d_list_insert_mid(DL_LINK_LIST * p, int data)
{
	// p为根据条件找到的p->data >= data 的中间节点  新节点要插入在p之前
	if (p == NULL)
	{
		printf("@_d_list_insert_mid, param in node is NULL, can not do insert\n");
		return false;
	}
 
	// 创建节点
	DL_LINK_LIST *node = (DL_LINK_LIST *)malloc(sizeof(DL_LINK_LIST));
	if (NULL == node)
	{
		printf("Not enogh memory to get!");
		return false;
	}
	init_d_list_node(node, data);
 
	// 如果找到了  p->data >= data    node 在p前面  因此节点关系为  
	/*
		pre	---------> p--------->
			<----------
			left<--node -->right
			node 的pre指向pre
			node的next 指向p
			以p来标识
	*/
 
	printf("@_d_list_insert_mid---->try to insert %d.\n", data);
	node->pre = p->pre;	// 1. 连接前节点pre与新增节点node  以p标识前节点为  p->pre  因此  node->pre = p->pre
	node->pre->next = node;	//  2.前节点的next  连接到node   因此  标识为   node->pre->next = node;
	node->next = p;		// 3.连接 node与p 
	p->pre = node;	// 4.p的前节点为新增node
 
	return true;
}
 
// 以升序排序的案例为例子 插入到指定节点
// 从尾部添加
DL_LINK_LIST * _d_list_insert_by_data(DL_LINK_LIST *head, int data)
{
	if (head == NULL)
	{
		printf("@_d_list_insert_by_data, param head is null, can not trans continue!\n");
		return head;
	}
	
 
	DL_LINK_LIST *p = head;
	while (p->next != NULL &&(p->data <data))//  要保证p不能为NULL 因此判断条件为p->next != NULL
	{
		p = p->next;
	}
	printf("@_d_list_insert_by_data---->try to insert %d.\n", data);
 
	if (p->data >= data)
	{
		// 如果插入头结点之前
		if (p == head)
		{
			head = _d_list_add_head(head, data);
		}
		else
		{
			// 找到在中间  按照中间法插入   head 不变
			 (void)_d_list_insert_mid(p, data);
		}
	}
	else
	{
		// 未找到比data大的数据  添加在末尾
		printf("@_d_list_insert_by_data---->未找到比data大的数据  添加在末尾 try to insert %d.\n", data);
		head = _d_list_add_tail(head, data);
	}
 
	return head;
}
 
 
 
DL_LINK_LIST * _d_list_del_head(DL_LINK_LIST *head)
{
	if (head == NULL)
	{
		printf("@_d_list_del_head, the list head is NULL!\n");
		return head;
	}
 
	// 删除头节点
	DL_LINK_LIST *p = head;
	head = head->next;	// 将head后移
	if (head != NULL)
	{
		head->pre = NULL;
	}
	
 
	free(p);
	p = NULL;
 
	return head;
}
 
DL_LINK_LIST * _d_list_del_tail(DL_LINK_LIST *head)
{
	if (head == NULL)
	{
		printf("@_d_list_del_tail, the list head is NULL!\n");
		return head;
	}
 
	DL_LINK_LIST *p = head;
	while (p->next != NULL)
	{
		p = p->next;
	}
 
	// 删除尾节点p p为尾结点  上一个可能是头结点 头结点pre 为NULL
	if (p->pre != NULL)
	{
		p->pre->next = NULL;	// 尾节点的上一个节点next指向空
	}
	
	if (p == head)
	{
		//如果当前删除的是head  将head置空
		head = NULL;
	}
 
	free(p);
	p = NULL;
 
	return head;
}
 
 
//从中间删除
bool _d_list_del_mid_node(DL_LINK_LIST *p)
{
	if (p == NULL)
	{
		printf("@_d_list_del_mid_node, param in node is NULL, can not do insert\n");
		return false;
	}
 
	p->pre->next = p->next;	// 前节点指向后节点 next
	p->next->pre = p->pre;  // 后节点指向前节点 pre
 
 
	free(p);
	p = NULL;
 
	return true;
}
 
// 删除指定节点
DL_LINK_LIST * _d_list_del_by_data(DL_LINK_LIST *head, int data)
{
	if (head == NULL)
	{
		printf("@_d_list_del_by_data, param head is null, can not trans continue!\n");
		return head;
	}
 
	printf("@_d_list_del_by_data---->try to delete %d.\n", data);
 
	DL_LINK_LIST *p = head;
	while (p->next != NULL && (p->data != data))
	{
		p = p->next;
	}
 
	if (p->data == data)
	{
		// 如果是头结点
		if(p == head)
		{
			// 删除头
			head = _d_list_del_head(head);
		}
		else
		{
			if (p->next == NULL)
			{
				// 删除尾节点
				head = _d_list_del_tail(head);
			}
			else
			{
				// head 不变
				(void)_d_list_del_mid_node(p);
			}
		}
	}
	else
	{
		printf("@_d_list_del_by_data, can not find the data %d\n", data);
	}
 
	return head;
}
 
void _d_list_del_all(DL_LINK_LIST *head)
{
	printf("_d_list_del_all******************\n");
	while (head != NULL)
	{
		//head = _d_list_del_head(head);  //测试通过
		head = _d_list_del_tail(head);
	}
}
 
 
void _d_list_diaplay(DL_LINK_LIST* head)
{
	printf("__d_list_diaplay******************\n");
 
	DL_LINK_LIST *p = head;
	int i = 1;
	while (p != NULL)
	{
		printf("_d_list_ Num %d data = %d.\n", i, p->data);
		p = p->next;
		i++;
	}
}
 
int main()
{
    std::cout << "Hello World!\n";
	// 创建双向链表
	DL_LINK_LIST *head = (DL_LINK_LIST*)malloc(sizeof(DL_LINK_LIST));
	init_d_list_node(head, -1);
	for (int i = 0; i < (13*10); i+= 13)
	{
		// apped5个 
		if(i <13*5)
		{
			// 尾插入
			head = _d_list_add_tail(head, i);
		}
		else
		{
			//尾插入
			head = _d_list_add_head(head, i);
		}
	}
 
	_d_list_diaplay(head);
	// 插入中间数值
	head = _d_list_insert_by_data(head, 14);
	head = _d_list_insert_by_data(head, 33);
	head = _d_list_insert_by_data(head, 120);
	_d_list_diaplay(head);
	// 删除中间值
	head = _d_list_del_by_data(head, 15);
	head = _d_list_del_by_data(head, 26);
	_d_list_diaplay(head);
	// 删除头  
	head = _d_list_del_by_data(head, 14);
	// 删除尾
	head = _d_list_del_by_data(head, 120);
	_d_list_diaplay(head);
	_d_list_del_all(head);
 
}
 
// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单
 
// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件