【数据结构】链表超全整理~

目录

1.链表

1.1 链表的概念及结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

1.2 链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

1.2.1. 单向或者双向

1.2.2. 带头或者不带头（是否有哨兵位

哨兵位

哨兵位要malloc一个新节点，哨兵里面不要存具体的值。也不能存链表的长度，万一链表里面的数据类型是char，链表长度超过128，就会溢出。

哨兵位的存在方便头插。

1.2.3. 循环或者非循环

最常用的链表还是单向无头不循环链表和双向带头循环链表。

1. 无头单向非循环链表：

结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

1. 带头双向循环链表：

结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。

1.3单链表相关函数代码

#pragma once

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
// slist.h
typedef int SLTDateType;
typedef struct SListNode
{
    SLTDateType data;
    struct SListNode* next;
}SListNode,*PSListNode;

//SListNode* p;  
//PSListNode p;
//struct SListNode p;  等价

// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);

// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
void SListInsertAfter(SListNode* pos, SLTDateType x);

// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
void SListEraseAfter(SListNode* pos);

// 单链表的销毁
void SListDestroy(SListNode** pplist);

#define _CRT_SECURE_NO_WARNINGS

#include"slist.h"

void SListPrint(SListNode* plist)
{
    //不能断言，因为如果链表一个元素都没有，元素指向空，还是要打印
    SListNode* cur = plist;
    while (cur)
    {
        printf("%d->", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}

SListNode* BuySListNode(SLTDateType x)
{
    SListNode* p = (SListNode*)malloc(sizeof(SListNode));
    if (p == NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    p->data = x;
    p->next = NULL;
    return p;
}

void SListPushBack(SListNode** pplist, SLTDateType x)
{
    SListNode* head = *pplist;
    SListNode* tail = BuySListNode(x);
    
    //空
    if (*pplist == NULL)
    {
        *pplist = tail;
    }

    //非空
    else
    {
        while (head->next)
        {
            head = head->next;
        }

        head->next = tail;
    }
}

void SListPushFront(SListNode** pplist, SLTDateType x)
{
    assert(*pplist);

    SListNode* cur = *pplist;
    SListNode* new = BuySListNode(x);
    new->next = cur;
    *pplist = new;
}

void SListPopBack(SListNode** pplist)
{
    assert(*pplist);

    SListNode* cur = *pplist;
    //一个结点
    if (cur->next == NULL)
    {
        free(cur);
        *pplist = NULL;
    }
    //多个节点
    else
    {
        while (cur->next->next)
        {
            cur = cur->next;
        }
        free(cur->next);
        cur->next = NULL;
    }

}

void SListPopFront(SListNode** pplist)
{
    assert(*pplist);
    SListNode* cur = *pplist;
    *pplist = cur->next;
    free(cur);
    cur = NULL;
}

SListNode* SListFind(SListNode* plist, SLTDateType x)
{
    assert(plist);
    SListNode* cur = plist;
    while (cur)
    {
        if (cur->data == x)
        {
            break;
        }
        cur = cur->next;
    }
    return cur;
}

void SListInsertAfter(SListNode* pos, SLTDateType x)
{
    SListNode* p = BuySListNode(x);
    p->next = pos->next;
    pos->next = p;
}

void SListEraseAfter(SListNode* pos)
{
    SListNode* p = pos->next;
    pos->next = p->next;
    free(p);

}

void SListDestroy(SListNode** pplist)
{
    assert(*pplist);

    SListNode* cur = *pplist;
    while (cur)
    {
        SListNode* next = cur->next;
        free(cur);
        cur = next;
    }
    *pplist = NULL;
}

1.4双向带头循环链表相关函数代码

#pragma once

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

// 带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{
    LTDataType data;
    struct ListNode* next;
    struct ListNode* prev;
}ListNode;

// 创建返回链表的头结点.
ListNode* ListCreate();
ListNode* AddListnode(LTDataType x);

// 双向链表销毁
void ListDestory(ListNode* pHead);
// 双向链表打印
void ListPrint(ListNode* pHead);
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* pHead);
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* pHead);
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);

#define _CRT_SECURE_NO_WARNINGS
#include"DLClinklist.h"

