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

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

 下面是几个方法的实现：

首先依旧是节点的结构

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

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