手写链表C++

news/2024/7/7 20:04:23

目录

一、链表基本概念以及注意事项

1.1 构造函数与析构函数

1.2 插入元素

1.3 重载运算符

二、小结

一、链表基本概念以及注意事项

        在工作中，链表是一种常见的数据结构，可以用于解决很多实际问题。在学习中，掌握链表可以提高编程能力和算法思维能力。在面试中，手写链表是一个常考的知识点，能够考察应聘者的编程水平和代码实现能力。因此，掌握手写C++链表对于程序员来说是非常重要的。

         C++链表，一种重要的数据结构，由一系列节点构成，每个节点包含两部分：数据和指向下一个节点的指针。链表是一种物理存储单元上非连续、非顺序的存储结构，数据结构的逻辑顺序是通过链表中的指针链接次序实现的。链表的最简单形式是单向链表，它只包含一个信息域和一个指针域。链表的优点是可以动态地分配内存空间，实现高效的数据操作。在C++中，链表的每个节点都是通过指针链接在一起，从而形成一个连续的链式结构。

        使用纯C/C++实现List链表。在编写函数之前，请务必注意以下三点：

  • 输入的指针、各类容器可能是空的
  • 输入的容器可能只有一个元素
  • 输入的容器可能有多个元素，这个是最常见的情况。

所以，为了代码安全，该加的判断都要加上。完整代码：

#include<iostream>
using namespace std;

class Node
{
public:
    int data_;//数据阈
    Node* next_;//指针阈
public:
    Node() :data_(-1), next_(nullptr) {}
};
class List
{
public:
    List()
    {
        this->head_ = new Node();// 不分配空间，下面赋值是不合理的！
                                 //this->head_->data_ = 0;//多余？
        this->head_->next_ = nullptr;
        this->size_ = 0;
    };
    void insert(int pos, int value);
    void remove(int pos);
    int get_reverse_element(int reverse_pos);//链表中倒数第k个节点
    void reverse();
    int operator[](int i);
    void print();
    ~List();
public:
    Node* head_;
    int size_;//维护一个size
};
//在第pos个元素前一个位置插入（创建、找到位置、入链表）
void List::insert(int pos, int value)
{
    if (pos < 0 || pos > size_)
        return;
    //创建新的节点接受数据
    Node* newnode = new Node();
    newnode->data_ = value;
    //cout << "newnode->data_ = " << *newnode->data_ << endl;
    newnode->next_ = nullptr;
    //利用辅助指针找到pos前一个节点
    // 其实这里不断next，无非就是希望p_curr = nullptr
    // 然后56行 让newnode->next_  = nullptr（这个nullptr是从head_->next 传过来的）；也就是尾部插入嘛
    // 而循环链表 同理 让newnode->next_  = &(head_)（这个 &(head_) 是从head_->next 传过来的）；
    Node* p_curr = head_;
    for (int i = 0; i < pos; i++) //这个for循环本质上是head_->next_->next_......
    {
        p_curr = p_curr->next_;
    }
    //现在p_curr就是pos前一个节点的指针阈
    //新节点入链表
    newnode->next_ = p_curr->next_;//右边
    p_curr->next_ = newnode;//左边
    size_++;
}
void List::remove(int pos)
{
    if (pos < 0 || pos > size_)
    {
        return;
    }
    Node* p_curr = head_;
    for (int i = 0; i < pos; i++)// 3
    {
        p_curr = p_curr->next_;
    }
    p_curr->next_ = p_curr->next_->next_;
    size_--;
}

//链表中倒数第k个节点
int List::get_reverse_element(int reverse_pos)
{
    int pos = size_ - reverse_pos;
    Node* p_curr = head_;
    for (int i = 0; i < pos; i++)
    {
        p_curr = p_curr->next_;
    }
    return p_curr->data_;
}

//反转链表
void List::reverse()
{
    // head   -> 1 -> 2 -> 3 -> 4 -> nullptr
    //nullptr <- 1 <- 2 <- 3 <- 4

    Node* p_curr = head_->next_;
    Node* p_prev = nullptr;
    while (p_curr != nullptr)
    {
        Node* p_next = p_curr->next_;
        if (p_next == nullptr)
            if (p_curr->next_ == nullptr)
            {
                head_->next_ = p_curr;
            }
        p_curr->next_ = p_prev;
        p_prev = p_curr;
        p_curr = p_next;
    }
}
int List::operator[](int i)
{
    Node* p_curr = head_;
    int count = 0;
    while (count <= i)
    {
        p_curr = p_curr->next_;
        count++;
    }
    return p_curr->data_;
}
void List::print()
{
    if (size_ == 0)
    {
        cout << "size = 0" << endl;
        return;
    }
    //遍历
    Node* p_curr = head_->next_;//【注意这里next】
    while (p_curr != nullptr)
    {
        cout << p_curr->data_ << " ";
        p_curr = p_curr->next_;
    }
    cout << endl;
}
List::~List()
{
    while (size_ != 0)
    {
        Node* p_curr = head_;
        for (int i = 0; i < (size_ - 1); i++)// 012345 i < 5
        {
            p_curr = p_curr->next_;//for循环执行完，p_curr指向4
        }
        delete p_curr->next_;//删除最后一个元素
        p_curr->next_ = nullptr;//末尾元素 空指针
        size_--;
        print();
    }
    delete head_; //【这个容易忘记！】
    cout << "delete!" << endl;
}

