Technology Sharing

【Data structure】Doubly linked list

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Hi~! This is the struggling lamb. I am honored that you can read my article. Please give me comments and suggestions. Welcome~~
💥💥个人主页：The struggling lamb
💥💥所属专栏：C

🚀本系列文章为个人学习笔记，在这里撰写成文一为巩固知识，二为展示我的学习过程及理解。文笔、排版拙劣，望见谅。

Table of contents

Preface

A singly linked list can only access data in one direction through the address of a certain node, while a doubly linked list can access data in two directions through the address of a certain node. The efficiency of adding, deleting, checking and modifying is higher, but the code implementation is simpler than that of a singly linked list. In general, the advantages of a doubly linked list are more obvious.

1. Classification of linked lists

There are eight types of linked lists: headed, headless, unidirectional, bidirectional, cyclic, and non-cyclic. We will only learn the common ones.Headless one-way non-circular linked listandHeaded bidirectional circular linked list, that isSingle listandDoubly linked list。
Doubly linked list:
insert image description here
In fact, in the previous article, we called the first node of the singly linked list the head node, which is not accurate. The reason for calling it this way is to make it easier to understand, because a singly linked list has no head, and a doubly linked list has a head node, also calledSentinel。

  • The head node of the bidirectional linked list does not store valid data, but invalid data.
  • The sentinel position cannot be changed, only its direction can be changed

2. Implementation of a bidirectional linked list

2.1 Doubly Linked List Node

The nodes of a doubly linked list need to store data and the addresses of the previous and next nodes, so the nodes of a doubly linked list are:

typedef int dlist_data_type;

//双向链表节点
typedef struct dlist
{
	dlist_data_type data;
	struct dlist* next
	struct dlist* prev;
}dlist;

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

2.2 Application Node

Unlike a singly linked list, a doubly linked list must have at least one node, which is the head node, also called the sentinel.
Before adding, deleting, checking, or modifying,The doubly linked list must initialize a sentinel bit, which stores an invalid data.

Initially, the two pointers of the requested node point to itself.。

