备案控制台
探索云世界
开发者社区 开发与运维 文章 正文

【链表】还不会用C++实现链表？一文教会你各种链表的实现

2024-03-28 38
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【链表】还不会用C++实现链表？一文教会你各种链表的实现

本文将用C++语言来实现数据结构中的无头单链表，带头循环链表，以及带头循环双向链表等链表结构（带头单链表与后两种链表的结构相似，实现起来比后两种更简单，读者阅读完本文即可自行实现）

一、无头单链表的实现

无头单链表在头插时需要改变头指针的位置，具体代码实现如下：

//无头单链表
#include <iostream>
#include <assert.h>
using namespace std;
template <class T>
//先定义链表中的节点
struct SListNode
{
  T data;
  SListNode* next;
  SListNode(T x)
  {
    this->data = x;
    this->next = nullptr;
  }
};
template <class T>
class SList
{
private:
  //链表初始化后链表中就有一个节点
  SListNode<T>* head;
  
public:
  SList(T x)
  {
    this->head = new SListNode<T>(x);
  }
  ~SList()
  {
    SListNode<T>* cur = head;
    while (cur)
    {
      SListNode<T>* next = cur->next;
      delete cur;
      cur = next;
    }
  }
  // 动态申请一个节点
  SListNode<T>* BuySListNode(T x);
  // 单链表打印
  void SListPrint();
  // 单链表尾插
  void SListPushBack(T x);
  // 单链表的头插
  void SListPushFront(T x);
  // 单链表的尾删
  void SListPopBack();
  // 单链表头删
  void SListPopFront();
  // 单链表查找
  SListNode<T>* SListFind(T x);
  // 单链表在pos位置之后插入x
  void SListInsertAfter(SListNode<T>* pos, T x);
  // 单链表删除pos位置之后的值
  void SListEraseAfter(SListNode<T>* pos);
};
template <class T>
SListNode<T>* SList<T>:: BuySListNode(T x)
{
  SListNode<T>* tmp = new SListNode<T>(x);
  tmp->next = nullptr;
  return tmp;
}
template <class T>
void SList<T>::SListPrint()
{
  SListNode<T>* cur =head;
  while (cur)
  {
    cout << cur->data << "->";
    cur = cur->next;
  }
  cout << "NULL" << endl;
}
template <class T>
void SList<T>::SListPushBack(T x)
{
  SListNode<T>* cur = head;
  while (cur->next)
  {
    cur = cur->next;
  }
  SListNode<T>* newnode = BuySListNode(x);
  cur->next = newnode;//连接
}
template <class T>
void SList<T>::SListPushFront(T x)
{
  SListNode<T>* newnode = BuySListNode(x);
  newnode->next = head;
  head = newnode;
}
template <class T>
void SList<T>::SListPopBack()
{
  assert(head);//头结点为空就不能继续删除了
  SListNode<T>* tail = head;
  //链表中只有一个节点就只能删除头结点
  if (tail->next == nullptr)
  {
    delete head;
  }
  else
  {
    while (tail->next->next != NULL)
    {
      tail = tail->next;
    }
    delete tail->next;
    tail->next = nullptr;
  }
}
template <class T>
void SList<T>::SListPopFront()
{
  assert(head);
  SListNode<T>* cur = head->next;
  delete head;
  head = cur;
}
template <class T>
SListNode<T>* SList<T>::SListFind(T x)
{
  assert(head);
  SListNode<T>* cur = head;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return nullptr;
}
template <class T>
void SList<T>::SListInsertAfter(SListNode<T>* pos, T x)
{
  assert(pos);
  SListNode<T>* newnode = BuySListNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
}
template <class T>
void SList<T>::SListEraseAfter(SListNode<T>* pos)
{
  assert(pos->next && pos);
  SListNode<T>* cur = pos->next;
  pos->next = pos->next->next;
  delete cur;
}
int main()
{
  SList<int> cur(1);
  cur.SListPushBack(2);
  cur.SListPushBack(3);
  cur.SListPushBack(4);
  cur.SListPushBack(5);
  cur.SListPushBack(6);
  cur.SListPrint();
  cur.SListPopFront();
  cur.SListPrint();
  cur.SListPopBack();
  cur.SListPrint();
  SListNode<int>* p1 = cur.SListFind(2);
  cur.SListInsertAfter(p1, 20);
  cur.SListPrint();
  cur.SListEraseAfter(p1);
  cur.SListPrint();
  
  return 0;
}

二、带头循环链表的实现

带头意味着链表中会一直存在着一个头结点，无论链表的插入还是删除都是对头结点后面的节点进行的操作。头插的节点也是直接连接在头结点的下一个结点，不会改变头结点。循环意味着尾节点的next指针指向头节点，就像是形成了一个环一样。

具体实现代码如下：