//合并两个排序链表
void mergeLists(List& list3, List& list4, List& list34)
{
    Node* p_curr3 = list3.head_->next_;
    Node* p_curr4 = list4.head_->next_;
    Node* p_curr34 = list34.head_->next_;
    int location = 0;
    while ((p_curr3 != nullptr) || (p_curr4 != nullptr))
    {
        if ((p_curr3 != nullptr) && (p_curr4 != nullptr))
        {
            if (p_curr3->data_ < p_curr4->data_)
            {
                list34.insert(location, p_curr3->data_);
                location++;
                list34.insert(location, p_curr4->data_);
                location++;
            }
            else
            {
                list34.insert(location, p_curr4->data_);
                location++;
                list34.insert(location, p_curr3->data_);
                location++;
            }
            p_curr3 = p_curr3->next_;
            p_curr4 = p_curr4->next_;
        }
        else if ((p_curr3 != nullptr) && (p_curr4 == nullptr))
        {
            list34.insert(location, p_curr3->data_);
            location++;
            p_curr3 = p_curr3->next_;
        }
        else if ((p_curr3 == nullptr) && (p_curr4 != nullptr))
        {
            list34.insert(location, p_curr4->data_);
            location++;
            p_curr4 = p_curr4->next_;
        }
    }
}
int main()
{
    List list1;
    //插入
    for (int i = 0; i < 15; i++)
    {
        list1.insert(i, i);
    }
    //删除
    list1.remove(10);
    list1.remove(5);
    //打印
    list1.print();
    list1.reverse();
    list1.print();
    //访问倒数元素
    for (int i = 1; i < 4; i++)
    {
        cout << "倒数第" << i << "个元素是：" << list1.get_reverse_element(i) << endl;
    }
    list1.insert(2, 9999);
    //重载符[]
    for (int i = list1.size_ - 1; i >= 0; i--)
    {
        cout << list1[i] << " ";
    }
    cout << endl;
    List list2;
    list2.insert(0, 10);
    list2.insert(1, 20);
    list2.insert(2, 30);
    list2.print();
    int size2 = list2.size_;
    //合并两个排序链表
    List list3, list4;
    for (int i = 0; i < 5; i++)
    {
        list3.insert(i, 2 * i);
        list4.insert(i, 2 * i + 1);
    }
    list4.insert(5, 12);
    list4.insert(6, 21);
    list3.print();
    list4.print();
    List list34;
    mergeLists(list3, list4, list34);
    list34.print();
    return 1;
}

1.1 构造函数与析构函数

链表由多个Node节点组成 ，每个节点由数据和指针构成。其中，指针是下一个连接节点的地址。其中Node初始化数据一定要做，如下。

class Node
{
public:
    int data_;//数据阈
    Node* next_;//指针阈
public:
    Node():data_(-1), next_(nullptr)
    {}
};

List的构造函数实现，这里给头节点申请内存，size_参数初始化为0，后续每插入一个元素，就+1。

List()
{
    this->head_ = new Node();// 分配空间
    this->size_ = 0;
};

整个链表，实现任何功能，我们都要维护一个头节点和size_。析构函数如下，必须是串行的方式析构每一个节点，不然可能造成内存泄漏。

List::~List()
{
    while (size_ != 0)
    {
        Node* p_curr = head_;
        for (int i = 0; i < (size_ - 1); i++)// 012345 i < 5
        {
            p_curr = p_curr->next_;//for循环执行完，p_curr指向4
        }
        delete p_curr->next_;//删除最后一个元素
        p_curr->next_ = nullptr;//末尾元素 空指针
        size_--;
        print();
    }
    delete head_; //
    cout << "delete!" << endl;
}

在保证不断链的前提下；释放整个链表，似乎只能从后面开始delete。循环当中，每次遍历到 待删除节点前一个p_curr, 然后delete p_curr->next_

1.2 插入元素

//在第pos个元素前一个位置插入（创建、找到位置、入链表）
void List::insert(int pos, int value)
{
    if (pos < 0 || pos > size_)
        return;

    //创建新的节点接受数据
    Node* newnode = new Node();
    newnode->data_ = value;

    Node* p_curr = head_;
    for (int i = 0; i < pos; i++)
    {
        p_curr = p_curr->next_;
    }

    //新节点入链表
    newnode->next_ = p_curr->next_;
    p_curr->next_ = newnode;
    size_++;
}

18行、19行代码很好诠释了插入过程；其中18行代码：将当前节点的指针域指向 对象的地址 赋给 newnode->next_；保证了新数据与链表中后面连接；

19行代码：当前节点指针域指向 新的节点。例如： 1 2 3 4 5  要在 4 和 5 之间插入 一个 666，步骤如下：

  • 遍历至节点4；    1 2 3 4 5
  • 将666 指向5:； 1 2 3 4      666 5
  • 再将 4 指向 666； 1 2 3 4 666 5

