在cplusplus.com里，我们可以搜索list来查看库是如何实现双向链表的。当然，我们也可以在平时使用时包上头文件list来调用C++里的list库。在这里，我今天就不再赘述用C语言或者C++未引入模版这两种场景来向大家分享双向链表了，而是注重多类型都可以使用双向链表。也就是我们今天的主题：模版实现双向链表。
我主要实现了尾插、尾删、打印、去重、逆置等等一系列操作，而关于像Insert()、Erase()之类的操作我并没有在这里全部实现，一方面是因为之前我们反复实现过，如果你感兴趣的话，可以查看我之前的博客。另一方面，我出于较为低效不常见的原因。希望大家理解。
另外，需要说明的一点是，今天我使用的均是类内声明，类外定义的方式。
代码如下：
#include<iostream>
using namespace std;
template<class T>
struct ListNode
{
ListNode(const T& x)
:_next(NULL)
, _prev(NULL)
, _data(x)
{}
ListNode<T>* _next;
ListNode<T>* _prev;
T _data;
};
template<class T>
class List
{
public:
List()
:_head(NULL)
, _tail(NULL)
{}
List(const List<T>& l)
{
ListNode<T>* cur = l._head;
while (cur)
{
this->PushBack(cur->_data);
cur = cur->_next;
}
}
List<T>& operator=(const List<T>& l)
{
//先删除节点，再插入节点
if (&s != this)
{
ListNode<T>* pcur = _head;
while (pcur)
{
ListNode<T>* del = pcur;
pcur = pcur->_next;
delete del;
del = NULL;
}
ListNode<T>* cur = _head;
while (cur)
{
this->PushBack(cur->_data);
cur = cur->_next;
}
}
return *this;
}
~List()//一个节点一个节点的删除
{
ListNode<T>* cur = _head;
while (cur)
{
ListNode<T>* del = cur;
cur = cur->_next;
delete del;
del = NULL;
}
}
void PushBack(const T& x);
void PopBack();
void Unique();
void PrintList();
void Reverse();
int Length();
void Sort();
protected:
ListNode<T>* _head;
ListNode<T>* _tail;
};
//尾插
template<class T>
void List<T>::PushBack(const T& x)
{
//分析：分为两种情况：无节点、有节点
if (_head == NULL)
{
_head = _tail = new ListNode<T>(x);
}
else
{
ListNode<T>* cur = new ListNode<T>(x);
_tail->_next = cur;
cur->_prev = _tail;
_tail = cur;
_tail->_next = NULL;
}
}
//尾删
template<class T>
void List<T>::PopBack()
{
//分析：分为三种情况：无节点、一个节点、多个节点
if (_head == _tail)
{
if (_head == NULL)
{
return;
}
else
{
delete _head;
_head = _tail = NULL;
}
}
else
{
ListNode<T>* prev = _tail->_prev;
delete _tail;
_tail = NULL;
_tail = prev;
_tail->_next = NULL;
}
}
//去重:前提是针对已排序的有重复数据的链表
//template<class T>
//void List<T>::Unique()
//{
// //分析：分为三种情况：无节点一个节点（无需删除节点）、两个节点、两个以上节点
// if (_head == _tail)
// {
// return;
// }
// else
// {
// ListNode<T>* pcur = _head;
// ListNode<T>* pnext = _head->_next;
// if (pnext->_next == NULL) //两个节点
// {
// if (pcur->_data == pnext->_data)
// {
// delete pnext;
// pnext = NULL;
// _tail = _head = pcur;
// return;
// }
// else
// {
// return;
// }
// }
// else
// {
// //两个以上节点
// ListNode<T>* cur = _head;
// while (cur->_next)
// {
// ListNode<T>* next = cur->_next;
// ListNode<T>* nextnext = next->_next;
// if (cur->_data == next->_data)
// {
// cur->_next = nextnext;
// nextnext->_prev = cur;
// delete next;
// next = NULL;
// }
// cur = cur->_next;
// }
// }
// }
//}
//逆置
template<class T>
void List<T>::Reverse()
{
//分析：从两头开始走,交换数据（分奇数个数据和偶数个数据）
ListNode<T>* begin = _head;
ListNode<T>* end = _tail;
while (!((begin == end) || end->_next == begin))
{
swap(begin->_data, end->_data);
begin = begin->_next;
end = end->_prev;
}
}
//长度
template<class T>
int List<T>::Length()
{
ListNode<T>* cur = _head;
int count = 0;
while (cur)
{
count++;
cur = cur->_next;
}
return count;
}
//分类
//template<class T>
//void List<T>::Sort()
//{
// //使用冒泡排序,实现升序或者降序
// ListNode<T>* i = _head;
// ListNode<T>* j = _head;
// for (i = _head; i != _tail; i++)
// {
// for (j = _head->_next; j < Length() - i + 1; j++)
// {
// if (j->_data >(j + 1)->_data)
// {
// swap(j->_data, (j + 1)->_data);
// }
// }
// }
//}
//打印
template<class T>
void List<T>::PrintList()
{
ListNode<T>* cur = _head;
while (cur)
{
cout << cur->_data << "->";
cur = cur->_next;
}
cout << "NULL" << endl;
}
void Test()
{
List<int> l1;
l1.PushBack(1);
l1.PushBack(2);
l1.PushBack(2);
l1.PushBack(3);
l1.PushBack(4);
l1.PushBack(4);
l1.PushBack(5);
l1.PrintList();
l1.PopBack();
l1.PrintList();
/*l1.Unique();
l1.PrintList();*/
l1.Reverse();
l1.PrintList();
/*l1.Sort();
l1.PrintList();*/
}
int main()
{
Test();
system("pause");
return 0;
}本文出自 “C语言100-200素数” 博客，请务必保留此出处http://10740184.blog.51cto.com/10730184/1750695
【C++】模版实现双向链表的各种操作(如：逆置、去重、分类、合并)
原文：http://10740184.blog.51cto.com/10730184/1750695