21xrx.com
2025-03-30 07:56:22 Sunday
文章检索 我的文章 写文章
C++链表类的实现
2023-07-04 22:32:39 深夜i     10     0
C++ 链表类 实现

C++链表类是一种非常常用的数据结构，它可以用来存储和管理大量的数据。在这篇文章中，我们将介绍C++链表类的实现。

C++链表类的定义

链表是一种由节点组成的数据结构，每个节点包含一个数据项和指向下一个节点的指针。下面是C++链表类的基本定义：

template <class T>
class ListNode
{
public:
  T val; //节点的值
  ListNode* next; //指向下一个节点的指针
  ListNode(T x) : val(x), next(NULL) {}
};
template <class T>
class LinkedList
{
private:
  ListNode<T>* head; //链表的头节点
  int size; //链表的大小
public:
  //构造函数
  LinkedList() : head(NULL), size(0) {}
  //获取链表大小
  int getSize()
  
    return size;
  
  //判断链表是否为空
  bool isEmpty()
  
    return size == 0;
  
  //在链表头部插入一个节点
  void addFirst(T val)
  {
    ListNode<T>* newNode = new ListNode<T>(val);
    newNode->next = head;
    head = newNode;
    size++;
  }
  //在链表尾部插入一个节点
  void addLast(T val)
  {
    if (head == NULL)
    {
      addFirst(val);
      return;
    }
    ListNode<T>* cur = head;
    while (cur->next != NULL)
    
      cur = cur->next;
    
    ListNode<T>* newNode = new ListNode<T>(val);
    cur->next = newNode;
    size++;
  }
  //插入一个节点到指定位置
  void add(int index, T val)
  {
    if (index < 0 || index > size)
    
      throw "Index out of range";
    
    if (index == 0)
    {
      addFirst(val);
      return;
    }
    if (index == size)
    {
      addLast(val);
      return;
    }
    ListNode<T>* cur = head;
    for (int i = 0; i < index - 1; i++)
    
      cur = cur->next;
    
    ListNode<T>* newNode = new ListNode<T>(val);
    newNode->next = cur->next;
    cur->next = newNode;
    size++;
  }
  //删除链表头节点
  void removeFirst()
  {
    if (head == NULL)
    
      throw "Empty list";
    
    ListNode<T>* temp = head;
    head = head->next;
    delete temp;
    size--;
  }
  //删除链表尾节点
  void removeLast()
  {
    if (head == NULL)
    
      throw "Empty list";
    
    if (size == 1)
    {
      removeFirst();
      return;
    }
    ListNode<T>* cur = head;
    while (cur->next->next != NULL)
    
      cur = cur->next;
    
    ListNode<T>* temp = cur->next;
    cur->next = NULL;
    delete temp;
    size--;
  }
  //删除指定位置的节点
  void remove(int index)
  {
    if (index < 0 || index >= size)
    
      throw "Index out of range";
    
    if (index == 0)
    {
      removeFirst();
      return;
    }
    if (index == size - 1)
    {
      removeLast();
      return;
    }
    ListNode<T>* cur = head;
    for (int i = 0; i < index - 1; i++)
    
      cur = cur->next;
    
    ListNode<T>* temp = cur->next;
    cur->next = temp->next;
    delete temp;
    size--;
  }
  //获取指定位置的节点值
  T get(int index)
  {
    if (index < 0 || index >= size)
    
      throw "Index out of range";
    
    ListNode<T>* cur = head;
    for (int i = 0; i < index; i++)
    
      cur = cur->next;
    
    return cur->val;
  }
  //设置指定位置的节点值
  void set(int index, T val)
  {
    if (index < 0 || index >= size)
    
      throw "Index out of range";
    
    ListNode<T>* cur = head;
    for (int i = 0; i < index; i++)
    
      cur = cur->next;
    
    cur->val = val;
  }
};

C++链表类的使用

使用C++链表类非常简单，只需要按照下面的步骤进行操作：

LinkedList<int> list; //创建一个链表
list.addFirst(1); //在链表头部插入一个节点
list.addLast(2); //在链表尾部插入一个节点
list.add(1, 3); //在指定位置插入一个节点
list.removeFirst(); //删除链表头节点
list.removeLast(); //删除链表尾节点
list.remove(1); //删除指定位置的节点
int val = list.get(1); //获取指定位置的节点值
list.set(1, 4); //设置指定位置的节点值

C++链表类的优点

C++链表类有很多优点，其中最重要的就是它的动态性。与静态数组相比，链表可以动态地增加或删除节点，这使得它在存储和管理大量数据时非常有用。此外，C++链表类的实现也非常简单，易于学习和使用，因此它在软件开发中被广泛应用。

总结

C++链表类是一种非常实用的数据结构，它可以用来存储和管理大量的数据。本文通过介绍C++链表类的实现，让读者更好地理解链表的定义和使用方法。在使用C++链表类时，需要注意链表的指针操作，确保在正确的位置插入或删除节点，以确保程序的正确性和稳定性。

  
  

评论区

请求出错了