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

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

总结

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

# c # 链表接口 # 双向链表 # c语言双向链表 # C++ 双链表的基本操作(详解) # C数据结构之双链表详细示例分析 # C/C++ 双链表之逆序的实例详解 # C语言双向链表的表示与实现实例详解 # C语言实现双向链表 # C语言之双向链表详解及实例代码 # C语言数据结构双向链表的建立与基本操作 # C语言中双向链表和双向循环链表详解 # C语言数据结构双向链表简单实例 # C语言实现数据结构和双向链表操作 # C语言实现的双链表功能完整示例 # 链表 # 是一种 # 相关内容 # 给大家 # 这篇文章 # 谢谢大家 # 多说 # 复用 # 线性表 # 有疑问 # namespace # std # assert # iostream # gt # lt # typedef # ListNode # struct # DataType

返回目录在线咨询

上一篇：建站助手3.0：智能建站系统与CMS优化一键生成方案
下一篇：建站前必看：核心准备指南与优化技巧解析

您的项目需求

*请认真填写需求信息，我们会在24小时内与您取得联系。

全网整合营销服务商

利用C++实现双链表基本接口示例代码

您的项目需求