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

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

 下面是几个方法的实现:

首先依旧是节点的结构

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;
}
数据结构与算法(三) 线性表之双向链表
图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;
}
数据结构与算法(三) 线性表之双向链表
图2 删除节点

源码链接:
DouLinkList.h
DouLinkList.cpp


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

上一篇:应用hibernate中的hql语句对日期的操作总结


下一篇:Java多线程进一步的理解之------------缓存机制