#include <iostream>
#include <assert.h>
using namespace std;
template <class T>
struct Node
{
  T data;
  struct Node* next;
  Node()
  {
    this->data = 0;
    this->next = nullptr;
  }
  Node(T data)
  {
    this->data = data;
    this->next = nullptr;
  }
};
template <class T>
class SList
{
private:
  Node<T>* head;
  Node<T>* tail;
public:
  SList()
  {
    this->head = new Node<T>();
    this->tail = head;
  }
  ~SList()
  {
    Node<T>* p = head;
    Node<T>* q = head;
    while (p != tail)
    {
      q = p->next;
      delete p;
      p = q;
    }
    delete tail;
  }
  
  // 动态申请一个节点
  Node<T>* BuySListNode(T x);
  // 单链表打印
  void SListPrint();
  // 单链表尾插
  void SListPushBack(T x);
  // 单链表的头插
  void SListPushFront(T x);
  // 单链表的尾删
  void SListPopBack();
  // 单链表头删
  void SListPopFront();
  // 单链表查找
  Node<T>* SListFind( T x);
  // 单链表在pos位置之后插入x
  void SListInsertAfter(Node<T>* pos, T x);
  // 单链表删除pos位置之后的值
  void SListEraseAfter(Node<T>* pos);
};
template <class T>
Node<T>* SList<T>::BuySListNode(T x)
{
  Node<T>* tmp = new Node<T>;
  tmp->data = x;
  tmp->next = nullptr;
  return tmp;
}
template <class T>
void SList<T>::SListPrint()
{
  assert(head->next);//保证头节点后还有结点才打印，不然报错
  Node<T>* cur = head->next;
  while (cur != head)
  {
    cout << cur->data << "->";
    cur = cur->next;
  }
  cout << "NULL" << endl;
}
template <class T>
void SList<T>::SListPushBack(T x)
{
  Node<T>* newnode = BuySListNode(x);
  tail->next = newnode;
  tail = newnode;
  tail->next = head;//尾节点的next指向头节点
}
template <class T>
void SList<T>::SListPushFront(T x)
{
  Node<T>* newnode = BuySListNode(x);
  if (head == tail)
  {
    head->next = newnode;
    tail = newnode;
    tail->next = head;
  }
  else
  {
    newnode->next = head->next;
    head->next = newnode;
  }
}
template <class T>
void SList<T>::SListPopBack()
{
  assert(head->next);
  Node<T>* cur = head;
  while (cur->next != tail)
  {
    cur = cur->next;
  }
  delete tail;
  tail = cur;
  tail->next = head;
}
template <class T>
void SList<T>::SListPopFront()
{
  assert(head->next);
  Node<T>* cur = head->next;
  if (head->next == tail)
  {
    delete tail;
    tail = head;
  }
  else
  {
    head->next = cur->next;
    delete cur;
  }
}
template <class T>
Node<T>* SList<T>::SListFind(T x)
{
  assert(head->next);
  Node<T>* cur = head->next;
  while (cur != head)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return nullptr;
}
template <class T>
void SList<T>::SListInsertAfter(Node<T>* pos, T x)
{
  assert(pos);
  if (pos->next == head)
  {
    SListPushBack(x);
  }
  else if(pos == head)
  {
    SListPushFront(x);
  }
  else
  {
    Node<T>* newnode = BuySListNode(x);
    newnode->next = pos->next;
    pos->next = newnode;
  }
}
template <class T>
void SList<T>::SListEraseAfter(Node<T>* pos)
{
  assert(pos);
  //尾节点后的头节点不能删
  if (pos->next == head)
  {
    exit(-1);
  }
  else if (pos == head)
  {
    SListPopFront();
  }
  else
  {
    Node<T>* cur = pos->next;
    pos->next = pos->next->next;
    delete cur;
  }
}
int main()
{
  SList<int> SL1;
  SL1.SListPushBack(1);
  SL1.SListPushBack(2);
  SL1.SListPushBack(3);
  SL1.SListPushBack(4);
  SL1.SListPushBack(5);
  SL1.SListPrint();
  SL1.SListPushFront(10);
  SL1.SListPrint();
  SL1.SListPopFront();
  SL1.SListPrint();
  SL1.SListPopBack();
  SL1.SListPrint();
  Node<int>* cur = SL1.SListFind(2);
  SL1.SListInsertAfter(cur, 20);
  SL1.SListPrint();
  SL1.SListEraseAfter(cur);
  SL1.SListPrint();
  return 0;
}

三、带头双向循环链表的实现

具体实现思路与带头循环链表大同小异，只是在节点中需要增加一个指向前一个节点的指针。

具体实现代码如下：

