[数据结构]——链表详解
1.什么是链表?链表的概念及结构
链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
注意:
1.链式结构在逻辑上是连续的,但在物理上不一定连续
2.现实中的结点一般都是从堆上申请出来的
3.从堆上申请的空间,是按照一定的策略来分配的,两次申请的空间可能连续,也可能不连续
2.链表的分类
实际中链表的结构非常多样,以下的情况组合起来就有8种链表结构
1.单向或者双向
2.带头或者不带头
3.循环或者非循环
虽然有这么多的链表的结构,但是我们实际中最常用的还是两种结构
1.无头单向非循环链表
2.带头双向循环链表
文章来源:https://www.toymoban.com/news/detail-709350.html
- 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
- 带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了。
3.单链表的实现(增删查改)
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SListNodeType;
typedef struct SListNode
{
SListNodeType data;
SListNodeType* next;
}SLNode;
void SLNodePrint(SLNode* phead);
SLNode* BuySLNode(SListNodeType x);
void SLNodePushFront(SLNode* pphead, SListNodeType x);
void SLNodePushBack(SLNode** pphead, SListNodeType x);
void SLNodePopBack(SLNode** pphead);
void SLNodePopFront(SLNode** pphead);
void SListDestory(SLNode** pphead);
SLNode* SListFind(SLNode* phead, SListNodeType x);
void SListInsert(SLNode** pphead, SLNode* pos, SListNodeType x);
void SListInsertAfter(SLNode* pos, SListNodeType x);
1)链表的初始化
void SLNodeInit(SLNode* phead)
{
phead->data=0;
phead->next=NULL;
}
2)动态申请一个结点
//新创建一个结构体空间,存放新输入的数据
SLNode* BuySLNode(SListNodeType x)
{
SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
3)单链表尾插
//在链表最后端插入一个数据
void SLNodePushBack(SLNode** pphead, SListNodeType x)
{
SLNode* newnode = BuySLNode(x);
/*1.整个链表为空*/
if (*pphead == NULL)
{
*pphead = newnode;
}
/*2.链表不为空*/
else
{
SLNode* cur = *pphead;
while (cur->next != NULL)
{
cur = cur->next;
}
newnode = cur->next;
}
}
4)单链表头插
//在链表最前端插入一个数据
void SLNodePushFront(SLNode** pphead, SListNodeType x)
{
assert(pphead);
SLNode* newnode=BuySLNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
5)单链表尾删
//删除链表最后端的数据
void SLNodePopBack(SLNode** pphead)
{
/*1.链表为空*/
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
/*2.链表不为空*/
else
{
SLNode* cur = *pphead;
SLNode* prev = NULL;
while (cur->next != NULL)
{
prev = cur;
cur = cur->next;
}
prev->next = NULL;
free(cur);
cur = NULL;
}
}
6)单链表头删
//删除链表最前端的数据
void SLNodePopFront(SLNode** pphead)
{
assert(pphead);
SLNode* det = *pphead;
*pphead = (*pphead)->next;
free(det);
det = NULL;
}
7)单链表查找
//在链表中查找某个数据
SLNode* SListFind(SLNode* phead, SListNodeType x)
{
SLNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
8)在单链表中某个位置前插入数据
//在pos前插入一个数据
void SListInsert(SLNode** pphead, SLNode* pos, SListNodeType x)
{
assert(pphead);
assert(pos);
if (pos == *pphead)
{
SLNodePushFront(*pphead, x);
}
else
{
SLNode* cur = *pphead;
SLNode* newnode = BuySLNode(x);
while (cur->next != pos)
{
cur = cur->next;
}
cur->next=newnode;
newnode->next = pos;
}
9)在单链表中某个位置后插入数据
// 在pos后面插入
void SListInsertAfter(SLNode* pos, SListNodeType x)
{
assert(pos);
SLNode* newnode = BuySLNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
10)销毁单链表
void SListDestory(SLNode** pphead)
{
assert(pphead);
SLNode* cur = *pphead;
while (cur != NULL)
{
SLNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
4.双向链表的实现
双向链表的原理与单链表类似,双向链表需要两个指针来链接,一个指向前面的,一个指向后面的。同时需要一个head,头链表,方便操作。
文章来源地址https://www.toymoban.com/news/detail-709350.html
#pragma once
#include<stdlib.h>
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
typedef int LTDataType;
typedef struct ListNode
{
LTDataType data;
struct ListNode* prev;
struct ListNode* next;
}ListNode;
ListNode* ListInit();
ListNode* BuyListNode(LTDataType x);
void ListPushBack(ListNode* phead, LTDataType x);
void ListPushFront(ListNode* phead, LTDataType x);
void ListNodePopBack(ListNode* phead);
void ListNodePopFront(ListNode* phead);
bool ListNodeEmpty(ListNode* phead);
size_t ListNodeSize(ListNode* phead);
void ListNodeInsert(ListNode* pos, LTDataType x);
ListNode* ListNodeFInd(ListNode* phead, LTDataType x);
void ListNodeErase(ListNode* pos);
void ListNodeDestory(ListNode* phead);
1)双向链表的初始化
ListNode* ListInit()
{
ListNode* Guard=(ListNode*)malloc(sizeof(ListNode));
if (Guard == NULL)
{
perror("malloc fail");
exit(-1);
}
Guard->next = Guard;
Guard->prev = Guard;
return Guard;
}
2)动态申请一个结点
ListNode* BuyListNode(LTDataType x)
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
3)双向链表的尾插
void ListPushBack(ListNode* phead, LTDataType x)
{
assert(phead);
ListNode* newnode = BuyListNode(x);
ListNode* tail = phead->prev;
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}
4)双向链表的头插
void ListPushFront(ListNode* phead, LTDataType x)
{
assert(phead);
ListNode* newnode = BuyListNode(x);
ListNode* cur = phead->next;
phead->next = newnode;
newnode->prev = phead;
newnode->next = cur;
cur->prev= newnode;
}
5)双向链表的尾删
void ListNodePopBack(ListNode* phead)
{
assert(phead);
assert(!ListNodeEmpty(phead));
ListNode* tail = phead->prev;
ListNode* cur = tail->prev;
cur->next = phead;
phead -> prev = cur;
free(tail);
tail = NULL;
}
6)双向链表的头删
void ListNodePopFront(ListNode* phead)
{
assert(phead);
assert(!ListNodeEmpty(phead));
ListNode* cur = phead->next;
ListNode* pe = cur->next;
phead->next = pe;
pe->prev = phead;
free(cur);
cur = NULL;
}
7)判断链表是否为空
bool ListNodeEmpty(ListNode* phead)
{
assert(phead);
return phead->next==phead;
}
8)双向链表数据的个数
size_t ListNodeSize(ListNode* phead)
{
size_t n = 0;
ListNode* cur = phead->next;
while (cur != phead)
{
++n;
cur = cur->next;
}
return n;
}
9)在双向链表查找数据
ListNode* ListNodeFInd(ListNode* phead, LTDataType x)
{
ListNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
return cur;
cur = cur->next;
}
return NULL;
}
10)在双向链表中插入一个数据
void ListNodeInsert(ListNode* pos, LTDataType x)
{
assert(pos);
ListNode* prev = pos->prev;
ListNode* newnode = BuyListNode(x);
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
}
11)在双向链表中删除一个数据
void ListNodeErase(ListNode* pos)
{
assert(pos);
ListNode* prev = pos->prev;
ListNode* next = pos->next;
prev->next = next;
next->prev = prev;
free(pos);
pos = NULL;
}
12)销毁双向链表
void ListNodeDestory(ListNode* phead)
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead)
{
ListNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
phead = NULL;
}
5.顺序表与链表的区别
不同点 | 顺序表 | 链表 |
---|---|---|
存储空间上 | 物理上一定连续 | 逻辑上连续,但物理上不一定连续 |
随机访问 | 支持O(1) | 不支持:O(N) |
任意位置插入或者删除元素 | 可能需要搬移元素,效率低O(N) | 只需要修改指针指向 |
插入 | 动态顺序表,空间不够时需要扩容 | 没有容量概念 |
应用场景 | 元素高效存储+频繁访问 | 任意位置的插入和删除 |
缓存利用率 | 高 | 低 |
到了这里,关于[数据结构]——链表详解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!