//申请节点
dlist* dlist_buy(dlist_data_type x)
{
	dlist* newdlist = (dlist*)malloc(sizeof(dlist));
	if (newdlist == NULL)
	{
		perror("malloc fail!");
		return 1;
	}
	newdlist->data = x;
	newdlist->next = newdlist;
	newdlist->prev = newdlist;
	return newdlist;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

There are two ways to initialize the sentinel bit:
Returns as parameters:

void dlist_init(dlist** pphead)
{
	assert(pphead);
	*pphead = dlist_buy(-1);
}

  • 1
  • 2
  • 3
  • 4
  • 5

This method requires the use of a secondary pointer.
Returned as a return value:

dlist* dlist_init()
{
	dlist* phead = dlist_buy(-1);
	return phead;
}

  • 1
  • 2
  • 3
  • 4
  • 5

This method is simpler and easier to understand.

2.3 Printing and searching data

Printing and searching data are not much different from singly linked lists, so I will not go into details.
The only thing to note is the condition for ending the loop. The loop ends when the pointer points to the sentinel position, not when theNULL。

//打印数据
void dlist_print(dlist* phead)
{
	assert(phead);
	dlist* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULLn");
}
//查找
dlist* dlist_find(dlist* phead, dlist_data_type x)
{
	assert(phead);
	dlist* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27

2.4 Header and tailer plugs

Unlike a singly linked list, the addition, deletion, query and modification operations of a doubly linked list do not change the sentinel position, so onlyCall by valueThat's it.
The insertion operation of a bidirectional linked list requires modification of three nodes. During the modification process, pay attention toModify the new node first, then modify the next node, and finally modify the previous node.

//插入操作不改变哨兵位，因此传一级指针即可
//尾插
void dlist_push_back(dlist* phead, dlist_data_type x)
{
	assert(phead);
	dlist* newdlist = dlist_buy(x);

	//新尾节点
	newdlist->prev = phead->prev;
	newdlist->next = phead;

	//旧尾节点
	phead->prev->next = newdlist;

	//头节点（哨兵位）
	phead->prev = newdlist;
}
//头插
void dlist_push_front(dlist* phead, dlist_data_type x)
{
	assert(phead);
	dlist* newdlist = dlist_buy(x);

	//新节点
	newdlist->prev = phead;
	newdlist->next = phead->next;

	//旧节点
	phead->next->prev = newdlist;

	//哨兵位
	phead->next = newdlist;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33

2.5 Header and tailer deletion

The prerequisite for the deletion operation is that there must be no node (Sentinel position does not count), save the address of the node before deleting it, reassemble the doubly linked list, and then release the node.

//尾删
void dlist_pop_back(dlist* phead)
{
	assert(phead);
	assert(phead->next != phead);//双向链表不能为空
	dlist* del = phead->prev;
	//新尾节点
	del->prev->next = phead;
	//哨兵位
	phead->prev = del->prev;
	free(del);
	del = NULL;
}

//头删
void dlist_pop_front(dlist* phead)
{
	assert(phead);
	assert(phead->next != phead);
	dlist* del = phead->next;
	del->next->prev = phead;
	phead->next = del->next;
	free(del);
	del = NULL;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25

2.6 Insert and delete data at the specified location

//在指定位置之后插入数据
void dlist_insert_back(dlist* pos, dlist_data_type x)
{
	assert(pos);
	dlist* newdlist = dlist_buy(x);
	newdlist->prev = pos;
	newdlist->next = pos->next;

	pos->next->prev = newdlist;
	pos->next = newdlist;
}
//删除指定位置的节点
void dlist_erase(dlist* pos)
{
	assert(pos);
	dlist* del = pos;
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

After deleting the data at the specified location,Because this function is called by value, after releasing the node at the specified position, we just set the parameter pointer toNULL, and the actual parameter pointer still points to this position, so after the function call is completed, the actual parameter pointer must be resetNULL。

2.7 Destroying a Doubly Linked List

The end condition of the doubly linked list destruction is also to jump out of the loop when the traversal pointer points to the head node.Finally, the sentinel position must be released separatelyAfter the destruction function of the doubly linked list is called, the pointer to the sentinel position must also be setNULL。

//销毁
void dlist_destroy(dlist* phead)
{
	assert(phead);
	dlist* pcur = phead->next;
	while (pcur != phead)
	{
		dlist* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free(pcur);
	pcur = NULL;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

3. Complete code of bidirectional linked list

dlist.h:

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int dlist_data_type;

//双向链表节点
typedef struct dlist
{
	dlist_data_type data;
	struct dlist* next;
	struct dlist* prev;
}dlist;

//初始化
//插入数据之前，双向链表必须初始化到只有一个头节点（哨兵位）
//void dlist_init(dlist** pphead);//以参数的形式返回
dlist* dlist_init();//以返回值的形式返回

//打印数据
void dlist_print(dlist* phead);
//查找
dlist* dlist_find(dlist* phead, dlist_data_type x);
//尾插
void dlist_push_back(dlist* phead, dlist_data_type x);
//头插
void dlist_push_front(dlist* phead, dlist_data_type x);
//尾删
void dlist_pop_back(dlist* phead);
//头删
void dlist_pop_front(dlist* phead);
//在指定位置之后插入数据
void dlist_insert_back(dlist* pos, dlist_data_type x);
//删除指定位置的节点
void dlist_erase(dlist* pos);
//销毁
void dlist_destroy(dlist* phead);

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39

dlist.c:

#define  _CRT_SECURE_NO_WARNINGS

#include "dlist.h"

//申请节点
dlist* dlist_buy(dlist_data_type x)
{
	dlist* newdlist = (dlist*)malloc(sizeof(dlist));
	if (newdlist == NULL)
	{
		perror("malloc fail!");
		return 1;
	}
	newdlist->data = x;
	newdlist->next = newdlist;
	newdlist->prev = newdlist;
	return newdlist;
}

//初始化
//void dlist_init(dlist** pphead)
//{
//	assert(pphead);
//	*pphead = dlist_buy(-1);
//}

dlist* dlist_init()
{
	dlist* phead = dlist_buy(-1);
	return phead;
}

//打印数据
void dlist_print(dlist* phead)
{
	assert(phead);
	dlist* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULLn");
}

//查找
dlist* dlist_find(dlist* phead, dlist_data_type x)
{
	assert(phead);
	dlist* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

//插入操作不改变哨兵位，因此传一级指针即可
//尾插
void dlist_push_back(dlist* phead, dlist_data_type x)
{
	assert(phead);
	dlist* newdlist = dlist_buy(x);

	//新尾节点
	newdlist->prev = phead->prev;
	newdlist->next = phead;

	//旧尾节点
	phead->prev->next = newdlist;

	//头节点（哨兵位）
	phead->prev = newdlist;
}

//头插
void dlist_push_front(dlist* phead, dlist_data_type x)
{
	assert(phead);
	dlist* newdlist = dlist_buy(x);

	//新节点
	newdlist->prev = phead;
	newdlist->next = phead->next;

	//旧节点
	phead->next->prev = newdlist;

	//哨兵位
	phead->next = newdlist;
}

//尾删
void dlist_pop_back(dlist* phead)
{
	assert(phead);
	assert(phead->next != phead);//双向链表不能为空
	dlist* del = phead->prev;
	//新尾节点
	del->prev->next = phead;
	//哨兵位
	phead->prev = del->prev;
	free(del);
	del = NULL;
}

//头删
void dlist_pop_front(dlist* phead)
{
	assert(phead);
	assert(phead->next != phead);
	dlist* del = phead->next;
	del->next->prev = phead;
	phead->next = del->next;
	free(del);
	del = NULL;
}

//在指定位置之后插入数据
void dlist_insert_back(dlist* pos, dlist_data_type x)
{
	assert(pos);
	dlist* newdlist = dlist_buy(x);
	newdlist->prev = pos;
	newdlist->next = pos->next;

	pos->next->prev = newdlist;
	pos->next = newdlist;
}

//删除指定位置的节点
void dlist_erase(dlist* pos)
{
	assert(pos);
	dlist* del = pos;
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}

//销毁
void dlist_destroy(dlist* phead)
{
	assert(phead);
	dlist* pcur = phead->next;
	while (pcur != phead)
	{
		dlist* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free(pcur);
	pcur = NULL;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159

test.c:

#define  _CRT_SECURE_NO_WARNINGS

#include "dlist.h"

void test()
{
	//dlist* plist = NULL;
	//dlist_init(&plist);

	dlist* plist = dlist_init();

	//尾插
	dlist_push_back(plist, 1);
	dlist_push_back(plist, 2);
	dlist_push_back(plist, 3);
	dlist_print(plist);
	
	//头插
	//dlist_push_front(plist, 1);
	//dlist_push_front(plist, 2);
	//dlist_push_front(plist, 3);
	//dlist_print(plist);

	//尾删
	//dlist_pop_back(plist);
	//dlist_pop_back(plist);
	//dlist_pop_back(plist);
	//dlist_print(plist);

	//头删
	//dlist_pop_front(plist);
	//dlist_print(plist);
	//dlist_pop_front(plist);
	//dlist_print(plist);
	//dlist_pop_front(plist);
	//dlist_print(plist);

	//dlist* find = dlist_find(plist, 2);
	//dlist_insert_back(find, 4);
	//dlist_print(plist);

	//dlist* find = dlist_find(plist, 2);
	//dlist_erase(find);
	//find = NULL;
	//dlist_print(plist);

	dlist_destroy(plist);
	plist = NULL;//手动置空
}

int main()
{
	test();
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55

4. Comparison between sequential list and linked list

Sequence tableLinked list (doubly linked list)
Storage spaceLogically and physically continuousLogically continuous, but not necessarily physically continuous
Random AccessComplexity O(1)Complexity O(N)
Insert or delete data at any positionNeed to move data, complexity O(N)Just change the pointer to
insertDynamic sequence table, when the space is insufficient, the capacity can be expanded. The expansion itself consumes resources and is prone to space waste.No concept of capacity
Application ScenarioEfficient data storage + frequent accessFrequent insertion and deletion of data at any location
Cache utilizationhighLow

The advantages of sequential lists and linked lists complement each other and can play their respective advantages in different application scenarios.

Summarize

  • If the application scenario requires frequent search and deletion operations and can accept more memory consumption, a doubly linked list may be more appropriate.
  • If memory is limited or the efficiency of search and deletion operations is not high, a singly linked list may be more suitable.

Personal profile

I have devoted myself to the research of technology for more than 30 years. I am proficient in various languages ​​such as Java, Linux, JavaScript, PHP, CSS, etc. I have made many contributions in the field of open source. I have established a developer documentation site to share some problems in technology development for everyone to read.

my contact information

Mail