C++超详细分析单链表的实现与常见接口

C++超详细分析单链表的实现与常见接口

什么是单链表？

单链表，英文名为“Singly Linked List”，简称链表，是一种常用的数据结构，它是由若干个节点组成的，每个节点都包含了一个数据域和一个指向下一个节点的指针域。单链表的特点是以节点为单位，可以进行快速的插入和删除操作，但是随机访问就比较慢。

单链表的实现

定义节点类

在C++中，单链表可以通过类和指针来实现。首先我们需要定义一个节点类，包含数据和指向下一个节点的指针：

class Node {
public:
    int data; //数据
    Node* next; //指向下一个节点的指针
    Node(int _data): data(_data), next(nullptr) {}; //构造函数
};

其中，data是节点存储的数据，next是指向下一个节点的指针，构造函数用于初始化节点。在这里，我们将节点的指针初始化为nullptr，表示该节点没有指向任何其他节点。

定义链表类

接下来，我们需要定义一个链表类，包含链表的各种操作。

class LinkedList {
private:
    Node* head; //指向链表头节点的指针
    int length; //链表长度
public:
    LinkedList(): head(nullptr), length(0) {}; //构造函数
    ~LinkedList(); //析构函数
    void push_back(int data); //在链表末尾添加节点
    void insert(int index, int data); //在特定位置插入节点
    void remove(int index); //删除特定位置的节点
    int get(int index); //获取某一位置的节点数据
    int size(); //获取链表长度
};

其中，head是指向链表头节点的指针，length是链表长度。构造函数用于初始化链表，析构函数用于释放链表占用的内存。push_back函数将一个新节点插入到链表末尾，insert函数将一个新节点插入到链表的特定位置，remove函数将特定位置的节点从链表中删除，get函数用于获取链表中某一位置的节点的数据，size函数返回链表长度。

实现链表类中的各种操作

push_back函数

push_back函数用于在链表末尾添加节点。具体实现如下：

void LinkedList::push_back(int data) {
    Node* new_node = new Node(data); //创建新节点
    if (head == nullptr) {
        head = new_node; //如果链表为空，直接将头节点指向新节点
    } else {
        Node* p = head;
        while (p->next != nullptr) {
            p = p->next; //找到链表的尾节点
        }
        p->next = new_node; //将新节点插入到链表尾部
    }
    length++; //链表长度加1
}

首先创建一个新节点，在将其插入到链表尾部。如果链表为空，就将头节点指向新节点。否则，遍历链表找到尾节点，然后在将新节点插入到尾节点之后。最后更新链表长度。

insert函数

insert函数用于在链表的特定位置插入节点。具体实现如下：

void LinkedList::insert(int index, int data) {
    Node* new_node = new Node(data); //创建一个新节点

    if (index > length || index < 0) { //位置越界检查
        throw std::out_of_range("Index out of range!");
    }

    if (head == nullptr) {
        head = new_node; //如果链表为空，直接将头节点指向新节点
    } else if (index == 0) {
        new_node->next = head; //如果要插入的位置为0，直接插入到头节点之后
        head = new_node;
    } else {
        Node* p = head;
        for (int i = 1; i < index; i++) {
            p = p->next; //找到要插入位置的前一个节点
        }
        new_node->next = p->next; //将新节点插入到链表中
        p->next = new_node;
    }
    length++; //链表长度加1
}

首先创建一个新节点，然后判断要插入的位置是否越界。如果链表为空，直接将头节点指向新节点。如果插入的位置为0，直接插入到头节点之后。否则，遍历链表找到要插入位置的前一个节点，然后将新节点插入到链表中。最后更新链表长度。

remove函数

remove函数用于删除链表中特定位置的节点。具体实现如下：

void LinkedList::remove(int index) {
    if (index >= length || index < 0) { //位置越界检查
        throw std::out_of_range("Index out of range!");
    }

    Node* p = head;
    if (index == 0) {
        head = p->next; //删除头节点
    } else {
        for (int i = 1; i < index; i++) {
            p = p->next; //找到要删除的节点的前一个节点
        }
        Node* q = p->next; //要删除的节点
        p->next = q->next; //将删除节点的前后节点连接起来
        delete q; //释放删除节点的内存
    }
    length--; //链表长度减1
}

首先判断要删除的位置是否越界。如果要删除的是头节点，直接将头节点指向第二个节点。否则，遍历链表找到要删除节点的前一个节点，然后将要删除节点的前后节点连接起来，并释放要删除节点的内存。最后更新链表长度。

get函数

get函数用于获取链表中某一位置的节点的数据。具体实现如下：

int LinkedList::get(int index) {
    if (index >= length || index < 0) { //位置越界检查
        throw std::out_of_range("Index out of range!");
    }
    Node* p = head;
    for (int i = 0; i < index; i++) {
        p = p->next; //遍历链表找到特定位置的节点
    }
    return p->data; //返回该节点的数据
}

首先检查要获取的位置是否越界，然后遍历链表找到特定位置的节点，并返回该节点的数据。

size函数

size函数用于获取链表的长度。具体实现如下：

int LinkedList::size(){
    return length;
}

直接返回存储链表长度的变量。

示例

示例1

下面的示例演示了如何创建一个链表，并且向其中添加节点：

int main() {
    LinkedList list; //创建一个链表
    list.push_back(1); //在链表末尾添加节点
    list.push_back(2);
    list.push_back(3);
    for (int i = 0; i < list.size(); i++) {
        std::cout << list.get(i) << " "; //输出链表中各个节点的数据
    }
    return 0;
}

输出为：

1 2 3

示例2

下面的示例演示了如何创建一个链表，并删除其中的节点：

int main() {
    LinkedList list; //创建一个链表
    list.push_back(1);
    list.push_back(2);
    list.push_back(3);

    list.remove(1); //删除第2个节点之后

    for (int i = 0; i < list.size(); i++) {
        std::cout << list.get(i) << " "; //输出链表中各个节点的数据
    }
    return 0;
}

输出为：

1 3

以上示例演示了如何使用链表类中的操作来创建和修改一个链表的过程。