数据结构与算法(三) 线性表之双向链表

简介:  掌握了单链表的结构和实现方法后,再来看双向链表,其实就是在每个节点上添加一个指向其前驱节点的指针,这样就可以实现链表的双向遍历,提高了访问效率。 下面是几个方法的实现:首先依旧是节点的结构templatestruct Node{ ...

 掌握了单链表的结构和实现方法后,再来看双向链表,其实就是在每个节点上添加一个指向其前驱节点的指针,这样就可以实现链表的双向遍历,提高了访问效率。

 下面是几个方法的实现:

首先依旧是节点的结构

template<class T>
struct Node{
    T Data;
    Node<T>* Prior;
    Node<T>* Next;
};

插入函数

template<class T>
void DouLinkList<T>::ele_insert(T data, int posi)
{
    Node<T>* sign = Head;
    for(int i=1;i<posi;i++)
    {
        sign = sign->Next;
        if(sign == nullptr)
            throw"out of size";
    }
    Node<T>* p = new Node<T>;
    p->Data = data;
    p->Next = sign->Next;
    p->Prior = sign;
    sign->Next->Prior = p;
    sign->Next = p;
}
img_3e4a06911ea255e9b1e26b46e7cc4a15.png
图1 插入节点

删除函数

template<class T>
void DouLinkList<T>::ele_delete(int posi)
{
    Node<T>* sign = Head;
    for(int i=0;i<posi;i++)
    {
        sign = sign->Next;
        if(sign == nullptr)
            throw"out of size";
    }
    sign->Prior->Next = sign->Next;
    sign->Next->Prior = sign->Prior;
    delete sign;
    sign = nullptr;
}
img_8d544b10cda3de0ee336562544be2b15.png
图2 删除节点

源码链接:
DouLinkList.h
DouLinkList.cpp


上一篇:数据结构与算法(二) 线性表之单链表
下一篇:数据结构与算法(四) 常用排序算法

相关文章
|
3天前
|
存储 C语言
数据结构中的线性表链式存储介绍及其基本操作
链式存储是线性表的一种重要存储方式,它通过节点和指针的结构,实现了灵活的动态存储管理。本文介绍了单向链表的基本操作,并提供了相应的C语言代码示例。理解和掌握链表的操作对学习和应用数据结构具有重要意义。希望这篇博客能帮助你更好地理解线性表的链式存储。
14 2
|
5天前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
1天前
数据结构 链表(第7、8天)
数据结构 链表(第7、8天)
|
1天前
|
存储
数据结构——带头双向循环链表
数据结构——带头双向循环链表
|
2天前
|
算法
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
|
4天前
|
存储
初阶数据结构 带头双链表
初阶数据结构 带头双链表
7 0
|
4天前
数据结构初阶 链表的补充
数据结构初阶 链表的补充
7 0
|
4天前
|
存储
数据结构初阶 链表详解
数据结构初阶 链表详解
5 0
|
9天前
|
存储 算法
数据结构和算法学习记录——二叉树的存储结构&二叉树的递归遍历(顺序存储结构、链表存储结构、先序中序后序递归遍历)
数据结构和算法学习记录——二叉树的存储结构&二叉树的递归遍历(顺序存储结构、链表存储结构、先序中序后序递归遍历)
9 0
数据结构和算法学习记录——二叉树的存储结构&二叉树的递归遍历(顺序存储结构、链表存储结构、先序中序后序递归遍历)
|
9天前
|
存储 算法
数据结构和算法学习记录——特殊线性表之队列-队列的概念、队列结构体类型定义 、基本接口函数、初始化函数、销毁队列函数、入队列函数、判断队列是否为空、出队列函数、读取队头队尾的数据 、计算队列数据个数
数据结构和算法学习记录——特殊线性表之队列-队列的概念、队列结构体类型定义 、基本接口函数、初始化函数、销毁队列函数、入队列函数、判断队列是否为空、出队列函数、读取队头队尾的数据 、计算队列数据个数
8 0