// 创建返回链表的头结点.
// 哨兵位
ListNode* ListCreate()
{
    ListNode* head = (ListNode*)malloc(sizeof(ListNode));
    if (head == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    head->data = 0;
    head->next = head->prev = head;
    return head;
}

//创建节点
ListNode* AddListnode(LTDataType x)
{
    ListNode* p = (ListNode*)malloc(sizeof(ListNode));
    if (p == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    p->data = x;
    p->next = p->prev = NULL;
    return p;
}

// 双向链表销毁
void ListDestory(ListNode* pHead)
{
    assert(pHead);
    ListNode* cur = pHead;
    while (cur)
    {
        cur = cur->next;
        free(pHead);
        pHead = cur;
    }
}

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

// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
    assert(pHead);
    ListNode* newnode = AddListnode(x);
    newnode->next = pHead;
    newnode->prev = pHead->prev;
    pHead->prev->next = newnode;
    pHead->prev = newnode;
}

// 双向链表尾删
void ListPopBack(ListNode* pHead)
{
    assert(pHead);
    ListNode* tail = pHead->prev;
    tail->prev->next = pHead;
    pHead->prev = tail->prev;
    free(tail);
    tail = NULL;
}

// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
    assert(pHead);
    ListNode* newnode = AddListnode(x);
    newnode->prev = pHead;
    newnode->next = pHead->next;
    pHead->next->prev = newnode;
    pHead->next = newnode;
}

// 双向链表头删
void ListPopFront(ListNode* pHead)
{
    assert(pHead);
    ListNode* next = pHead->next->next;
    free(pHead->next);
    pHead->next = next;
    next->prev = pHead;

}

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

// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
    assert(pos);
    ListNode* ahead = pos->prev;
    ListNode* newnode = AddListnode(x);
    newnode->prev = ahead;
    newnode->next = pos;
    ahead->next = newnode;
    pos->prev = newnode;

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

4.顺序表和链表的区别

单纯的存储数据用的最多的就是顺序表和链表。

比较时使用带头双向循环链表，单链表相比于顺序表的优势不大。
不同点顺序表链表（带头双向循环链表）存储空间上物理上一定连续逻辑上连续，但物理上不一定连续随机访问支持O(1)不支持：O(N)任意位置插入或者删除元素可能需要搬移元素，效率低 O(N)只需修改指针指向插入动态顺序表，空间不够时需要扩容 没有容量的概念应用场景元素高效存储+频繁访问任意位置插入和删除频繁缓存利用率高
低

存储效率而言实际上顺序表使用更多。

双链表带头双向循环

顺序表——————————————————

优点：

1.尾插尾删效率很高。

2.顺序表可以随机访问（用下标可以直接访问)。

3.相比链表结构CPU高速缓存的命中率更高。

缺点：

1.头部和中部的插入效率低，因为要挪动数据。

2.扩容，扩容时单次的性能消耗（假如realloc异地扩容） +一定程度的空间浪费（每次扩容2倍可能用不完）。

链表：——————————————————

优点：

1.任意位置插入删除，效率都很高--O(1)（在知道这个位置指针的前提下）

2.按需申请释放空间，单次申请的效率要高一些，不存在空间浪费。

缺点：

1.不支持随机访问。

5.存储器相关知识：

CPU执行指令，不会直接访问内存:

1.先看数据在不在三级缓存，在就叫(命中)。直接访问。

2.不在(不命中)，会让数据先加载到缓存，再访问。

局部性原理:

就是你访问当前这一块数据的时候，你很有可能访问周边的数据。就比如说你访问四个字节，它不会只加载这—段，会加载一长段字节。不同的硬件不同,

堆是主存的一部分，堆是一个进程的虚拟地址空间
堆、栈都是虚拟内存，需要经过操作系统对于物理的划分，后面会用链表跟物理地址进行映射。

数据结构:
在主存里面管理数据。
缓存污染:

缓存是有限的，在每次加载的时候因为局部性原理，加载一些无效的东西，会把一些没有用的数据换出去。

你好，这里是媛仔。这篇博客真的攒了好久，终于要发布啦！!希望这篇博客对你能够有所帮助，也欢迎和我多多交流，共同进步~