【数据结构】双向链表

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6

1.双向链表的结构

2.双向链表的实现

首先在VS里面的源文件建立test.c和List.c,在头文件里面建立List.h

List.h:

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int LTDateType;
typedef struct ListNode
{
    LTDateType data;
    struct ListNode* next;
    struct ListNode* prev;
}LTNode;

2.1 初始化

List.h:

LTNode* ListInit(LTNode* phead);//初始化

List.c:

#include "List.h"
LTNode* ListInit()
{
    //哨兵位头结点
    LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
    phead->next = phead;
    phead->prev = phead;
    return phead;
}

test.c

#include "List.h"
void TestList1()
{
    LTNode* plist = ListInit();
}
int main()
{
    TestList1();
    return 0;
}

2.2 打印

List.h:

void ListPrint(LTNode* phead);//打印

List.c:

void ListPrint(LTNode* phead)
{
    assert(phead);
    LTNode* cur = phead->next;
    while (cur != phead)
    {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

2.3 申请结点

List.h:

LTNode* BuyListNode(LTDateType x);//申请结点

List.c:

LTNode* BuyListNode(LTDateType x)
{
    LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    newnode->data = x;
    newnode->next = NULL;
    newnode->prev = NULL;
    return newnode;
}

2.4 尾插

List.h:

void ListPushBack(LTNode* phead, LTDateType x);//尾插

List.c:

void ListPushBack(LTNode* phead, LTDateType x)
{
    assert(phead);
    LTNode* tail = phead->prev;
    LTNode* newnode = BuyListNode(x);
    tail->next = newnode;
    newnode->prev = tail;
    phead->prev = newnode;
    newnode->next = phead;
}

test.c

#include "List.h"
void TestList1()
{
    LTNode* plist = ListInit();
    ListPushBack(plist, 1);
    ListPushBack(plist, 2);
    ListPushBack(plist, 3);
    ListPrint(plist);
}
int main()
{
    TestList1();
    return 0;
}

运行结果

2.5 尾删

List.h:

void ListPopBack(LTNode* phead);//尾删

List.c:

void ListPopBack(LTNode* phead)
{
    assert(phead);
    assert(phead->next != phead);//排除为空的情况
    LTNode* tail = phead->prev;
    phead->prev = tail->prev;
    tail->prev->next = phead;
    free(tail);
}

test.c

#include "List.h"
void TestList1()
{
    LTNode* plist = ListInit();
    ListPushBack(plist, 1);
    ListPushBack(plist, 2);
    ListPushBack(plist, 3);
    ListPrint(plist);
    ListPopBack(plist);
    ListPrint(plist);

}
int main()
{
    TestList1();
    return 0;
}

运行结果

2.6 头插

List.h:

void ListPushFront(LTNode* phead, LTDateType x);//头插

List.c:

void ListPushFront(LTNode* phead, LTDateType x)
{
    assert(phead);
    LTNode* newnode = BuyListNode(x);
    LTNode* next = phead->next;
    phead->next = newnode;
    newnode->prev = phead;
    newnode->next = next;
    next->prev = newnode;
}

test.c

#include "List.h"
void TestList1()
{
    LTNode* plist = ListInit();
    ListPushBack(plist, 1);
    ListPushBack(plist, 2);
    ListPushBack(plist, 3);
    ListPrint(plist);
    ListPopBack(plist);
    ListPrint(plist);
    ListPushFront(plist, 10);
    ListPrint(plist);

}
int main()
{
    TestList1();
    return 0;
}

运行结果

2.7 头删

List.h:

void ListPopFront(LTNode* phead);//头删

List.c:

void ListPopFront(LTNode* phead)
{
    assert(phead);
    assert(phead->next != phead);
    LTNode* next = phead->next;
    LTNode* nextNext = next->next;
    phead->next = nextNext;
    nextNext->prev = phead;
    free(next);
}

test.c

#include "List.h"
void TestList1()
{
    LTNode* plist = ListInit();
    ListPushBack(plist, 1);
    ListPushBack(plist, 2);
    ListPushBack(plist, 3);
    ListPrint(plist);
    ListPopBack(plist);
    ListPrint(plist);
    ListPushFront(plist, 10);
    ListPrint(plist);
    ListPopFront(plist);
    ListPrint(plist);
}
int main()
{
    TestList1();
    return 0;
}

运行结果

2.8 查找

List.h:

LTNode* ListFind(LTNode* phead, LTDateType x);//查找

List.c:

LTNode* ListFind(LTNode* phead, LTDateType x)
{
    assert(phead);
    LTNode* cur = phead->next;
    while (cur != phead)
    {
        if (cur->data == x)
            return cur;
        cur = cur->next;
    }
    return NULL;
}

2.9 前插

List.h:

void ListInsert(LTNode* pos, LTDateType x);//前插

List.c:

void ListInsert(LTNode* pos, LTDateType x)
{
    assert(pos);
    LTNode* posPrev = pos->prev;
    LTNode* newnode = BuyListNode(x);
    posPrev->next = newnode;
    newnode->prev = posPrev;
    newnode->next = pos;
    pos->prev = newnode;
}

test.c

#include "List.h"
void TestList1()
{
    LTNode* plist = ListInit();
    ListPushBack(plist, 1);
    ListPushBack(plist, 2);
    ListPushBack(plist, 3);
    ListPrint(plist);
    ListPopBack(plist);
    ListPrint(plist);
    ListPushFront(plist, 10);
    ListPrint(plist);
    ListPopFront(plist);
    ListPrint(plist);
    LTNode* list = ListFind(plist, 2);
    ListInsert(plist->next->next, 20);
    ListPrint(plist);
}
int main()
{
    TestList1();
    return 0;
}

运行结果

2.10 删除

List.h:

void ListErase(LTNode* pos);//删除

List.c:

void ListErase(LTNode* pos)
{
    assert(pos);
    LTNode* posPrev = pos->prev;
    LTNode* posNext = pos->next;
    posPrev->next = posNext;
    posNext->prev = posPrev;
    free(pos);
    pos = NULL;
}

test.c

#include "List.h"
void TestList1()
{
    LTNode* plist = ListInit();
    ListPushBack(plist, 1);
    ListPushBack(plist, 2);
    ListPushBack(plist, 3);
    ListPrint(plist);
    ListPopBack(plist);
    ListPrint(plist);
    ListPushFront(plist, 10);
    ListPrint(plist);
    ListPopFront(plist);
    ListPrint(plist);
    LTNode* list = ListFind(plist, 2);
    ListInsert(plist->next->next, 20);
    ListPrint(plist);
    ListErase(plist->next->next);
    ListPrint(plist);
}
int main()
{
    TestList1();
    return 0;
}

运行结果

2.11 销毁

List.h:

void ListDestroy(LTNode* phead);//销毁

List.c:

void ListDestroy(LTNode* phead)
{
    assert(phead);
    LTNode* cur = phead->next;
    while (cur != phead);
    {
        LTNode* next = cur->next;
        free(cur);
        cur = next;
    }
    free(phead);//置空放在test.c里面因为形参是实参的临时拷贝
}

3.完整代码展示

List.h:

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int LTDateType;
typedef struct ListNode
{
    LTDateType data;
    struct ListNode* next;
    struct ListNode* prev;
}LTNode;
LTNode* ListInit();//初始化
void ListPrint(LTNode* phead);//打印
LTNode* BuyListNode(LTDateType x);//申请结点 
void ListPushBack(LTNode* phead, LTDateType x);//尾插 
void ListPopBack(LTNode* phead);//尾删
void ListPushFront(LTNode* phead, LTDateType x);//头插
void ListPopFront(LTNode* phead);//头删
LTNode* ListFind(LTNode* phead, LTDateType x);//查找
void ListInsert(LTNode* pos, LTDateType x);//前插
void ListErase(LTNode* pos);//删除
void ListDestroy(LTNode* phead);//销毁

List.c:

#include "List.h"
LTNode* ListInit()
{
    //哨兵位头结点
    LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
    phead->next = phead;
    phead->prev = phead;
    return phead;
}

void ListPrint(LTNode* phead)
{
    assert(phead);
    LTNode* cur = phead->next;
    while (cur != phead)
    {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

LTNode* BuyListNode(LTDateType x)
{
    LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    newnode->data = x;
    newnode->next = NULL;
    newnode->prev = NULL;
    return newnode;
}

void ListPushBack(LTNode* phead, LTDateType x)
{
    assert(phead);
    LTNode* tail = phead->prev;
    LTNode* newnode = BuyListNode(x);
    tail->next = newnode;
    newnode->prev = tail;
    phead->prev = newnode;
    newnode->next = phead;
}

void ListPopBack(LTNode* phead)
{
    assert(phead);
    assert(phead->next != phead);//排除为空的情况
    LTNode* tail = phead->prev;
    phead->prev = tail->prev;
    tail->prev->next = phead;
    free(tail);
}

void ListPushFront(LTNode* phead, LTDateType x)
{
    assert(phead);
    LTNode* newnode = BuyListNode(x);
    LTNode* next = phead->next;
    phead->next = newnode;
    newnode->prev = phead;
    newnode->next = next;
    next->prev = newnode;
}

void ListPopFront(LTNode* phead)
{
    assert(phead);
    assert(phead->next != phead);
    LTNode* next = phead->next;
    LTNode* nextNext = next->next;
    phead->next = nextNext;
    nextNext->prev = phead;
    free(next);
}

LTNode* ListFind(LTNode* phead, LTDateType x)
{
    assert(phead);
    LTNode* cur = phead->next;
    while (cur != phead)
    {
        if (cur->data == x)
            return cur;
        cur = cur->next;
    }
    return NULL;
}

void ListInsert(LTNode* pos, LTDateType x)
{
    assert(pos);
    LTNode* posPrev = pos->prev;
    LTNode* newnode = BuyListNode(x);
    posPrev->next = newnode;
    newnode->prev = posPrev;
    newnode->next = pos;
    pos->prev = newnode;
}

void ListErase(LTNode* pos)
{
    assert(pos);
    LTNode* posPrev = pos->prev;
    LTNode* posNext = pos->next;
    posPrev->next = posNext;
    posNext->prev = posPrev;
    free(pos);
    pos = NULL;
}

void ListDestroy(LTNode* phead)
{
    assert(phead);
    LTNode* cur = phead->next;
    while (cur != phead);
    {
        LTNode* next = cur->next;
        free(cur);
        cur = next;
    }
    free(phead);//置空放在test.c里面因为形参是实参的临时拷贝
}

test.c

#include "List.h"
void TestList1()
{
    LTNode* plist = ListInit();
    ListPushBack(plist, 1);
    ListPushBack(plist, 2);
    ListPushBack(plist, 3);
    ListPrint(plist);
    ListPopBack(plist);
    ListPrint(plist);
    ListPushFront(plist, 10);
    ListPrint(plist);
    ListPopFront(plist);
    ListPrint(plist);
    LTNode* list = ListFind(plist, 2);
    ListInsert(plist->next->next, 20);
    ListPrint(plist);
    ListErase(plist->next->next);
    ListPrint(plist);
}
int main()
{
    TestList1();
    return 0;
}

4.顺序表和链表的区别

不同点

顺序表

链表

存储空间上

物理上一定连续

逻辑上连续但物理上不一定连

续

随机访问

支持O(1)

不支持O(N)

任意位置插入或者删除元

素

可能需要搬移元素效率低O(N)

只需修改指针指向

插入

动态顺序表空间不够时需要扩

容

没有容量的概念

应用场景

元素高效存储+频繁访问

任意位置插入和删除频繁

缓存利用率

高

低

备注缓存利用率参考存储体系结构以及局部原理性。

5.链表OJ题

5.1 环形链表1

给你一个链表的头节点 head 判断链表中是否有环。如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 则返回 true 。 否则返回 false 。

链接https://leetcode.cn/problems/linked-list-cycle/

bool hasCycle(struct ListNode *head) {
    struct ListNode* slow=head,*fast=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)
        {
            return true;
        }
    }
    return false;
}

5.2 环形链表2

给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。不允许修改链表。

链接https://leetcode.cn/problems/linked-list-cycle-ii/description/

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* slow=head,*fast=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)
        {
            //相遇
            struct ListNode* meet=slow;
            //公式
            while(meet!=head)
            {
                meet=meet->next;
                head=head->next;
            }
            return meet;
        }
    }
    return NULL;
}