#include <iostream>
#include <assert.h>
using namespace std;
template <class T>
struct Node
{
  T data;
  struct Node* prev;//指向前一个节点的指针
  struct Node* next;
  Node()
  {
    this->data = 0;
    this->prev = nullptr;
    this->next = nullptr;
  }
  Node(T data)
  {
    this->data = data;
    this->prev = nullptr;
    this->next = nullptr;
  }
};
template <class T>
class SList
{
private:
  Node<T>* head;//头节点
  Node<T>* tail;//尾节点
public:
  SList()
  {
    this->head = new Node<T>();
    head->next = nullptr;
    head->prev = nullptr;
    this->tail = head;
  }
  ~SList()
  {
    Node<T>* p = head;
    Node<T>* q = head;
    while (p != tail)
    {
      q = p->next;
      delete p;
      p = q;
    }
    delete tail;
  }
  Node<T>* getHead()
  {
    return this->head;
  }
  // 动态申请一个节点
  Node<T>* BuySListNode(T x);
  // 单链表打印
  void SListPrint();
  // 单链表尾插
  void SListPushBack(T x);
  // 单链表的头插
  void SListPushFront(T x);
  // 单链表的尾删
  void SListPopBack();
  // 单链表头删
  void SListPopFront();
  // 单链表查找
  Node<T>* SListFind(T x);
  // 单链表在pos位置之后插入x
  void SListInsertAfter(Node<T>* pos, T x);
  // 单链表删除pos位置之后的值
  void SListEraseAfter(Node<T>* pos);
};
template <class T>
Node<T>* SList<T>::BuySListNode(T x)
{
  Node<T>* tmp = new Node<T>;
  tmp->data = x;
  tmp->prev = nullptr;
  tmp->next = nullptr;
  return tmp;
}
template <class T>
void SList<T>::SListPrint()
{
  assert(head->next);
  Node<T>* cur = head->next;
  while (cur != head)
  {
    cout << cur->data << "<->";
    cur = cur->next;
  }
  cout << endl;
}
template <class T>
void SList<T>::SListPushBack(T x)
{
  Node<T>* newnode = BuySListNode(x);
  tail->next = newnode;
  newnode->prev = tail;
  tail = newnode;
  tail->next = head;
  head->prev = tail;
}
template <class T>
void SList<T>::SListPushFront(T x)
{
  Node<T>* newnode = BuySListNode(x);
  if (head == tail)//头节点后没有节点
  {
    head->next = newnode;
    newnode->prev = head;
    tail = newnode;
    tail->next = head;
    head->prev = tail;
  }
  else
  {
    newnode->next = head->next;
    newnode->prev = head;
    head->next = newnode;
  }
}
template <class T>
void SList<T>::SListPopBack()
{
  assert(head->next);
  Node<T>* cur = tail->prev;
  head->prev = tail->prev;
  delete tail;
  tail = cur;
  tail->next = head;
  
}
template <class T>
void SList<T>::SListPopFront()
{
  assert(head->next);//只剩头节点不删
  Node<T>* cur = head->next;
  if (head->next == tail)//头节点后只有一个节点
  {
    delete tail;
    tail = head;
    head->next = head;
    head->prev = head;
  }
  else
  {
    head->next = cur->next;
    cur->next->prev = head;
    delete cur;
  }
}
template <class T>
Node<T>* SList<T>::SListFind(T x)
{
  assert(head->next);
  Node<T>* cur = head->next;
  while (cur != head)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return nullptr;
}
template <class T>
void SList<T>::SListInsertAfter(Node<T>* pos, T x)
{
  assert(pos);
  if (pos->next == head)
  {
    SListPushBack(x);
  }
  else if (pos == head)
  {
    SListPushFront(x);
  }
  else
  {
    Node<T>* newnode = BuySListNode(x);
    newnode->next = pos->next;
    newnode->prev = pos;
    pos->next = newnode;
  }
}
template <class T>
void SList<T>::SListEraseAfter(Node<T>* pos)
{
  assert(pos);
  if (pos->next == head)//尾节点后的头节点不删
  {
    exit(-1);
  }
  else if (pos == head)
  {
    SListPopFront();
  }
  else
  {
    Node<T>* cur = pos->next;
    pos->next = pos->next->next;
    pos->next->prev = pos;
    delete cur;
  }
}
int main()
{
  //SListNode<int>* head = new SListNode<int>;
  SList<int> SL1;
  SL1.SListPushBack(1);
  SL1.SListPushBack(2);
  SL1.SListPushBack(3);
  SL1.SListPushBack(4);
  SL1.SListPushBack(5);
  SL1.SListPrint();
  SL1.SListPushFront(10);
  SL1.SListPrint();
  SL1.SListPopFront();
  SL1.SListPrint();
  SL1.SListPopBack();
  SL1.SListPrint();
  Node<int>* cur = SL1.SListFind(2);
  SL1.SListInsertAfter(cur, 20);
  SL1.SListPrint();
  SL1.SListEraseAfter(cur);
  SL1.SListPrint();
  return 0;
}
文章标签：
C++
关键词：
C++链表
链表c++
北飞的山羊
目录
相关文章
凉开水白菜
|
25天前
|
存储 缓存 C++
C++链表常用的函数编写（增查删改）内附完整程序
C++链表常用的函数编写（增查删改）内附完整程序
凉开水白菜
24 0
泡沫o0
|
1月前
|
存储 算法 C语言
【C/C++ 链表结构】探索链表迭代器：C++实现的深入分析与优化策略
【C/C++ 链表结构】探索链表迭代器：C++实现的深入分析与优化策略
泡沫o0
38 0
泡沫o0
|
1月前
|
存储 缓存 算法
C++链表解析：从基础原理到高级应用，全面掌握链表的使用
C++链表解析：从基础原理到高级应用，全面掌握链表的使用
泡沫o0
51 0
醋溜马桶圈
|
2月前
|
C语言 C++
【c++】用c++实现带头双向循环链表
【c++】用c++实现带头双向循环链表
醋溜马桶圈
23 1
红目香薰
|
2月前
|
Java C++ Python
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-456 求链表各节点的平均值(C++解法)
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-456 求链表各节点的平均值(C++解法)
红目香薰
29 0
SarPro
|
2月前
|
存储 算法 C++
【数据结构】链表—C/C++实现
【数据结构】链表—C/C++实现
SarPro
60 1
HannYang
|
3月前
|
Python Linux Ubuntu
Linux系统部署Python语言开发运行环境
Linux系统部署Python语言开发运行环境
HannYang
93 0
Linux系统部署Python语言开发运行环境
HannYang
|
3月前
|
Go Unix 开发者
Go语言time库，时间和日期相关的操作方法
Go语言time库，时间和日期相关的操作方法
HannYang
51 0
Go语言time库，时间和日期相关的操作方法
HannYang
|
3月前
|
Java Go C++
Golang每日一练(leetDay0092) 丑数 I\II Ugly Number i\ii
Golang每日一练(leetDay0092) 丑数 I\II Ugly Number i\ii
HannYang
40 0
Golang每日一练(leetDay0092) 丑数 I\II Ugly Number i\ii
HannYang
|
3月前
|
C++ Java Go
Java每日一练(20230425) 乘积最大子数组、插入区间、删除有序数组中的重复项II
Java每日一练(20230425) 乘积最大子数组、插入区间、删除有序数组中的重复项II
HannYang
31 0
Java每日一练(20230425) 乘积最大子数组、插入区间、删除有序数组中的重复项II

