技術共有

【データ構造】 二重連結リスト

2024-07-12

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

こんにちは～！奮闘中の小さな羊です。コメントやアドバイスをいただけて光栄です。
💥💥个人主页：奮闘する子羊
💥💥所属专栏：C言語

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

目次

序文

単一リンク リストは特定のノードのアドレスを通じて一方向にのみデータにアクセスできますが、二重リンク リストはノードのアドレスを通じて両方向にデータにアクセスでき、追加、削除、確認、変更の効率が高くなります。ただし、コードの実装は単一リンク リストよりも単純です。 の点では、二重リンク リストの利点がより明らかです。

1. リンクリストの分類

連結リストは、見出し付き、見出しなし、一方向、双方向、循環型、非循環型の 8 つのタイプに分類されます。ここでは、一般的なもののみを学習します。リーダーなしの一方向非巡回リンク リストそして見出し付き双方向循環リンクリスト、 あれは単一リストそして二重リンクリスト。
二重リンクリスト:
ここに画像の説明を挿入します
実際、前の記事では、単連結リストの最初のノードをヘッド ノードと呼びましたが、これは不正確です。単連結リストにはヘッドがないため、わかりやすくするためです。二重リンクリストのみに と呼ばれるヘッドノードがあります。センチネルの位置。

  • 二重リンクリストの先頭ノードには有効なデータが格納されておらず、無効なデータが格納されています。
  • センチネルの位置は変更できません。変更できるのは方向のみです。

2. 二重リンクリストの実装

2.1 二重リンクリストノード

二重リンク リストのノードは、データと前後のノードのアドレスを格納する必要があるため、二重リンク リストのノードは次のようになります。

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 ノードの申請

単一リンク リストとは異なり、二重リンク リストには少なくとも 1 つのノードが必要です。これがヘッド ノードであり、センチネル位置とも呼ばれます。
追加、削除、確認、変更を行う前に、二重リンク リストはセンチネル ビットを初期化する必要があり、センチネル ビットには無効なデータが格納されます。

適用されたノードには、最初はそれ自体を指す 2 つのポインターがあります。。

//申请节点
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

センチネル ビットを初期化するには 2 つの方法があります。
パラメータとして返されるもの:

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

  • 1
  • 2
  • 3
  • 4
  • 5

このメソッドでは、セカンダリ ポインターを使用する必要があります。
戻り値として返されるもの:

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

  • 1
  • 2
  • 3
  • 4
  • 5

この方法の方がシンプルで理解しやすいです。

2.3 データの印刷と検索

データの印刷と検索は、単一リンク リストの場合とあまり変わらないため、詳細は説明しません。
注意が必要な唯一のことは、ループが終了する条件です。ポインタがセンチネル ビットを指したときではなく、ポインタがセンチネル ビットを指したときにループが終了します。NULL。

//打印数据
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 ヘッドプラグとテールプラグ

単一リンク リストとは異なり、二重リンク リストの追加、削除、クエリ、変更操作はセンチネル ビットを変更しないため、値による呼び出しそれでおしまい。
二重リンクリストの挿入操作には、3 つのノードの変更が必要です。変更プロセス中には、次の点に注意してください。最初に新しいノードを変更し、次に次のノードを変更し、最後に前のノードを変更します。

//插入操作不改变哨兵位，因此传一级指针即可
//尾插
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 先頭の削除と末尾の削除

削除操作の前提条件は、ノードが存在しないことです (センチネルの位置は考慮されません)、削除する前に、ノードのアドレスを保存し、二重リンク リストに再参加してから、ノードを解放します。

//尾删
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 指定した場所へのデータの挿入と削除

//在指定位置之后插入数据
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

指定した場所のデータを削除した後、この関数は値によって呼び出されるため、指定された位置でノードを解放した後、仮パラメータ ポインタを次のように設定するだけです。NULL、実際のパラメータ ポインタはまだこの場所を指しているため、関数呼び出しが終了した後、実際のパラメータ ポインタを設定する必要があります。NULL。

2.7 二重リンクリストを破棄する

二重リンク リストの破棄の終了条件は、トラバーサル ポインタがヘッド ノードを指しているときにループから抜け出すことです。最後に、センチネルの位置を個別に解放する必要があります、二重リンクリストの破棄関数呼び出しが完了した後、センチネルビットを指すポインタも設定する必要があります。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

3. 二重リンクリストの完全なコード

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. シーケンスリストとリンクリストの比較

シーケンステーブルリンクリスト（ダブルリンクリスト）
収納スペースについて論理的かつ物理的に連続している論理的には連続的ですが、物理的には必ずしも連続的ではありません
ランダムアクセス複雑さ O(1)複雑さ O(N)
任意の場所にデータを挿入または削除するデータを移動する必要があるが、複雑さは O(N)ポインタを次のように変更するだけです
入れるダイナミックシーケンステーブルは、容量が足りない場合に拡張することができ、拡張自体が消費され、容量を無駄にしやすい。容量という概念がない
アプリケーションシナリオ効率的なデータストレージ + 頻繁なアクセス任意の場所でデータを頻繁に挿入および削除する
キャッシュの使用率高い低い

シーケンス リストとリンク リストには補完的な利点があり、さまざまなアプリケーション シナリオでそれぞれの利点を発揮できます。

要約する

  • アプリケーション シナリオで頻繁な検索と削除の操作が必要であり、より多くのメモリ消費を許容できる場合は、二重リンク リストの方が適している可能性があります。
  • メモリが限られている場合、または検索および削除操作の効率が高くない場合は、単一リンク リストの方が適している可能性があります。

個人プロフィール

彼は 30 年以上テクノロジーの研究に専念しており、java、linux、javascript、php、css などのさまざまな言語に堪能であり、オープンソース分野で多くの貢献を行っています。将来の参考のために技術開発におけるいくつかの問題を共有する開発者ドキュメント ステーション。

私の連絡先情報

郵便