双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。可以向前遍历，也可以向后遍历，双链表中还有一个尾指针。
双链表的操作比单链表要稍微复杂一些，因为删除和插入都要操控一个额外的指针，特别是在双链表的插入中指针的指向顺序是不可修改的。当然双链表可以反向查找结点优于单链表。在操作发生时必须要更新尾指针。
下面来实现双链表的各个功能：
#include<iostream>
#include<assert.h>
using namespace std;
typedef int DataType;
struct ListNode
{
DataType _data;
ListNode *_next;
ListNode *_prev;
ListNode(const DataType x)
:_data(x), _next(NULL), _prev(NULL)
{}
};
class List
{
typedef ListNode Node;
public:
List()
:_head(NULL), _tail(NULL)
{
}
void PushBack(DataType x)
{
if (_head == NULL)
{
_head = _tail = new Node(x);
}
else
{
Node* tmp = new Node(x);
_tail->_next = tmp;
tmp->_prev = _tail;
_tail = _tail->_next;
}
}
void PushFront(DataType x)
{
if (_head == NULL)
{
_head = _tail = new Node(x);
}
else
{
Node *tmp = new Node(x);
tmp->_next = _head;
_head->_prev = tmp;
_head = tmp;
}
}
void Display()
{
if (_head == NULL)
return;
else
{
Node* cur(_head);
while (cur != NULL)
{
cout << cur->_data << " ";
cur = cur->_next;
}
cout << endl;
}
}
void PopBack()
{
if (_head == NULL||_head==_tail)
{
delete _tail;
_head = _tail = NULL;
}
else
{
_tail = _tail->_prev;
delete _tail->_next;
}
}
void PopFront()
{
if (_head == NULL || _head == _tail)
{
delete _tail;
_head = _tail = NULL;
}
else
{
_head = _head->_next;
delete _head->_prev;
}
}
void Destroy()
{
if (_head == _tail)
{
delete _tail;
_head = _tail = NULL;
}
else
{
while (_head->_next != NULL)
{
_head = _head->_next;
delete _head->_prev;
}
delete _tail;
_head = _tail = NULL;
}
}
Node* Find(DataType x)
{
if (_head == NULL)
return NULL;
else
{
Node *cur(_head);
while (cur != NULL)
{
if (cur->_data == x)
{
break;
}
cur = cur->_next;
}
return cur;
}
}
void Insert(Node* pos, DataType x)
{
assert(pos);
if (pos == _head)
{
PushFront(x);
}
else
{
Node *tmp = new Node(x);
tmp->_next = pos;
pos->_prev->_next = tmp;
tmp->_prev = pos->_prev;
pos->_prev = tmp;
}
}
void Erase(Node* pos)
{
assert(pos);
if (pos == _head)
{
_head = _head->_next;
delete pos;
}
else
{
pos->_next->_prev = pos->_prev;
pos->_prev->_next = pos->_next;
delete pos;
pos = NULL;
}
}
void Reverse()//定义了一个NewHead 让其从第一个一直走到最后一个，将其再给_head
{
if (_head == _tail)
{
return;
}
else
{
ListNode* cur = _head;
ListNode* tmp = cur;
ListNode* NewHead = NULL;
while (cur)
{
tmp = cur;
cur = cur->_next;
tmp->_next = NewHead;
tmp->_prev = cur;
NewHead = tmp;
}
_head = NewHead;
}
}
private:
Node *_head;
Node *_tail;
};
void test()
{
List l1;
l1.PushBack(0);
l1.PushBack(1);
l1.PushBack(2);
l1.PushBack(3);
/*l1.PushFront(2);
l1.PushFront(1);
l1.PushFront(0);*/
/*l1.PopBack();
l1.PopBack();
l1.PopBack();*/
//l1.PopFront();
//l1.PopFront();
//l1.PopFront();
//l1.Destroy();
//l1.Find(1);
//l1.Insert(l1.Find(5), 9);
//l1.Insert(l1.Find(1), 6);
//l1.Insert(l1.Find(3), 5);
//l1.Insert(l1.Find(0), 9);
//l1.Erase(l1.Find(1));
//l1.Erase(l1.Find(10));
l1.Reverse();
l1.Display();
}
int main()
{
test();
system("pause");
return 0;
}
