实现有头单向链表

定义数据结构

定义链表的节点

struct Node {  
    int data;  
    Node *next;  
};

包含两个部分，一个是数据（简单起见，只考虑是int的情形）

class LinkedList {  
private:  
    Node *virtual_head;  
    int size;  
  
public:  
    LinkedList();  
  
    bool isEmpty();  
  
    int getSize();  
      
    void print();  
  
    void add(int data);  
  
    int getIndex(int val);  
  
    int getValue(int index);  
  
    void remove(int index);  
  
    void insert(int index, int data);  
  
    ~LinkedList();  
  
};

链表的结构大致如下

初始化

LinkedList::LinkedList() {  
    virtual_head = new Node;  
    virtual_head->next = nullptr;  
    size = 0;  
}

判断链表是否为空

bool LinkedList::isEmpty() {  
    return virtual_head->next == nullptr;  
}

还可以这样写

bool LinkedList::isEmpty() {  
    return this->size == 0; 
}

获取链表大小

int LinkedList::getSize() {  
    return this->size;  
}

打印链表

void LinkedList::print() {  
    // 创建一个Node指针，指向虚拟头节点（其next指向virtual_head）  
    Node *current_node = this->virtual_head;  
    // 遍历链表，打印每个节点的数据  
    while (current_node->next != nullptr) {  
        current_node = current_node->next;  
        cout << current_node->data << " ";  
    }  
    cout << endl;  
    // 打印效果类似如下 1 2 3 4 5

新增元素

    Node *new_node = new Node;  
    new_node->data = data;  
    new_node->next = nullptr;

先考虑一般情形，假如链表长度为5（不算虚拟头结点），想在链表尾部增加元素，需要知道最后一个节点（第五个节点）的地址，将其next指针修改为新的节点的地址

再考虑特殊情形，如果链表为空，则直接将虚拟头结点的next指针指向新的节点的地址即可

void LinkedList::add(int data) {  
    // 新建一个节点  
    Node *new_node = new Node;  
    new_node->data = data;  
    new_node->next = nullptr;  
  
    // 如果链表为空，则 virtual_head 指向 new_node    
    if (isEmpty()) {  
        virtual_head->next = new_node;  
    }  
    // 如果链表不为空，则找到最后一个节点，把其 next 指针指向 new_node    
    else {  
        Node *last_node = this->virtual_head;  
        while (last_node->next != nullptr) {  
            last_node = last_node->next;  
        }
        // while循环结束后，last_node指向链表的最后一个节点  
        last_node->next = new_node;  
    }  
    size++;  
}

特殊的情形带入到一般的情形适不适用？
看刚刚代码的循环部分

while (last_node->next != nullptr) {  
	last_node = last_node->next;  
}

如果链表为空，last_node->next为nullptr，不满足while的条件，last_node为virtual_head，可以作为链表最后一个元素

优化后代码如下

void LinkedList::add(int data) {  
    // 新建一个节点  
    Node *new_node = new Node;  
    new_node->data = data;  
    new_node->next = nullptr;  
      
    Node *last_node = this->virtual_head;  
    while (last_node->next != nullptr) {  
        last_node = last_node->next;  
    }  
    // while循环结束后，last_node指向链表的最后一个节点  
    last_node->next = new_node;  
      
    size++;  
}

根据值获取索引

int LinkedList::getIndex(int val) {  
    // 函数作用：获取值为val的节点的索引  
    // 如果没有找到，则返回-1  
    Node *current_node = this->virtual_head;  
    // 变量i用于记录current_node遍历到的节点的索引  
    int i = -1;  
    while (current_node->next != nullptr) {  
        current_node = current_node->next;  
        i++;  
        if (current_node->data == val) {  
            break;  
        }  
    }  
    return i;  
}

根据索引获取值

int LinkedList::getValue(int index) {  
    // 函数作用：获取索引为index的节点的值  
    // 如果索引越界，则返回0,并打印警告信息  
    if (index < 0 || index >= this->size) {  
        cout << "警告：索引越界" << endl;  
        return 0;  
    }  
  
    // 假如访问的索引是i，则需要找到索引为i的节点，然后返回其值。需要遍历链表  
  
    Node *current_node = this->virtual_head;  
    // 变量i用于记录current_node遍历到的节点的索引  
    int i = -1;  
  
    while (i != index) {  
        current_node = current_node->next;  
        i++;  
    }  
    // while循环结束后，current_node指向索引为index的节点  
    return current_node->data;  
}

删除节点

void LinkedList::remove(int index) {  
    // 函数作用：删除索引为index的节点  
  
    // 链表如果是空的，那就不用删除了  
    if (isEmpty()) {  
        return;  
    }  
    // 如果索引越界，则不删除  
    if (index < 0 || index >= this->size) {  
        return;  
    }  
    // --------------------------  
    if (index == 0) {   
        // 删除头结点  
        // 获取索引为0的节点的next指针，把它赋值给virtual_head，然后删除索引为0的节点  
        Node *head_node = this->virtual_head->next;   
        this->virtual_head->next = head_node->next;  
        delete head_node;  
        this->size--;  
    }  
    else if (index == this->size - 1) {  
        // 要删除最后一个节点  
        Node *pre_last_node = this->virtual_head;  
        while (pre_last_node->next != nullptr) {  
            pre_last_node = pre_last_node->next;  
        }  
        // while循环结束后，pre_last_node指向链表的倒数第二个节点  
        // 把pre_last_node的next指针指向nullptr  
        pre_last_node->next = nullptr;  
        delete pre_last_node;  
        this->size--;  
    }  
    else {  
        // 一般情形，即删除中间节点  
        // 想要删除索引为index的节点，需要先获取索引为index-1的节点，  
        // 然后把其next指针指向索引为index+1的节点（原本指向索引为index的节点），最后删除索引为index的节点  
  
        Node *pre_index_node = this->virtual_head;  
        // 变量i用于记录pre_index_node遍历到的节点的索引  
        int i = -1;  
  
        while (i != index - 1) { // 当pre_index_node指向索引为index-1的节点时，i为index-1，循环结束  
            pre_index_node = pre_index_node->next;  
            i++;  
        }  
        // while循环结束后，pre_index_node指向索引为index-1的节点  
        // 找到索引为index的节点，把它的地址赋值给index_node  
        Node *index_node = pre_index_node->next;  
        // 把索引为index-1的节点的next指针指向索引为index的节点的next  
        pre_index_node->next = index_node->next;  
        // 删除索引为index的节点，防止内存泄漏  
        delete index_node;  
        this->size--;  
    }  
}

三种情形可以合并成一种情形

void LinkedList::remove(int index) {  
    // 函数作用：删除索引为index的节点  
    // 链表如果是空的，那就不用删除了  
    if (isEmpty()) {  
        return;  
    }  
  
    // 如果索引越界，则不删除  
    if (index < 0 || index >= this->size) {  
        return;  
    }  
    // 执行到这里，索引的取值范围一定是[0,size-1]  
    // ----------------------    // 先考虑一般情形，即删除中间节点  
    // 想要删除索引为index的节点，需要先获取索引为index-1的节点，  
    // 然后把其next指针指向索引为index+1的节点（原本指向索引为index的节点），最后删除索引为index的节点  
    // 如果要删除最后一个节点，过程类似，先获取索引为index-1的节点，修改其next指针指向nullptr，然后删除索引为index的节点  
    // 可以与一般情形合并。都需要索取索引为index-1的节点，然后修改其next指针指向索引为index节点的next  
    // 如果要删除头结点（即索引为0的节点），需要获取索引为0的节点的前一个节点virtual_head，  
    // 把这个节点的next修改为索引为index（0）的节点的next，然后删除索引为0的节点  
  
    // 这3种情况的共同特点：  
    // 都需要找到索引为index-1的节点，然后修改其next指针指向索引为index的节点的next，最后删除索引为index的节点  
    // 合并这三种情况的代码如下  
       Node *pre_index_node = this->virtual_head;  
    // 变量i用于记录pre_index_node遍历到的节点的索引  
    int i = -1;  
      
    while (i != index - 1) { // 当pre_index_node指向索引为index-1的节点时，i为index-1，循环结束  
        pre_index_node = pre_index_node->next;  
        i++;  
    }  
    // while循环结束后，pre_index_node指向索引为index-1的节点  
    // 找到索引为index的节点，把它的地址赋值给index_node  
    Node *index_node = pre_index_node->next;  
    // 把索引为index-1的节点的next指针指向索引为index的节点的next  
    pre_index_node->next = index_node->next;  
    // 删除索引为index的节点，防止内存泄漏  
    delete index_node;  
    this->size--;  
  
}

插入元素

void LinkedList::insert(int index, int data) {  
    // 函数作用：在索引为index的节点前插入一个元素。（即插入后新的元素索引为index）  
  
    if (index < 0 || index > this->size) {  
        return;  
    }  
  
    // 索引为size的话，就是在链表尾部插入一个节点。这也包括了链表为空的情况  
    if (index == this->size) {  
        add(data);    
    }  
    else {  
  
        // 需要在索引为index的节点之前插入一个节点，所以需要找到索引为index-1的节点。  
        // 然后先把新建的节点的next指向（插入前）索引为index的节点，  
        // 再把索引为index-1的节点的next指针指向新建的节点，  
  
        Node *pre_index_node = this->virtual_head;  
        int i = -1;  
        while (i < index - 1) {  
            pre_index_node = pre_index_node->next;  
            i++;  
        } // while循环结束后，pre_index_node指向索引为index-1的节点  
  
        // 新建一个节点  
        Node *new_node_to_insert = new Node;  
        new_node_to_insert->data = data;  
        new_node_to_insert->next = pre_index_node->next;  
        // 把索引为index-1的节点的next指针指向新建的节点  
        pre_index_node->next = new_node_to_insert;  
        this->size++;  
    }  
}

析构函数

LinkedList::~LinkedList() {  
    // 析构函数，释放链表占用的内存  
    // 为什么需要释放？因为链表的每一个节点都是一个动态申请的内存（使用了new关键字），我们需要逐一释放。  
    Node *current_node = this->virtual_head;  
  
    while (current_node != nullptr) {  
        Node *temp = current_node;  
        current_node = current_node->next;  
        delete temp;  
    }  
    // 为什么需要设计temp？举个例子，current_node指向节点5时，如果我们直接删除节点5对于的内存，  
    // 那么current_node就变成了nullptr，导致后续的操作无法进行。所以我们需要一个临时变量temp，  
    // 用来保存当前节点，然后删除当前节点temp，然后current_node指向下一个节点。  
}

参考：
【数据结构】链表(单链表实现+详解+原码)-CSDN博客