21xrx.com
2024-11-22 07:06:42 Friday
登录
文章检索 我的文章 写文章
C++数据结构之单链表简介
2023-06-29 15:49:24 深夜i     --     --
C++ 数据结构 单链表 简介 链表实现

单链表是一种常见的数据结构,它是由若干个节点构成的,每个节点都包含一个数据元素和指向下一个节点的指针。单链表的特点在于它只能从头节点开始遍历,因此访问节点的时间复杂度为O(n),其中n为链表的长度。但是,插入和删除节点的时间复杂度仅仅为O(1),所以单链表的优点在于插入和删除操作非常高效。

在C++中,实现单链表需要定义一个节点结构体,结构体包含了节点的数据元素和指向下一个节点的指针。代码如下:


struct Node {

  int val; //数据元素

  Node* next; //指向下一个节点的指针

};

接下来,我们需要定义一个单链表类,类中包括单链表的头节点和一些基本操作,如插入和删除等。代码如下:


class LinkedList {

private:

  Node* head; //头节点

public:

  LinkedList() //构造函数

    head = NULL; //初始化头节点为空

  

  void insert(int val) { //插入操作

    Node* node = new Node; //创建一个新的节点

    node->val = val; //设置节点的数据元素

    node->next = head; //将节点的指针指向头节点

    head = node; //将头节点指向新节点

  }

  void remove(int val) { //删除操作

    if (head == NULL) return; //链表为空,不需要删除

    if (head->val == val) { //头节点需要删除

      Node* node = head;

      head = node->next; //将头节点指向下一个节点

      delete node; //释放节点内存

      return;

    }

    Node* prev = head;

    while (prev->next != NULL && prev->next->val != val) //找到待删除节点的前一个节点

      prev = prev->next;

    

    if (prev->next == NULL) return; //没有找到待删除节点

    Node* node = prev->next; //找到待删除节点

    prev->next = node->next; //将前一个节点的指针指向下一个节点

    delete node; //释放节点内存

  }

  void print() { //遍历操作

    Node* node = head;

    while (node != NULL) //当节点不为空时输出节点的数据元素

      cout << node->val << " ";

      node = node->next; //继续遍历下一个节点

    

    cout << endl;

  }

};

使用以上的LinkedList类,我们可以方便地进行单链表的插入、删除和遍历等操作。例如,我们可以将以下代码添加到main函数中:


LinkedList list;

list.insert(1);

list.insert(2);

list.insert(3);

list.print();

list.remove(2);

list.print();

运行上述代码,输出结果为:


3 2 1

3 1

可以看到,单链表的插入和删除操作非常高效,我们可以方便地通过单链表实现许多复杂的算法。因此,掌握单链表的实现是C++程序员必不可少的基础知识之一。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复