首页 前端知识 【数据结构】双向链表

【数据结构】双向链表

2024-06-01 10:06:04 前端知识 前端哥 6 852 我要收藏

在这里插入图片描述
个人主页点这里~


双向链表

  • 一、双向链表的结构
    • 1、带头双向循环列表
  • 二、实现双向链表
    • 1、ListNode.h
    • 2、ListNode.c
    • 3、test.c
    • 调试结果
  • 三、链表和顺序表的不同点

一、双向链表的结构

1、带头双向循环列表

头:指一个固定点,我们叫它哨兵位,它不存储任何数据,只是起到作为一个哨兵的作用,跟头节点的意义不同
双向链表概念图:
在这里插入图片描述
每一个节点由一个数据点和两个指针点组成,指针点一指向前面的元素,指针点二指向后边的元素

二、实现双向链表

1、ListNode.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* next; 
	struct ListNode* prev; 
	LTDataType data;
}LTNode;
//节点创建函数
LTNode* LTBuyNode(LTDataType x);
//初始化
LTNode* LTInit();
//摧毁
void LTDestroy(LTNode* phead);
//打印
void LTPrint(LTNode* phead);
//检查链表是否只有哨兵位
bool LTEmpty(LTNode* phead);
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//尾删
void LTPopBack(LTNode* phead);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//头删
void LTPopFront(LTNode* phead);
//pos节点后插入
void LTInsert(LTNode* pos, LTDataType x);
//删除pos节点
void LTErase(LTNode* pos);
//查找某个数据的位置
LTNode* LTFind(LTNode* phead, LTDataType x);

2、ListNode.c

#include "ListNode.h"

//节点创建函数
LTNode* LTBuyNode(LTDataType x)
{
    LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    if (newnode == NULL)
    {
        perror("malloc fail");
        exit(1);
    }
    newnode->data = x;
    newnode->prev = newnode->next = newnode;
    return newnode;
}

//初始化,建立哨兵位
LTNode* LTInit()
{
    LTNode* head = LTBuyNode(-1);
    return head;
}

//销毁链表
void LTDestroy(LTNode* phead)
{
    assert(phead);
    LTNode* n1 = phead->next;
    while (n1 != phead)
    {
        LTNode* n2 = n1->next;
        free(n1);
        n1 = n2;
    }//将除了哨兵位以外的所有节点销毁
    free(phead);//最后销毁哨兵位
}

//打印链表
void LTPrint(LTNode* phead)
{
    LTNode* pur = phead->next;
    while (pur != phead)
    {
        printf("%d ", pur->data);
        pur = pur->next;
    }
    printf("\n");
}

//检查链表是否只含有哨兵位
bool LTEmpty(LTNode* phead)
{
    if (phead->next == phead && phead->prev == phead)
        return 1;
    else
        return 0;
}//当只含哨兵位时,phead的next与prev指针都是指向phead的

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
    assert(phead);
    LTNode* newnode = LTBuyNode(x);
    phead->prev->next = newnode;
    newnode->prev = phead->prev;
    newnode->next = phead;
    phead->prev = newnode;//将新创建的newcode节点连接phead以及此时的phead前一个结点
}

//尾删
void LTPopBack(LTNode* phead)
{
    assert(phead && phead->next != phead);
    LTNode* del = phead->prev;
    del->prev->next = phead;
    phead->prev = del->prev;
    free(del);
}

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
    LTNode* pur = phead->next;
    LTNode* newnode = LTBuyNode(x);
    phead->next = newnode;
    newnode->prev = phead;
    newnode->next = pur;
    pur->prev = newnode;
}//头插的意义是在哨兵位和第一个有效节点之间插入节点

//头删
void LTPopFront(LTNode* phead)
{
    LTNode* pur = phead->next;
    LTNode* purr = pur->next;
    phead->next = purr;
    purr->prev = phead;
    free(pur);
}//头删的意义是删除哨兵位后边的这一个节点

//在指定位置后插
void LTInsert(LTNode* pos, LTDataType x)
{
    LTNode* pur = pos->next;
    LTNode* newnode = LTBuyNode(x);
    pos->next = newnode;
    newnode->prev = pos;
    newnode->next = pur;
    pur->prev = newnode;
}

//删除指定位置
void LTErase(LTNode* pos)
{
    LTNode* before = pos->prev;
    LTNode* after = pos->next;
    before->next = after;
    after->prev = before;
    free(pos);
}

//查找某个节点
LTNode* LTFind(LTNode* phead, LTDataType x)
{
    LTNode* pur = phead->next;
    while (pur != phead)
    {
        if (pur->data == x)
        {
            return pur;
        }
        pur = pur->next;
    }
    return NULL;
}//找到则返回该节点的地址,找不到则返回空

3、test.c

#include "ListNode.h"
void test()
{
	//测试初始化与检测哨兵位是否有效
	//LTNode* plist = LTInit();
	//printf("%d", LTEmpty(plist));
	
	//测试尾插及打印
	//LTPushBack(plist, 1);
	//LTPushBack(plist, 2);
	//LTPushBack(plist, 3);
	//LTPrint(plist);
	// 
	//测试头插
	//LTPushFront(plist, 5);
	//LTPrint(plist);
	// 
	//测试指定位置后插
	//LTInsert(plist->next->next, 8);
	// 
	// 测试尾删
	//LTPopBack(plist);
	//LTPrint(plist);
	// 
	// 测试头删
	//LTPopFront(plist);
	// 
	// 测试指定位置删
	//LTErase(plist->next->next);
	//LTPrint(plist);
	// 
	//测试查找某一位置
	//LTNode* n = LTFind(plist, 3);
	//printf("%p", n);

	//测试销毁链表
	//LTDestroy(plist);
}
int main()
{
	test();
	return 0;
}

调试结果

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

三、链表和顺序表的不同点

不同点顺序表链表
存储空间逻辑和物理上连续逻辑上连续,物理上不一定连续
随机访问支持不支持
任意位置插入或者删除元素可能需要搬移元素,效率低只需修改指针指向
插入动态顺序表,空间不够时需要扩容没有容量的概念
应用场景元素高效访问/频繁访问任意位置插入和删除频繁

今天的分享就到这里了~

在这里插入图片描述

转载请注明出处或者链接地址:https://www.qianduange.cn//article/10358.html
评论
发布的文章

npmjs官网(查询依赖包)

2024-06-07 00:06:56

npx使用及原理

2024-06-07 00:06:36

npm 包管理工具

2024-06-07 00:06:33

vue 思极地图开发

2024-06-07 00:06:28

大家推荐的文章
会员中心 联系我 留言建议 回顶部
复制成功!