C++中链表的创建与操作 |21xrx.com

C++中链表的创建与操作

2023-07-03 16:57:44 深夜i 7 0

C++ 链表创建操作节点

链表是一种常用的数据结构，C++语言中也有对应的链表类供开发者使用。链表类的定义大致如下：

template <typename T>
class LinkedList{
public:
  //节点类的定义
  class Node{
    public:
      T data;
      Node* next;
      Node(T data)
        this->data = data;
        this->next = nullptr;
      
  };
  Node* head = nullptr;
  int size = 0;
  //列表的操作函数
  void insert(int pos, T data);
  void remove(int pos);
  T get(int pos);
  void print();
};

可以看到，链表类主要由节点类（Node）和链表类（LinkedList）两部分构成，其中“链表类”封装了一些常见的链表操作，如插入、删除、获取、打印链表等。下面我们一起来了解一下如何使用链表类进行操作。

一、链表的创建

链表类中的节点类（Node）是链表中基本的单位，链表类通过对这些节点进行管理，实现了链表的创建和操作。链表的创建主要分为两种方式，一种是从头部开始逐个插入节点，一种是直接将一整组数据插入到链表中（也称为尾插法）。

1、从头部开始逐个插入节点

首先需要创建一个指向链表头部的指针（例如下面的head），它指向的是第一个节点的位置。然后通过不断地创建新的节点，将它们插入到链表中。

LinkedList<int>* list = new LinkedList<int>(); //创建一个空链表
LinkedList<int>::Node* head = new LinkedList<int>::Node(1); //创建第一个节点
list->head = head; //指定头节点
list->size = 1; //链表的长度加1
LinkedList<int>::Node* node1 = new LinkedList<int>::Node(2); //创建第二个节点
head->next = node1; //将第二个节点插入链表
list->size++; //链表的长度再次加1
//以此类推，插入更多的节点到链表中

2、直接将一组数据插入到链表中（尾插法）

另一种方式是先创建一个头节点，然后通过对于链表尾部的插入操作，依次将大量数据插入到链表尾部。这种方式也称为尾插法。

//定义一个数组
int arr[] = 2;
LinkedList<int>* list = new LinkedList<int>(); //创建一个空链表
list->head = new LinkedList<int>::Node(-1); //创建一个头节点
LinkedList<int>::Node* tail = list->head; //tail指向头节点
for(int i = 0; i < 5; i++){
  LinkedList<int>::Node* node = new LinkedList<int>::Node(arr[i]);
  tail->next = node; //将新节点插入到链表尾部
  tail = node; //将tail指向新的链表尾部
}
list->size = 5; //链表长度加1

二、链表的操作

创建好链表之后，就可以对链表进行各种操作了，例如获取链表中第k个节点、删除链表中指定位置的节点、插入新节点到链表中等等。下面我们一起来了解一下链表的常见操作。

1、获取链表中第k个节点（从1开始）

T get(int pos){
  if(pos < 1 || pos > size)
    throw runtime_error("Index out of range!");
  LinkedList<T>::Node* temp = head;
  for(int i = 1; i <= pos; i++)
    temp = temp->next;
  
  return temp->data;
}

上面的函数中，参数pos就是第k个节点的位置（从1开始），返回值为该节点保存的数据。首先对于pos的值进行了有效性校验，防止越界访问。然后通过一个循环，找到第k个节点，最后返回该节点保存的数据即可。

2、删除链表中指定的位置（从1开始）或数据

void remove(int pos){
  if(pos < 1 || pos > size)
    throw runtime_error("Index out of range!");
  LinkedList<T>::Node* temp = head;
  for(int i = 1; i < pos; i++)
    temp = temp->next;
  
  LinkedList<T>::Node* target = temp->next;
  temp->next = target->next;
  delete target;
  size--;
}
void remove(T data){
  LinkedList<T>::Node* temp = head;
  while(temp->next != nullptr){
    if(temp->next->data == data){
      LinkedList<T>::Node* target = temp->next;
      temp->next = target->next;
      delete target;
      size--;
      return;
    }
    temp = temp->next;
  }
}

上面的两个函数都用来删除链表中的节点，一个是根据位置进行删除，一个是根据具体的数据进行删除。首先对于pos的值或data的值进行了有效性校验，然后通过循环找到要删除的节点的位置。删除节点的过程中，只需要将前一个节点连接到后一个节点即可，同时注意将删除节点的内存空间释放，最后链表长度减1。

3、在链表中插入新节点

void insert(int pos, T data){
  if(pos < 1 || pos > size+1)
    throw runtime_error("Index out of range!");
  LinkedList<T>::Node* temp = head;
  for(int i = 1; i < pos; i++)
    temp = temp->next;
  
  LinkedList<T>::Node* node = new LinkedList<T>::Node(data);
  node->next = temp->next;
  temp->next = node;
  size++;
}

上面的函数中，pos表示要插入的位置，data表示新节点的数据。首先对于pos的值进行了有效性校验，确定了要插入的位置。插入节点的过程中，需要先将新节点的next指向后面的节点，然后将前一个节点的next指向新节点即可，最后将链表长度加1。

4、打印链表

void print(){
  LinkedList<T>::Node* temp = head;
  while(temp->next != nullptr)
    cout << temp->next->data << " ";
    temp = temp->next;
  
  cout << endl;
}

最后还可以添加一个打印链表的函数，用来展示当前链表的数据情况。这个函数很简单，只需要遍历整个链表，将每个节点的数据依次输出即可。

上一篇: idea打包java可执行jar包

下一篇: C++利用While循环编写九九乘法表

评论区

相似文章