最优链表&&链表与顺序表的优缺点.

🧸🧸🧸各位巨佬大家好，我是猪皮兄弟

文章目录

🚒前言

**链表有几种结构

1.单向或者双向
2.带头或者不带头
3.循环或者不循环**
这样算下来也就是八种结构

其中，最重要的就是单链表和双向带头循环链表（最优链表）
下面是双向带头循环链表的结构

typedefint LTDataType;typedefstructListNode{
    LTDataType data;structListNode* next;structListNode* prev;}LTNode;

一、⛄头文件中需要提供的相关接口

//void ListInit(LTNode**pphead);
LTNode*ListInit();voidListPrint(LTNode* phead);voidListPushFront(LTNode* phead, LTDataType x);voidListPushBack(LTNode*phead,LTDataType x);voidListPopBack(LTNode* phead);voidListPopFront(LTNode* phead);
bool ListEmpty(LTNode*phead);voidListInsert(LTNode* pos, LTDataType x);voidListErase(LTNode* pos);intListSize(LTNode* phead);voidListDestroy(LTNode*phead);

二、⛄初始化返回结构体的优势

**返回结构体更方便，在C语言中，避免了需要用二级指针去操控的问题**

LTNode*CreateListNode(LTDataType x){
    LTNode* node =(LTNode*)malloc(sizeof(LTNode));if(node ==NULL){perror("CreateListNode::malloc");exit(-1);}
    node->data = x;
    node->next =NULL;
    node->prev =NULL;return node;}//void ListInit(LTNode**pphead)//{//    *pphead = CreateListNode(-1);//    (*pphead)->next = *pphead;//    (*pphead)->prev = *pphead;//}//在初始化的时候就malloc哨兵位
LTNode*ListInit(){
    LTNode*phead =CreateListNode(-1);
    phead->next = phead;
    phead->prev = phead;return phead;}

三、⛄为什么这里只传一级指针就可以了呢？

在不带头的单链表中，是必须传二级指针的，因为我们知道，传一级指针是对传过来的参数的拷贝(&plist),所以想对第一个结点进行增添，修改和删除的话，并不会影响原结点的值，这只是临时的拷贝，那么带头了之后传一级就可以搞定呢？？

voidListPushBack(LTNode* phead, LTDataType x){assert(phead);/*LTNode* tail = phead->prev;
    LTNode* newnode = CreateListNode(x);
    newnode->next = tail->next;
    phead->prev = newnode;
    newnode->prev = tail;
    tail->next = newnode;*/ListInsert(phead, x);}

**传一级指针只是说不能改变phead指向的结构体的值，phead后面的结构体还是可以改变的，因为，虽然是临时拷贝，但是->next指向的结构体是一样的，除了phead指向的结构体外，其他的都能改变，因为后面的是准确的找到了，而不是说是临时拷贝，就因为不能通用，所以传二级指针,但当带了头之后，这个问题也就迎刃而解**

四、⛄相关代码的实现

其实，增添删除只需要完成Insert和Erase就可以了，其他的都只需要复用这两个函数

voidListPrint(LTNode* phead){assert(phead);printf("-1->");
    LTNode* cur = phead->next;while(cur!=phead){printf("%d->",cur->data);
        cur = cur->next;}printf("-1\n");}voidListPushBack(LTNode* phead, LTDataType x){assert(phead);/*LTNode* tail = phead->prev;
    LTNode* newnode = CreateListNode(x);
    newnode->next = tail->next;
    phead->prev = newnode;
    newnode->prev = tail;
    tail->next = newnode;*/ListInsert(phead, x);}voidListPushFront(LTNode* phead, LTDataType x){assert(phead);/*LTNode* newnode = CreateListNode(x);
    LTNode* head = phead->next;
    newnode -> next = head;
    head->prev = newnode;
    phead->next = newnode;
    newnode->prev = phead;*/ListInsert(phead->next, x);}

bool ListEmpty(LTNode* phead){assert(phead);return phead->next == phead;}//链表为空就有问题了voidListPopBack(LTNode* phead){assert(phead);assert(!ListEmpty(phead));//真就没事，假就报错
    LTNode* tail = phead->prev;
    LTNode* tailPrev = tail->prev;
    tailPrev->next = phead;
    phead->prev = tailPrev;free(tail);}//void ListPopFront(LTNode* phead)；//一样的思路//在pos位置之前插入xvoidListInsert(LTNode* pos, LTDataType x){assert(pos);
    LTNode* posPrev = pos->prev;
    LTNode* newnode =CreateListNode(x);
    posPrev->next = newnode;
    newnode->next = pos;
    newnode->prev = posPrev;
    pos->prev = newnode;}//删除pos位置voidListErase(LTNode* pos){assert(pos);
    LTNode* prev = pos->prev;
    LTNode* next = pos->next;free(pos);
    pos =NULL;
    prev->next = next;
    next->prev = prev;}//前面的插入删除都是O(1)，这个倒成了O(N)，不太好，所以封装成一个结构体intListSize(LTNode* phead){assert(phead);int count=0;
    LTNode* cur = phead->next;while(cur != phead){
        cur = cur->next;++count;}return count;}voidListDestroy(LTNode* phead){
    LTNode* cur = phead->next;while(cur!=phead){
        LTNode* des=cur;
        cur = cur->next;free(des);
        des =NULL;}free(phead);
    phead =NULL;}

五、⛄顺序表和链表的优缺点！！！

顺序表：
优点：
1.下标的随机访问（因为内存地址连续）
2.缓存利用率高（CPU高速缓存命中率高）
缺点：
1.头部或者中间想要增添或者删除，需要挪动数据，效率太低
2.扩容的问题
a.首先，扩容就有一定程度的消耗，realloc扩容有两种可能，一是当前位置后面的空间足够，直接扩容，这个还好，二是当前位置后面的空间不够了，需要在堆区重新找一块足够的空间来进行扩容，并把现在的数据拷贝过去，再释放掉，如果数据太大，消耗是很大很大的。
b.扩容一般是扩充1.5倍或2倍，没有被使用的空间也就造成了浪费。

链表（主要是带头双向循环）：
优点：
1.按需申请释放空间
2.插入删除的时间内复杂度都是O(1);
缺点：
1.不支持下标的随机访问，因为空间不连续
2.缓存利用率低（CPU高速缓存命中率低）

从中可以看出，链表和顺序表是相辅相成的

六、⛄真心流露

    😶‍🌫️😶‍🌫️😶‍🌫️。**创作不易，如果看到这里，觉得有什么帮助的话，还请多多支持**。