掌握了单链表的结构和实现方法后,再来看双向链表,其实就是在每个节点上添加一个指向其前驱节点的指针,这样就可以实现链表的双向遍历,提高了访问效率。
下面是几个方法的实现:
首先依旧是节点的结构
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;
}
删除函数
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;
}
源码链接:
DouLinkList.h
DouLinkList.cpp
上一篇:数据结构与算法(二) 线性表之单链表
下一篇:数据结构与算法(四) 常用排序算法