迹忆客 专注技术分享

本文将首先讨论链表数据结构的概念以及使用它的合适场景。 然后，我们将讨论使用 C++ 的单链表和单链表的复制构造函数的紧凑实现。

C++ 链表数据结构

链表数据结构的主要优点是能够将数据存储在不连续的内存位置。 它是由节点组成的线性数据结构，其中每个节点存储数据项（密钥和相关卫星数据）以及对下一个节点的引用。

头指针指向该数据结构中的第一个节点； 因此，它有时被称为头节点。 单链表的一些经典实现也有一个指向列表最后一个节点的尾指针。

例如，下图显示了没有尾指针的链表概念的示例描述。

链表有三种类型：

1. 单链表或简单链表

   它是一个简单的链表，也称为单向链表，在其中我们只能向前移动。 每个节点存储数据项和下一个节点的引用。

2. 双向链表

   它是一个链表，我们可以在其中向前和向后移动。 双向链表的每个节点都由数据项、下一个节点的引用和前一个节点的引用组成。

   它非常适合执行/重做状态场景，包括网络浏览器的下一页和上一个导航。

3. 循环链表

   它与单向链表几乎相同，只是链表最后一个节点中的下一个指针始终指向第一个节点。 这会创建一个圆圈； 因此，它被称为循环链表。

   它通常在循环队列管理系统中很方便。

单链表的示例代码

让我们看一下以下单链表的 C++ 实现：

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
};
class LinkedList{
  public:
  Node * head;

  LinkedList()
  {
      head=nullptr;
  }
  void addNewItem(int data)
  {
      Node * temp=new Node();
      temp->data = data;
      temp->next = head;
      head = temp;

  }
  void display()
  {
      Node * temp=head;
      while (temp!=nullptr)
      {
          cout<<temp->data<<",";
          temp=temp->next;
      }
      cout<<endl;
  }
};
int main() {
    LinkedList list;
    list.addNewItem(5);
    list.addNewItem(10);
    list.addNewItem(15);
    list.display();
    return 0;
}

上面的代码由以下几个类组成：

1. 一个 Node 类有两个成员变量：data 和 Node 类指针 next。 data变量用于存储元素的值，next变量用于存储下一个元素的引用。
2. 一个类LinkedList有一个Node类型的成员变量head用于存储链表的第一个元素，还有一个构造函数LinkedList()，以及两个成员函数addNewItem和display()。 LinkedList() 构造函数用 null 值初始化头部。

addNewItem() 方法用于在链表的前面添加一个新元素。 我们也可以将此函数命名为AddToFront 或push。

display() 方法显示链接列表元素。

C++ 单链表的复制构造函数

以下是单链表的复制构造函数的代码。

LinkedList( const LinkedList &obj )
{
    if (obj.head!=nullptr)
    {
        this->head=new Node;
        this->head->data=obj.head->data;
        Node* temp= obj.head->next;
        Node* temp2=this->head;
        while(temp!=nullptr)
        {
            Node * newNode=new Node; ////
            newNode->data=temp->data;////    creating new node
            newNode->next=temp->next;////
            temp2->next=newNode;
            temp2=temp2->next;
            temp=temp->next;
        }
    }
    else
    {
        head=nullptr;
    }
}

上面的代码显示了单链表复制构造函数，它接受一个链表对象 const LinkedList &obj 作为参数，并将接收到的链表中的所有数据复制到调用链表中。

由于链表使用Node类型指针，因此我们必须为深拷贝定义拷贝构造函数。 如果未提供复制构造函数的实现，将创建浅复制。

调用复制构造函数

考虑 main() 函数的以下代码：

int main() {

    LinkedList list; // Declaring a List
    list.addNewItem(5);
    list.addNewItem(10);
    list.addNewItem(15);
    cout<<"The content of List 1 are: ";
    list.display();

    LinkedList list2 (list); //Declaring a list2 with the copy constructor
    cout<<"The content of List 2 are: ";
    list2.display();
    return 0;
}

上面的代码中，使用LinkedList列表创建了一个LinkedList类型的对象列表； 陈述。 之后，我们使用 list.addNewItem( ) 方法将三个值插入到列表中。

创建了另一个 LinkedList 类型的 list2 对象，我们在声明时将第一个列表对象作为参数传递给调用复制构造函数。 两个对象的 display() 方法在列表中显示相同的数据项。

输出: