利用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;
};

注：在一些操作实现时，一定要要考虑清楚各种情况，再进行情况的分类尽量提高代码的复用程度。

总结

以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作能带来一定的帮助，如果有疑问大家可以留言交流，谢谢大家对服务器之家的支持

原文链接：http://blog.csdn.net/sssssuuuuu666/article/details/75442501