AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

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

2024-03-28 256
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【链表】还不会用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++链表
北飞的山羊
目录
相关文章
芯动大师
|
4月前
|
存储 C++
C++的list-map链表与映射表
```markdown C++ 中的`list`和`map`提供链表和映射表功能。`list`是双向链表，支持头尾插入删除（`push_front/push_back/pop_front/pop_back`），迭代器遍历及任意位置插入删除。`map`是键值对集合，自动按键排序，支持直接通过键来添加、修改和删除元素。两者均能使用范围for循环遍历，`map`的`count`函数用于统计键值出现次数。 ```
芯动大师
34 1
芯动大师
|
5月前
|
存储 C++
C++的list-map链表与映射表
这篇教程介绍了C++中`list`链表和`map`映射表的基本使用。`list`链表可通过`push_front()`、`push_back()`、`pop_front()`和`pop_back()`进行元素的添加和删除，使用迭代器遍历并支持在任意位置插入或删除元素。`map`是一个键值对的集合，元素自动按键值排序，可使用下标操作符或`insert()`函数插入元素，通过迭代器遍历并修改键值对，同时提供`count()`方法统计键值出现次数。教程中包含多个示例代码以帮助理解和学习。
芯动大师
45 2
什么时候能躺平
|
6月前
|
算法 C++
c++算法学习笔记 (13) 链表
c++算法学习笔记 (13) 链表
什么时候能躺平
39 2
1897697198172439
|
5月前
|
C++ Python
UE C++ 链表
UE C++ 链表
1897697198172439
50 0
Eternity._
|
5月前
|
C++ 容器
【C++进阶】深入STL之list：高效双向链表的使用技巧
【C++进阶】深入STL之list：高效双向链表的使用技巧
Eternity._
55 0
喵~来学编程啦
|
6月前
|
C++
有序链表的操作（底层c++实现）
有序链表的操作（底层c++实现）
喵~来学编程啦
37 0
凉开水白菜
|
6月前
|
存储 缓存 C++
C++链表常用的函数编写（增查删改）内附完整程序
C++链表常用的函数编写（增查删改）内附完整程序
凉开水白菜
105 0
泡沫o0
|
6月前
|
存储 算法 C语言
【C/C++ 链表结构】探索链表迭代器：C++实现的深入分析与优化策略
【C/C++ 链表结构】探索链表迭代器：C++实现的深入分析与优化策略
泡沫o0
129 0
泡沫o0
|
6月前
|
存储 算法 程序员
深入理解 C++ 自定义链表中实现迭代器
深入理解 C++ 自定义链表中实现迭代器
泡沫o0
87 0
数据分析螺丝钉
|
5月前
|
存储 SQL 算法
LeetCode力扣第114题：多种算法实现 将二叉树展开为链表
LeetCode力扣第114题：多种算法实现 将二叉树展开为链表
数据分析螺丝钉
39 0