初学数据结构，按自己的想法写的双向链表，还有很多不足，希望各位能指出。
双向循环链表
双向链表
template<class T>
class Node
{
private:
Node<T>* next;
Node<T>* pre;
T ELEM = 0;
public:
Node() {}
~Node() {}
template<class T>
friend class dblinklist;
friend ostream& operator<<(ostream& os, dblinklist<T>& dbl);
};
dblinklist类的成员函数使用了Node类的私有成员，所以声明为友元类，要加template
dblinklist类只有长度成员和head指针：在构造时赋值为0，每次插入结点时++，删除结点时- -，dblinklist类不保存结点类，只保存一个结点的地址，该结点保存用来检索多结点构成链表的首地址和尾地址。
template<class T>
class dblinklist {
private:
Node<T>* head;
int len;
public:
dblinklist();
~dblinklist();
dblinklist<T>& insert(int k, const T& x);
dblinklist<T>& deletebyindex(int k, T& x);
dblinklist<T>& deletebykey(const T& x, T& y);
int find(const T& x);
bool isempty();
bool modify(int k,const T &x);
friend ostream& operator<<(ostream& os, dblinklist<T>& dbl)
{
Node<T>* ptem = dbl.head->pre;
int len = dbl.len;
os << "----"<<endl;
for (int i = 0; i < len; i++)
{
os << ptem->ELEM << endl;
ptem = ptem->next;
}
os << "----"<<endl;
return os;
}
};
dblinkt的数据成员为长度和类型指向Node的指针，在此将其命名head。
其他人的双链表实现为建立两个指向Node的指针，分别取名为first和end，在这里，在链表构造函数中让head指向new开辟的一个内存空间，该内存模型即为Node类的模型，其中有一个数据域，我们不适用他也就不管他，还有两个链接域，可以当做first和end使用，即head->pre就是first，head->next就是end。
template<class T>
dblinklist<T>::dblinklist()
{
head = new Node<T>();
head->next = nullptr;
head->pre = nullptr;
len = 0;
}
在<<重载函数中使用了dblinklist类的私有成员head，所以要在dblinklist类中将<<重载函数声明为友元；使用了Node类的next和pre和ELEM成员，所以在Node类中也将其声明为友元。
先将ptem指向head，在前移指向链表的第一个成员，然后在for循环中一边打印ptem指向的elem一边将ptem后移。
在<<重载函数中加上----以便直观区分不同的链表。
template<class T>
dblinklist<T>::~dblinklist()
{
T x;
for (int i =1; i < len + 1; i++)
deletebyindex(i, x);
cout << "析构" << endl;
}
在使用完dblinklist类后，遍历链表，在每个位置调用按位置删除函数以释放每个Node所占的空间。
template<class T>
dblinklist<T>& dblinklist<T>::insert(int k, const T& x)
{
if (k<1 || k>len + 1)
cout << "插入下标越界";
else
{
Node<T>* pt = new Node<T>();
Node<T>* ptemp = head;
if (head->next == nullptr)
{
head->next = pt;
head->pre = pt;
}
else
{
if (k == 1)
{
pt->next = head->pre;
head->pre->pre = pt;
head->pre = pt;
}
if (k == len + 1)
{
pt->pre = head->next;
head->next->next = pt;
head->next = pt;
}
if (k > 1 && k < len + 1)
{
ptemp = ptemp->pre;
for (int i = 1; i < k - 1; i++)
ptemp = ptemp->next;
pt->next = ptemp->next;
ptemp->next->pre = pt;
ptemp->next = pt;
pt->pre = ptemp;
}
}
pt->ELEM = x;
len++;
}
return *this;
}
该链表支持从空链表时插入，将头插尾插和中间插和空链表时插入都统一为一个insert函数，由图可知四种插入和的具体行为都不同，故将其分类讨论。
在完成链接域的重构后将x放入pt的数据域即可。
template<class T>
dblinklist<T>& dblinklist<T>::deletebyindex(int k, T& x)
{
if (k < 1 || k >len)
cout << "删除越界";
else
{
if(k==1)
{
Node<T>* ptem = head->pre;
x = head->pre->ELEM;
head->pre = head->pre->next;
delete ptem;
}
if(k==len)
{
Node<T>* ptem = head->next;
x = head->next->ELEM;
head->next = head->next->pre;
delete ptem;
}
if (k > 1 && k < len )
{
Node<T>* ptem = head->pre;
for (int i = 1; i < k; i++)
ptem = ptem->next;
x = ptem->ELEM;
ptem->pre->next = ptem->next;
ptem->next->pre = ptem->pre;
delete ptem;
}
len--;
}
return *this;
}
根据索引删除时同样要分类讨论。
Node* ptem = head->pre;
该句很重要，要删哪个结点把ptem指向哪，若指向前一个元素（Node* ptem = head；），在delete时使用delete ptem->next，由于ptem也指向头结点，该删除会删除头结点的next。
其他功能如下：
template<class T>
int dblinklist<T>::find(const T&x)
{
if (head->next == nullptr)
{
cout << "没找到" << endl;
return 0;
}
else
{
Node<T>* ptem = head->pre;
for (int i = 1; i < len; i++)
{
if (ptem->ELEM == x)
return i;
ptem = ptem->next;
}
}
}
template<class T>
dblinklist<T>& dblinklist<T>::deletebykey(const T& x, T& y)
{
int k = find(x);
deletebyindex(k, y);
return *this;
}
template<class T>
bool dblinklist<T>::isempty()
{
return(head->next == nullptr);
}
template<class T>
bool dblinklist<T>::modify(int k,const T& x)
{
if (k<1 || k>len)
return false;
else{
Node<T>* ptem = head->pre;
for (int i = 1; i < k; i++)
ptem = ptem->next;
ptem->ELEM = x;
return true;
}
}
测试：
先插入5个元素并打印。
删除第二个元素，将被删的元素打印
打印5所在的位置。
将现有4个元素打印
删除元素3并打印
将第二个元素修改成之前删除的元素并打印。
#include"dblinklist.h"
using namespace std;
int main()
{
dblinklist<int>dbl;
dbl.insert(1, 1);
dbl.insert(2, 2);
dbl.insert(3, 3);
dbl.insert(4, 4);
dbl.insert(5, 5);
cout << dbl;
int x;
dbl.deletebyindex(2, x);
cout << "x?" << x << endl;
cout << dbl.find(5);
cout << dbl;
dbl.deletebykey(3, x);
cout << dbl;
dbl.modify(2, x);
cout << dbl;
}
