【数据结构】自己动手写一个C++链表功能

链表数据结构在操作数据时具有更高的性能，但同时因为其结构的原因会造成时间复杂度为O(N)，因此理解链表结构的底层实现能够让我们在开发中对程序的性能进行进一步优化。

如果你不知道什么是链表或者时间复杂度，可以参考我另外两篇文章：

• 【数据结构】数组、链表、堆栈、队列到底是什么？它们之间有什么区别？
• 【数据结构】时间复杂度和空间复杂度是什么？

代码

为了保证你能够更好的理解，我已经在代码中加入了很多注释方便理解，因此文章内不再阐述每个代码的作用。

#include <iostream>
using namespace std;

template <typename T>

// 节点结构
struct Node
{
    // 节点存储的数据
    T data;
    Node* next;

    explicit Node(T value): data(value), next(nullptr)
    {
    }
};

// 定义链表类
template <typename T>
class LinkedList
{
private:
    Node<T>* head; // 链表头指针私有
    int size; // 链表大小


public:
    LinkedList(): head(nullptr), size(0)
    {
    } // 构造函数
    // 插入节点到链表头部
    void add(T value)
    {
        // 链表中个数数量增加
        size++;
        // 创建一个新的Node
        auto* newNode = new Node(value);
        // 如果链接中当前头是空的
        if (head == nullptr)
        {
            // 则把头元素设置为当前的新元素
            head = newNode;
            return;
        }
        Node<T>* temp = head;
        while (temp->next != nullptr)
        {
            temp = temp->next; // 找到链表的末尾
        }
        // 将末尾Node的next指向新Node
        temp->next = newNode;
    }

    // 添加元素到指定位置
    void addAt(int index, T value)
    {
        // 检查要添加的索引是否不正确
        if (index > size || index < 0)
        {
            cout << "index out of bounds" << endl;
            return;
        }
        // 元素个数增加
        size++;
        if (index == 0)
        {
            head = new Node<T>(value);
            return;
        }
        // 当前索引位置
        int i = 0;
        // 临时变量
        Node<T>* temp = head;
        // 从链表头开始逐步取下一个链接并且要求下一个链表的位置<index
        while (temp->next != nullptr && i++ < index - 1)
        {
            temp = temp->next;
        }
        // 此时i == index，取出当前Node的正常next
        Node<T>* next = temp->next;
        // 将当前Node的next指向新Node
        temp->next = new Node<T>(value);
        // 将新创建的node的next指向原来的next
        temp->next->next = next;
    }

    void removeAt(int index)
    {
        if (index > size || index < 0)
        {
            cout << "index out of bounds" << endl;
            return;
        }
        int i = 0;
        Node<T>* temp = head;
        // 找到要删除的节点的前一个节点（i++ < index - 1）
        while (temp->next != nullptr && i++ < index - 1)
        {
            temp = temp->next;
        }
        // 要删除的Node节点
        Node<T>* deleteNode = temp->next;
        // 把当前Node节点的next指向deleteNode的next
        temp->next = deleteNode->next;
        size--;
        delete deleteNode;
    }

    T get(int index)
    {
        if (index > size || index < 0)
        {
            cout << "index out of bounds" << endl;
            return nullptr;
        }
        int i = 0;
        // 临时变量
        Node<T>* temp = head;
        // 从链表头开始逐步取下一个链接并且要求下一个链表的位置<index
        while (temp->next != nullptr && i++ < index)
        {
            temp = temp->next;
        }
        return temp->data;
    }

    // 清空链表元素
    void clear()
    {
        while (head != nullptr)
        {
            Node<T>* temp = head;
            head = head->next;
            delete temp;
        }
        size = 0;
    }

    // 输出链表中的元素
    void print() const
    {
        Node<T>* temp = head;
        while (temp != nullptr)
        {
            cout << temp->data << " ";
            temp = temp->next;
        }
        cout << endl;
    }

    // 析构函数，清理内存空间
    ~LinkedList()
    {
        clear();
    }
};

int main(int argc, char* argv[])
{
    LinkedList<int> list;
    list.add(1);
    list.add(2);
    list.add(3);
    list.print(); // 输出：1 2 3

    // 在索引1处插入4
    list.addAt(1, 4);
    list.print(); // 输出：1 4 2 3

    // 删除索引1的元素
    list.removeAt(1);
    list.print(); // 输出：1 2 3

    // 清空
    list.clear();
    list.print(); // 输出空
}

版权所有：XuanRan
未经书面授权，禁止转载