5.3 复杂链表的复制

给你一个长度为 n 的链表每个节点包含一个额外增加的随机指针 random 该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如如果原链表中有 X 和 Y 两个节点其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y 同样有 x.random --> y 。返回复制链表的头节点。用一个由 n 个节点组成的链表来表示输入/输出中的链表。
每个节点用一个 [val, random_index] 表示
val一个表示 Node.val 的整数。
random_index随机指针指向的节点索引范围从 0 到 n-1如果不指向任何节点则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。

链接https://leetcode.cn/problems/copy-list-with-random-pointer/description/

struct Node* copyRandomList(struct Node* head) {
    //1.拷贝结点插入原结点的后面
    struct Node* cur=head;
    while(cur)
    {
        struct Node* copy=(struct Node*)malloc(sizeof(struct Node));
        copy->val=cur->val;
        //插入copy结点
        copy->next=cur->next;
        cur->next=copy;
        cur=copy->next;
    }
    //2.根据原结点处理copy结点的random
    cur=head;
    while(cur)
    {
        struct Node* copy=cur->next;
        if(cur->random==NULL)
        {
            copy->random=NULL;
        }
        else
        {
            copy->random=cur->random->next;
        }
        cur=copy->next;
    }
    struct Node* copyHead=NULL,*copyTail=NULL;
    cur=head;
    while(cur)
    {
        struct Node* copy=cur->next;
        struct Node* next=copy->next;
        if(copyTail==NULL)
        {
            copyHead=copyTail=copy;
        }
        else
        {
            copyTail->next=copy;
            copyTail=copy;
        }
        cur->next=next;
        cur=next;
    }
    return copyHead;
}
阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6
返回列表

上一篇：重新认识 tag 快照 git (项目临时添加需求，之前有分支合并，导致从节点拉分支不行了，因为没有tag快照）

下一篇：[ docker相关知识 ] 删除 docker 拉取的容器 -- 解决删除镜像报错问题

“【数据结构】双向链表” 的相关文章

R语言、01 VSCODE 配置 R 环境快速指南、4.2.1版本1年前 (2023-02-02)
如何使用 Node.js Stream API 减少服务器端内存消耗？1年前 (2023-02-02)
看我是如何用C#编写一个小于8KB的贪吃蛇游戏的1年前 (2023-02-02)
Phi的反函数1年前 (2023-02-02)
2022圣诞代码合集(圣诞树+圣诞老人)1年前 (2023-02-02)
matplotlib+cartopy+geopandas，实现专业地图可视化！1年前 (2023-02-02)
Nmap使用教程图文教程（超详细）1年前 (2023-02-02)
【Redis】分别从互斥锁与逻辑过期两个方面来解决缓存击穿问题1年前 (2023-02-02)
【强烈推荐】基于STM32的TFT-LCD各种显示实现（内容详尽含代码）1年前 (2023-02-02)
Python取出字典中的值_python字典取值1年前 (2023-02-02)

阿里云国际版