双向链表的实现

双向链表的声明

``````#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int LTDataType;

typedef struct ListNode
{
struct ListNode* prev;
struct ListNode* next;
LTDataType data;
}ListNode;

//链表初始化
ListNode* ListInit();
// 创建返回链表的头结点.
ListNode* ListCreate(int x);
// 双向链表销毁
void ListDestory(ListNode** plist);
// 双向链表打印
void ListPrint(ListNode* plist);
// 双向链表尾插
void ListPushBack(ListNode* plist, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* plist);
// 双向链表头插
void ListPushFront(ListNode* plist, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* plist);
// 双向链表查找
ListNode* ListFind(ListNode* plist, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);
``````

双向链表的实现

``````#include"DSLTNode.h"
// 创建返回链表的头结点.
ListNode* ListCreate(int x)
{
ListNode *tmp = (ListNode *)malloc(sizeof(ListNode));
tmp->data = x;
tmp->next = tmp;
tmp->prev = tmp;
return tmp;
}

//链表初始化
ListNode * ListInit()
{
}
// 双向链表销毁
void ListDestory(ListNode** plist)
{
ListNode *cur = *plist;
while (cur != *plist)
{
ListNode* next = cur->next;
cur = next;
free(next);
}
free(*plist);
*plist = NULL;
}
// 双向链表打印
void ListPrint(ListNode* plist)
{
assert(plist);
ListNode *cur = plist->next;
while (cur != plist)
{
printf("%d->",cur->data);
cur = cur->next;
}
printf("NULL\n");
}
// 双向链表尾插
void ListPushBack(ListNode* plist, LTDataType x)
{
assert(plist);
ListNode *newNode = ListCreate(x);
newNode->data = x;

ListNode *listtali = plist->prev;
listtali->next = newNode;
newNode->prev = listtali;
newNode->next = plist;
plist->prev = newNode;
}
// 双向链表尾删
void ListPopBack(ListNode* plist)
{
assert(plist);
assert(plist->next != plist);
ListNode *tail = plist->prev;
ListNode *prevtail = tail->prev;
free(tail);
prevtail->next = plist;
plist->prev = prevtail;

}
// 双向链表头插
{
ListNode *newNode = ListCreate(x);

newNode->next = first;
first->prev = newNode;

}
// 双向链表头删
void ListPopFront(ListNode* plist)
{
assert(plist);
assert(plist->next != plist);

ListNode *first = plist->next;
ListNode *second = first->next;

plist->next = second;
second->prev = plist;
free(first);
}
// 双向链表查找
ListNode* ListFind(ListNode* plist, LTDataType x)
{
assert(plist);
ListNode *cur = plist->next;
while (cur != plist)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
ListNode *newNode = ListCreate(x);
ListNode *prev = pos->prev;

prev->next = newNode;
newNode->prev = prev;

newNode->next = pos;
pos->prev = newNode;
}
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
ListNode *prev = pos->prev;
ListNode *next = pos->next;

prev->next = next;
next->prev = prev;
}

``````

结点的创建

``````// 创建返回链表的头结点.
ListNode* ListCreate(int x)
{
ListNode *tmp = (ListNode *)malloc(sizeof(ListNode));
tmp->data = x;
tmp->next = tmp;
tmp->prev = tmp;
return tmp;
}
``````

头结点的创建

``````//链表初始化
ListNode * ListInit()
{
}
``````

链表的销毁

``````// 双向链表销毁
void ListDestory(ListNode** plist)
{
ListNode *cur = *plist;
while (cur != *plist)
{
ListNode* next = cur->next;
cur = next;
free(next);
}
free(*plist);
*plist = NULL;
}
``````

链表的打印

``````// 双向链表打印
void ListPrint(ListNode* plist)
{
assert(plist);
ListNode *cur = plist->next;
while (cur != plist)
{
printf("%d->",cur->data);
cur = cur->next;
}
printf("NULL\n");
}
``````

链表的尾插

``````// 双向链表尾插
void ListPushBack(ListNode* plist, LTDataType x)
{
assert(plist);
ListNode *newNode = ListCreate(x);
newNode->data = x;

ListNode *listtali = plist->prev;
listtali->next = newNode;
newNode->prev = listtali;
newNode->next = plist;
plist->prev = newNode;
}
``````

链表的尾删

``````// 双向链表尾删
void ListPopBack(ListNode* plist)
{
assert(plist);
assert(plist->next != plist);
ListNode *tail = plist->prev;
ListNode *prevtail = tail->prev;
free(tail);
prevtail->next = plist;
plist->prev = prevtail;

}
``````

链表的头插

``````// 双向链表头插
{
ListNode *newNode = ListCreate(x);

newNode->next = first;
first->prev = newNode;

}
``````

链表的头删

``````// 双向链表头删
void ListPopFront(ListNode* plist)
{
assert(plist);
assert(plist->next != plist);

ListNode *first = plist->next;
ListNode *second = first->next;

plist->next = second;
second->prev = plist;
free(first);
}
``````

查找

``````// 双向链表查找
ListNode* ListFind(ListNode* plist, LTDataType x)
{
assert(plist);
ListNode *cur = plist->next;
while (cur != plist)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
``````

指定位置前插入

``````// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
ListNode *newNode = ListCreate(x);
ListNode *prev = pos->prev;

prev->next = newNode;
newNode->prev = prev;

newNode->next = pos;
pos->prev = newNode;
}
``````

指定位置删除

``````// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
ListNode *prev = pos->prev;
ListNode *next = pos->next;

prev->next = next;
next->prev = prev;
}
``````

总结顺序表和链表(双向带头循环)

• 顺序表优点：
1、按下标进行随机访问
2、cpu高速缓存命中比较高

• 顺序表缺点：
1、空间不够需要增容，一定程度的性能消耗，有一定的空间浪费
2、头部或者中间插入删除数据，需要挪动数据，效率比较低，挪动数据的时间复杂度O(N)

• 链表表优点：
1、按需申请内存，需要存一个数据，就申请一块内存，也不浪费空间
2、任意位置插入删除不需要挪动数据，时间复杂度O(1)

• 顺序表缺点：
1、空间不够需要增容，一定程序的性能消耗
2、头部或者中间插入删除数据，需要挪动数据，效率比较低，挪动数据的时间复杂度O(N)

原文作者：IT莫扎特
原文地址: https://blog.csdn.net/m0_53421868/article/details/120615230
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。