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

简介:  掌握了单链表的结构和实现方法后,再来看双向链表,其实就是在每个节点上添加一个指向其前驱节点的指针,这样就可以实现链表的双向遍历,提高了访问效率。 下面是几个方法的实现:首先依旧是节点的结构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天前
【数据结构OJ题】合并两个有序链表
力扣题目——合并两个有序链表
21 8
【数据结构OJ题】合并两个有序链表
|
5天前
【数据结构OJ题】移除链表元素
力扣题目——移除链表元素
10 2
【数据结构OJ题】移除链表元素
|
5天前
【数据结构OJ题】链表中倒数第k个结点
牛客题目——链表中倒数第k个结点
9 1
【数据结构OJ题】链表中倒数第k个结点
|
5天前
|
存储 DataX C语言
【数据结构】双链表
数据结构中的双链表
14 1
【数据结构】双链表
|
2天前
【数据结构OJ题】链表分割
牛客题目——链表分割
3 0
【数据结构OJ题】链表分割
|
3天前
【数据结构OJ题】链表的回文结构
牛客题目——链表的回文结构
5 0
【数据结构OJ题】链表的回文结构
|
5天前
【数据结构OJ题】链表的中间结点
力扣题目——链表的中间结点
9 0
【数据结构OJ题】链表的中间结点
|
5天前
【数据结构OJ题】反转链表
力扣题目——反转链表
10 0
【数据结构OJ题】反转链表
|
18天前
|
算法 Java
Java数据结构与算法:双向链表
Java数据结构与算法:双向链表
|
1月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表