热门文章

最新文章

  • 1
    从Proto到C++：探索Protocol Buffers的强大转换机制
  • 2
    【C/C++ 数据库 sqlite3】SQLite C语言API返回值深入解析
  • 3
    【C++ 职业方向】C++ 职业方向探索：工作职责、编程技能与MBTI人格匹配
  • 4
    拓扑排序解析：计算机与数学的交汇点以及C++ 实现
  • 5
    【C++ 可调用对象的应用】C++设计模式与现代编程技巧：深入可调用对象的世界
  • 6
    【C/C++ 性能优化】提高C++程序的缓存命中率以优化性能
  • 7
    【C++ 软件设计思路】学习C++中如何生成唯一标识符：从UUID到自定义规则
  • 8
    C++代码复用策略及与标准兼容性指南
  • 9
    【C++ 基本知识】现代C++内存管理：探究std::make_系列函数的力量
  • 10
    深入对比：Qt 的 QFile/QFileInfo 和与 C++17 Filesystem 和标准文件流 的细节剖析
  • 1
    【数据结构算法（二）】链表总结
    15
  • 2
    《剑指offer》——合并两个排序的链表
    19
  • 3
    《剑指offer》——从尾到头打印链表
    21
  • 4
    【移除链表元素】LeetCode第203题讲解
    19
  • 5
    【顺序表和链表的对比】
    15
  • 6
    【双向链表】数据结构双向链表的实现
    21
  • 7
    【单链表】数据结构单链表的实现
    34
  • 8
    实现单链表的基本操作（力扣、牛客刷题的基础&笔试题常客）
    143
  • 9
    快慢指针该如何操作？本文带你认识快慢指针常见的三种用法及在链表中的实战
    21
  • 10
    leetcode82. 删除排序链表中的重复元素 II
    22

    • 相关课程

    更多
  • C++ 入门教程开发文档

    • 相关电子书

    更多
  • 使用C++11开发PHP7扩展
  • GPON Class C++ SFP O;T Transce
  • GPON Class C++ SFP OLT Transce
    • 下一篇
    部署LAMP环境（Alibaba Cloud Linux 3）