当前位置： 首页 > news >正文

【数据结构】双向链表

news 来源：原创 2024/11/17 7:53:48

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;
}

相关文章：

  • 高级seo是什么职位/seo外链软件
  • 镇江市网站建设/友链交换有什么作用
  • 国家建设部人才交流中心网站/游戏推广员拉人技巧
  • wordpress审批流/网络营销策划怎么写
  • 快速知彼网络网站建设/成都seo技术经理
  • vsftpd wordpress/win优化大师官网
  • 为什么书呆子不受欢迎-《黑客与画家》
  • “链引擎”（PBC）计划 | 太保集团长安链应用展示
  • 滑动列表中使用粒子特效层级问题
  • maven常见面试题
  • ASUS X415安装系统找不到硬盘解决办法
  • PHP MySQL 创建数据库
  • Linux--线程互斥与同步--0112 13
  • 基于域控的SSO单点登录
  • PyCharm调用远程Python解释器
  • 汇编【王爽】实验3、4
  • 【AcWing寒假每日一题2023】Day14——如此编码
  • C/C++ 调用规则