1.3 重载运算符

C++ STL中的List是不能通过[ ]来访问元素的，只有vector可以。本文这里给自定义的List重载一个 [ ]，实现类似：arr[2]来访问元素的方法。

int List::operator[](int i)
{
    Node* p_curr = head_;
    int count = 0;
    while (count <= i)
    {
        p_curr = p_curr->next_;
        count++;
    }
    return p_curr->data_;
}

二、小结

        本文我们将实现最基础的List。List是一个常见的数据结构，用于存储有序的元素集合。在C++中，我们可以使用类和指针来实现List。

        下一篇文章将带来《C++ 实现List的反转、删除、合并》。这些操作在面试中经常被问到，因为它们是List的基本操作之一。通过反转、删除和合并List，我们可以更加深入地了解List的实现方式和应用场景。同时，这些操作也是许多算法的基础，例如排序、查找等。因此，掌握这些操作对于面试和实际应用都非常重要。

        在接下来的文章中，我们将介绍如何实现List的反转、删除和合并。如果您对这些操作感兴趣，敬请关注我们的下一篇文章！


http://lihuaxi.xjx100.cn/news/1776679.html

相关文章

第一章 Object-XML 映射简介

第一章 Object-XML 映射简介

文章目录 第一章 Object-XML 映射简介基础如何工作的映射选项IRIS 中的相关工具XML 文档的可能应用 第一章 Object-XML 映射简介 基础 将对象映射到 XML 一词意味着定义如何将该对象用作 XML 文档。要将对象映射到 XML&#xff0c;请将 %XML.Adaptor 添加到定义该对象的类的超…
阅读更多...
Javaweb之javascript的BOM对象的详细解析

Javaweb之javascript的BOM对象的详细解析

1.5.2 BOM对象 接下来我们学习BOM对象&#xff0c;BOM的全称是Browser Object Model,翻译过来是浏览器对象模型。也就是JavaScript将浏览器的各个组成部分封装成了对象。我们要操作浏览器的部分功能&#xff0c;可以通过操作BOM对象的相关属性或者函数来完成。例如&#xff1a…
阅读更多...
18 Linux 阻塞和非阻塞 IO

18 Linux 阻塞和非阻塞 IO

一、阻塞和非阻塞 IO 1. 阻塞和非阻塞简介 这里的 IO 指 Input/Output&#xff08;输入/输出&#xff09;&#xff0c;是应用程序对驱动设备的输入/输出操作。当应用程序对设备驱动进行操作的时候&#xff0c;如果不能获取到设备资源&#xff0c;那么阻塞式 IO 就会将对应应用…
阅读更多...
线性代数-Python-04：线性系统+高斯消元的实现

线性代数-Python-04：线性系统+高斯消元的实现

文章目录 1 线性系统2 高斯-jordon消元法的实现2.1 Matrix2.2 Vector2.3 线性系统 3 行最简形式4 线性方程组的结构5 线性方程组-通用高斯消元的实现5.1 global5.2 Vector-引入is_zero5.3 LinearSystem5.4 main 1 线性系统 2 高斯-jordon消元法的实现 2.1 Matrix from .Vecto…
阅读更多...
jQuery 网页属性操作

jQuery 网页属性操作

jQuery提供了一些方法&#xff0c;例如 attr() 、 html() 、 text() 和 val() &#xff0c;它们充当了HTML文档中内容的获取器和设置器。 jQuery – 获取内容 jQuery提供了 html() 和 text() 方法来提取匹配的HTML元素的内容。以下是这两种方法的语法&#xff1a; $(selector…
阅读更多...
根据DataFrame指定的列该列中如果有n个不同元素则将其转化为n行显示explode()

根据DataFrame指定的列该列中如果有n个不同元素则将其转化为n行显示explode()

【小白从小学Python、C、Java】 【计算机等考500强证书考研】 【Python-数据分析】 根据DataFrame指定的列 该列中如果有n个不同元素 则将其转化为n行显示 explode() 选择题 以下代码两次输出结果分别为几行&#xff1f; import pandas as pd df pd.DataFrame({种类:[蔬菜,水…
阅读更多...
一题三解(暴力、二分查找算法、单指针):鸡蛋掉落

一题三解(暴力、二分查找算法、单指针):鸡蛋掉落

涉及知识点 暴力、二分查找算法、单指针 题目 给你 k 枚相同的鸡蛋&#xff0c;并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。 已知存在楼层 f &#xff0c;满足 0 < f < n &#xff0c;任何从 高于 f 的楼层落下的鸡蛋都会碎&#xff0c;从 f 楼层或比它低的…
阅读更多...
Linux编写一个极简版本的Shell

Linux编写一个极简版本的Shell

Linux编写一个极简版本的Shell &#x1f4df;作者主页&#xff1a;慢热的陕西人 &#x1f334;专栏链接&#xff1a;Linux &#x1f4e3;欢迎各位大佬&#x1f44d;点赞&#x1f525;关注&#x1f693;收藏&#xff0c;&#x1f349;留言 本博客主要内容在Linux环境下&#xff…
阅读更多...
最新文章

Copyright @ 2022~2023