利用C++实现双链表基本接口示例代码
时间：2020-10-03 10:14:02|栏目：C代码|点击： 次
链表
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，链表比较方便插入和删除操作。
本文主要给大家介绍了关于C++实现双链表基本接口的相关内容，分享出来供大家参考学习，话不多说，来一起看看详细的介绍吧。
首先先简单通过图示区分单链表和双链表的结构差异：
单链表的基本接口实现可参考：单链表简单实现
接下来就是双链表的基本接口实现：
#include <iostream>
#include <assert.h>
using namespace std;
typedef int DataType;
struct ListNode
{
ListNode* _next;
ListNode* _prev;
DataType _data;
ListNode(DataType x)
:_next(NULL)
, _prev(NULL)
, _data(x)
{}
};
typedef ListNode Node;
class List
{
public:
List()
:_head(NULL)
,_tail(NULL)
{}
List(const List& l)
:_head(NULL)
,_tail(NULL)
{
Copy(l);
}
void Copy(const List& l)
{
Node* cur = l._head;
while (cur)
{
PushBack(cur->_data);
cur = cur->_next;
}
}
List& operator=(const List& l)
{
Destory();
Copy(l);
return *this;
}
~List()
{
Destory();
}
void Destory()
{
if (_head)
{
Node* cur = _head;
while (_head)
{
cur = _head;
_head = _head->_next;
delete cur;
}
_head = _tail = NULL;
}
}
void PushBack(DataType x)
{
if (_head == NULL)
{
Node* tmp = new Node(x);
tmp->_next = tmp->_prev = NULL;
_head = _tail = tmp;
}
else
{
Node* tmp = new Node(x);
_tail->_next = tmp;
tmp->_prev = _tail;
_tail = tmp;
}
}
void PopBack()
{
if (_head == NULL)
{
return;
}
else if (_head->_next == NULL)
{
delete _head;
_head = _tail = NULL;
}
else
{
Node* tmp = _tail;
_tail = _tail->_prev;
_tail->_next = NULL;
delete tmp;
}
}
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 = _head->_prev;
}
}
void PopFront()
{
if (_head == NULL)
{
return;
}
else if (_head->_next == NULL)
{
delete _head;
_head = _tail = NULL;
}
else
{
Node* tmp = _head;
_head = _head->_next;
delete tmp;
_head->_prev = NULL;
}
}
Node* Find(DataType x)
{
Node* cur = _head;
while (cur)
{
if (cur->_data == x)
return cur;
cur = cur->_next;
}
return NULL;
}
// 在pos的前面插入x
void Insert(Node* pos, DataType x)
{
assert(pos);
if ((pos == 0) || (pos->_prev == NULL))
{
PushFront(x);
}
else
{
Node* font = pos->_prev;
Node* tmp = new Node(x);
tmp->_prev = font;
tmp->_next = pos;
font->_next = tmp;
pos->_prev = tmp;
}
}
//删除pos位置的元素
void Erase(Node* pos)
{
assert(pos);
if ((pos == 0) || (pos->_prev == NULL))
{
PopFront();
}
else if (pos->_next == NULL)
{
PopBack();
}
else
{
Node* font = pos->_prev;
Node* last = pos->_next;
font->_next = last;
last->_prev = font;
delete pos;
}
}
//逆序整个双链表
void Reverse()
{
Node* cur = _head;
while (cur)
{
swap(cur->_next,cur->_prev);
cur = cur->_prev;
}
swap(_head, _tail);
}
void Print()
{
Node* cur = _head;
while (cur)
{
cout << cur->_data << "->";
cur = cur->_next;
}
cout << "NULL" << endl;
}
private:
Node* _head;
Node* _tail;
};
注：在一些操作实现时，一定要要考虑清楚各种情况，再进行情况的分类尽量提高代码的复用程度。
总结
