单链表的局限：
单链表的缺点：逆序访问单链表中的元素耗时大。（时间复杂度：O²）
双向链表的定义
第0个节点【a1】的pre指针为NULL，要注意
插入操作：
删除操作：
初步实现双链表 代码：
插入代码中要注意：
注意：第0个元素的pre指针为NULL
插入的是空双链表中的 第一个元素,示意图：
插入的为最后一个元素：
main.c
//双链表
#include "DLinkList.h"
struct Value
{
DLinkListNode header;
int v;
};
int main() {
int i;
DLinkList* list = DLinkList_Create();
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;
DLinkList_Insert(list, &v1, DLinkList_Length(list));
DLinkList_Insert(list, &v2, DLinkList_Length(list));
DLinkList_Insert(list, &v3, DLinkList_Length(list));
DLinkList_Insert(list, &v4, DLinkList_Length(list));
DLinkList_Insert(list, &v5, DLinkList_Length(list));
for ( i = 0; i < DLinkList_Length(list); i++)
{
struct Value* 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);
for (i = 0; i < DLinkList_Length(list); i++)
{
struct Value* pv = (struct Value*)DLinkList_Get(list, i);
printf("%d\n", pv->v);
}
DLinkList_Destory(list);
}
DLinkList.h
#pragma once
#pragma once
#pragma once
#include <stdio.h>
typedef void DLinkList;
//定义包含指针next的结构体
typedef struct _tag_DLinkListNode DLinkListNode;
typedef struct _tag_DLinkListNode
{
DLinkListNode* next;
DLinkListNode* pre;
};
/*
该方法用于创建并且返回一个空的线性表
*/
DLinkList* DLinkList_Create();
/*
该方法用于销毁一个线性表DLinkList
*/
void DLinkList_Destory(DLinkList* list);
/*
该方法用于将一个线性表DLinkList中的所有元素清空
使得线性表回到创建时的初始状态
*/
void DLinkList_Clear(DLinkList* list);
/*
该方法用于返回一个线性表DLinkList中的所有元素个数
*/
int DLinkList_Length(DLinkList* list);
int DLinkList_Capacity(DLinkList* list);
/*
该方法用于向一个线性表DLinkList的pos位置处插入新元素node
返回值为1表示插入成功，0表示插入失败
*/
int DLinkList_Insert(DLinkList* list, DLinkListNode* node, int pos);
/*
该方法用于获取一个线性表DLinkList的pos位置处的元素
返回值为pos位置处的元素，NULL表示获取失败
*/
DLinkListNode* DLinkList_Get(DLinkList* list, int pos);
/*
该方法用于删除一个线性表DLinkList的pos位置处的元素
返回值为被删除的元素，NULL表示删除失败
*/
DLinkListNode* DLinkList_Delete(DLinkList* list, int pos);
DLinkList.c
#include "DLinkList.h"
typedef struct _tag_DLinkList
{
DLinkListNode header;//头指针
int length;//单链表的长度
}TDLinkList; //类型：既代表头结点，又代表整个单链表
DLinkList* DLinkList_Create() {
TDLinkList* ret = (TDLinkList*)malloc(sizeof(TDLinkList));
if (ret) {
ret->length = 0;
ret->header.next = NULL;
ret->header.pre = NULL;
}
}
void DLinkList_Destory(DLinkList* list) {
free(list);
}
void DLinkList_Clear(DLinkList* list) {
((TDLinkList*)list)->length = 0;
((TDLinkList*)list)->header.next = NULL;
((TDLinkList*)list)->header.pre = NULL;
}
int DLinkList_Length(DLinkList* list) {
return ((TDLinkList*)list)->length;
}
int DLinkList_Insert(DLinkList* list, DLinkListNode* node, int pos) {
TDLinkList* tll = (TDLinkList*)list;
int i = 0;
int ret = -1;
ret = (tll != NULL) && (pos >= 0) && (node != NULL);
if (ret) {
DLinkListNode* current = (DLinkListNode*)tll;
DLinkListNode* next = NULL;
//移动current指针到pos位置
for (i = 0; (i < pos) && (current->next != NULL); i++)
{
current = current->next;
}
next = current->next; //
//关键
current->next = node;//插入的步骤
node->next = next;
if (next) {
next->pre = node;
}
node->pre = current;
//个人认为这个判定条件不对：如果链表原来长度为5，现在要插入第0个位置【即链表第一个节点】，此if的代码不会被执行，
//那么第一个节点的pre指针就不能被赋值为NULL，导致问题
if (tll->length == 0) {
node->pre = NULL;
}
tll->length++;
}
return ret;
}
DLinkListNode* DLinkList_Get(DLinkList* list, int pos) {
TDLinkList* tll = (TDLinkList*)list;
DLinkListNode* ret = NULL;
int i = 0;
if ((tll != NULL) && (pos >= 0) && pos < tll->length) {
DLinkListNode* current = (DLinkListNode*)tll;
for (i = 0; i < pos; i++)
{
current = current->next;
}
ret = current->next;
}
return ret;
}
DLinkListNode* DLinkList_Delete(DLinkList* list, int pos) {
TDLinkList* tll = (TDLinkList*)list;
DLinkListNode* ret = NULL;
int i = 0;
if ((tll != NULL) && (pos >= 0) && pos < tll->length) {
DLinkListNode* current = (DLinkListNode*)tll;
DLinkListNode* next = NULL;
for (i = 0; i < pos; i++)
{
current = current->next;
}
ret = current->next;
next = ret->next;
current->next = next;//删除的步骤
if (next) {
next->pre = current;
if (current == (DLinkListNode*)tll) { //如果删除的是第一个元素
next->pre = NULL;
}
}
tll->length--;
}
return ret;
}
最终的代码：
添加“游标”操作
DLinkList.h
#pragma once
#pragma once
#pragma once
#include <stdio.h>
typedef void DLinkList;
//定义包含指针next的结构体
typedef struct _tag_DLinkListNode DLinkListNode;
typedef struct _tag_DLinkListNode
{
DLinkListNode* next;
DLinkListNode* pre;
};
/*
该方法用于创建并且返回一个空的线性表
*/
DLinkList* DLinkList_Create();
/*
该方法用于销毁一个线性表DLinkList
*/
void DLinkList_Destory(DLinkList* list);
/*
该方法用于将一个线性表DLinkList中的所有元素清空
使得线性表回到创建时的初始状态
*/
void DLinkList_Clear(DLinkList* list);
/*
该方法用于返回一个线性表DLinkList中的所有元素个数
*/
int DLinkList_Length(DLinkList* list);
int DLinkList_Capacity(DLinkList* list);
/*
该方法用于向一个线性表DLinkList的pos位置处插入新元素node
返回值为1表示插入成功，0表示插入失败
*/
int DLinkList_Insert(DLinkList* list, DLinkListNode* node, int pos);
/*
该方法用于获取一个线性表DLinkList的pos位置处的元素
返回值为pos位置处的元素，NULL表示获取失败
*/
DLinkListNode* DLinkList_Get(DLinkList* list, int pos);
/*
该方法用于删除一个线性表DLinkList的pos位置处的元素
返回值为被删除的元素，NULL表示删除失败
*/
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);
DLinkList.c
#include "DLinkList.h"
typedef struct _tag_DLinkList
{
DLinkListNode header;//头指针
DLinkListNode* slider; //头结点处添加“游标”
int length;//单链表的长度
}TDLinkList; //类型：既代表头结点，又代表整个单链表
DLinkList* DLinkList_Create() {
TDLinkList* ret = (TDLinkList*)malloc(sizeof(TDLinkList));
if (ret) {
ret->length = 0;
ret->header.next = NULL;
ret->header.pre = NULL;
ret->slider = NULL;
}
}
void DLinkList_Destory(DLinkList* list) {
free(list);
}
void DLinkList_Clear(DLinkList* list) {
((TDLinkList*)list)->length = 0;
((TDLinkList*)list)->header.next = NULL;
((TDLinkList*)list)->header.pre = NULL;
((TDLinkList*)list)->slider = NULL;
}
int DLinkList_Length(DLinkList* list) {
return ((TDLinkList*)list)->length;
}
int DLinkList_Insert(DLinkList* list, DLinkListNode* node, int pos) {
TDLinkList* tll = (TDLinkList*)list;
int i = 0;
int ret = -1;
ret = (tll != NULL) && (pos >= 0) && (node != NULL);
if (ret) {
DLinkListNode* current = (DLinkListNode*)tll;
DLinkListNode* next = NULL;
//移动current指针到pos位置
for (i = 0; (i < pos) && (current->next != NULL); i++)
{
current = current->next;
}
next = current->next; //
//关键
current->next = node;//插入的步骤
node->next = next;
if (next) {
next->pre = node;
}
node->pre = current;
//个人认为这个判定条件不对：如果链表原来长度为5，现在要插入第0个位置【即链表第一个节点】，此if的代码不会被执行，
//那么第一个节点的pre指针就不能被赋值为NULL，导致问题
if (tll->length == 0) {
node->pre = NULL;
tll->slider = node; //游标默认指向第一个元素
}
tll->length++;
}
return ret;
}
DLinkListNode* DLinkList_Get(DLinkList* list, int pos) {
TDLinkList* tll = (TDLinkList*)list;
DLinkListNode* ret = NULL;
int i = 0;
if ((tll != NULL) && (pos >= 0) && pos < tll->length) {
DLinkListNode* current = (DLinkListNode*)tll;
for (i = 0; i < pos; i++)
{
current = current->next;
}
ret = current->next;
}
return ret;
}
DLinkListNode* DLinkList_Delete(DLinkList* list, int pos) {
TDLinkList* tll = (TDLinkList*)list;
DLinkListNode* ret = NULL;
int i = 0;
if ((tll != NULL) && (pos >= 0) && pos < tll->length) {
DLinkListNode* current = (DLinkListNode*)tll;
DLinkListNode* next = NULL;
for (i = 0; i < pos; i++)
{
current = current->next;
}
ret = current->next;
next = ret->next;
current->next = next;//删除的步骤
if (next) {
next->pre = current;
if (current == (DLinkListNode*)tll) { //如果删除的是第一个元素
next->pre = NULL;
}
}
if (tll->slider == ret) {
tll->slider = next; //当前删除的节点恰好是游标所在的节点，那么游标移动到下一个节点
}
tll->length--;
}
return ret;
}
DLinkListNode* DLinkList_DeleteNode(DLinkList* list, DLinkListNode* node) {
TDLinkList* tdll = (TDLinkList*)list;
DLinkListNode* ret = NULL;
int i = 0;
if (tdll) {
DLinkListNode* current = (DLinkListNode*)tdll;
for ( i = 0; i < tdll->length; i++)
{
if (current->next == node) {
ret = current->next;
break;
}
current = current->next;
}
if(ret){
DLinkList_Delete(list, i);
}
}
return ret;
}
DLinkListNode* DLinkList_Reset(DLinkList* list) {
TDLinkList* sList = (TDLinkList*)list;
DLinkListNode* ret = NULL;
if (sList) {
sList->slider = sList->header.next;
ret = sList->slider;
}
return ret;
}
DLinkListNode* DLinkList_Current(DLinkList* list) {
TDLinkList* sList = (TDLinkList*)list;
DLinkListNode* ret = NULL;
if (sList) {
ret = sList->slider;
}
return ret;
}
DLinkListNode* DLinkList_Next(DLinkList* list) {
TDLinkList* sList = (TDLinkList*)list;
DLinkListNode* ret = NULL;
if (sList && sList->slider) {
ret = sList->slider;
sList->slider = ret->next;
}
return ret;//?此处的返回值对吗？
}
DLinkListNode* DLinkList_Pre(DLinkList* list) {
TDLinkList* sList = (TDLinkList*)list;
DLinkListNode* ret = NULL;
if (sList && sList->slider) {
ret = sList->slider;
sList->slider = ret->pre;
}
return ret;//?此处的返回值对吗？
}
main.c文章来源：https://www.toymoban.com/news/detail-783683.html
//双链表
#include "DLinkList.h"
struct Value
{
DLinkListNode header;
int v;
};
int main() {
int i;
DLinkList* list = DLinkList_Create();
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;
DLinkList_Insert(list, &v1, DLinkList_Length(list));
DLinkList_Insert(list, &v2, DLinkList_Length(list));
DLinkList_Insert(list, &v3, DLinkList_Length(list));
DLinkList_Insert(list, &v4, DLinkList_Length(list));
DLinkList_Insert(list, &v5, DLinkList_Length(list));
for ( i = 0; i < DLinkList_Length(list); i++)
{
struct Value* 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);
for (i = 0; i < DLinkList_Length(list); i++)
{
struct Value* pv = (struct Value*)DLinkList_Next(list); //此处遍历分析：时间复杂度确实减低了！
printf("%d\n", pv->v);
}
printf("\n");
DLinkList_Reset(list);
DLinkList_Next(list);
struct Value* pv = (struct Value*)DLinkList_Current(list);
printf("%d\n", pv->v);
printf("\n");
DLinkList_DeleteNode(list, pv);
pv = (struct Value*)DLinkList_Current(list);
printf("%d\n\n", pv->v);
DLinkList_Pre(list);
pv = (struct Value*)DLinkList_Current(list);
printf("%d\n\n", pv->v);
printf("%d\n", DLinkList_Length(list));
DLinkList_Destory(list);
}
文章来源地址https://www.toymoban.com/news/detail-783683.html
到了这里，关于11 双向链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
