[数据结构与算法]C++实现单链表

实现链表的基本功能

链表的特点就不赘述了，这类的文章特别多，这里以简单的方式手动实现链表的各种操作。

结点结构

链表中的每个结点，包括一个结点值val和指向下一个结点的指针next。

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

实现功能：

1. get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
2. addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
3. addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
4. addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
5. deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

设计

维护一个链表元素个数size。
所有元素结点index的范围是[0…size-1]，第一个结点的index是0，第二个是1，以此类推。

获取前置结点

因为单链表不能反向遍历，而且插入，删除操作都要对目标结点的前一个结点进行操作，所以特地编写一个获取目标序号之前结点的方法：
如果index=0，就返回头结点；如果index=1，就返回第一个结点；以此类推。

//查找index位置的前一个结点，index范围[0...size-1]
ListNode* findBefore(int index) {
    ListNode* p = head;
    for (int i = 0; p != nullptr && i < index; i++) {
        p = p->next;
    }
    return p;
}

获取第index个结点的值

借助于前面写的findBefore方法，可以不用另外写一个for循环了。
index超出范围的话，返回-1

//获取链表中第 index 个节点的值。如果索引无效，则返回-1。index范围[0...size-1]
int get(int index) {
    if (index < 0 || index >= size) {
        return -1;
    }
    return findBefore(index)->next->val;
}

头插

在链表最前面插入新节点，值val，这个结点在head和第一个结点之间。

//头插
void addAtHead(int val) {
    ListNode* node = new ListNode(val);
    node->next = head->next;
    head->next = node;
    size++;
    
	//对一个结点的链表进行头插会导致尾结点发生变化
	if (size == 1) {
    	tail = node;
    }
}

尾插

在链表尾部插入新结点，值val。
因为尾插是比较常用的操作，如果每次尾插都遍历链表查找尾结点，性能会比较差，所以这里维护了一个尾结点指针tail。
尾插、删除最后一个结点、空表重复头插都会导致尾结点产生变化，具体维护方式在对应方法里。

//尾插
void addAtTail(int val) {
    ListNode* node = new ListNode(val);
    tail->next = node;
    tail = node;
    size++;
}

在指定index位置插入新结点

在链表中的第 index 个节点之前添加值为 val 的节点，插入的合法范围：index<=size。
如果index<=0则执行头插，index=size则执行尾插。

void addAtIndex(int index, int val) {
    if (index > size) {
        return;
    }
    if (index <= 0) {
        addAtHead(val);
    }
    else if (index == size) {
        addAtTail(val);
    }
    else {
        ListNode* before = findBefore(index);
        ListNode* node = new ListNode(val);
        node->next = before->next;
        before->next = node;
        size++;
    }
}

删除指定index位置的结点

index范围[0…size-1]

void deleteAtIndex(int index) {
    if (index < 0 || index >= size) {
        return;
    }
    ListNode* before = findBefore(index);
    //如果删除最后一个结点，需要处理尾结点
    if (index == size - 1) {
        tail = before;
    }
    ListNode* delNode = before->next;
    before->next = delNode->next;
    size--;
}

打印链表

每个结点之间用空格分隔。

//输出链表
void printList() {
    //p指向头结点后面的首个数据结点
    ListNode* p = head->next;
    while (p != nullptr) {
        cout << p->val << " ";
        p = p->next;
    }
    cout << endl;
}

完整代码

用一个链表类实现链表的初始化和各种功能。

#include <iostream>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

class MyLinkedList {
private:
    ListNode* head;
    ListNode* tail;
    //数据结点的数量
    int size;

public:
    //构造为只有一个头结点，大小为0的初始链表
    MyLinkedList() {
        size = 0;
        head = new ListNode(0);
        tail = head;
    }

    int getSize() {
        return size;
    }

    //查找index位置的前一个结点，index范围[0...size-1]
    ListNode* findBefore(int index) {
        ListNode* p = head;
        for (int i = 0; p != nullptr && i < index; i++) {
            p = p->next;
        }
        return p;
    }

    //获取链表中第 index 个节点的值。如果索引无效，则返回-1。index范围[0...size-1]
    int get(int index) {
        if (index < 0 || index >= size) {
            return -1;
        }
        return findBefore(index)->next->val;
    }

    //头插
    void addAtHead(int val) {
        ListNode* node = new ListNode(val);
        node->next = head->next;
        head->next = node;
        size++;
        if (size == 1) {
            tail = node;
        }
    }

    //尾插
    void addAtTail(int val) {
        ListNode* node = new ListNode(val);
        tail->next = node;
        tail = node;
        size++;
    }

    /*
    * 在链表中的第 index 个节点之前添加值为 val  的节点，插入的合法范围：index<=size。
    * 如果index<=0则执行头插，index=size则执行尾插
    */
    void addAtIndex(int index, int val) {
        if (index > size) {
            return;
        }
        if (index <= 0) {
            addAtHead(val);
        }
        else if (index == size) {
            addAtTail(val);
        }
        else {
            ListNode* before = findBefore(index);
            ListNode* node = new ListNode(val);
            node->next = before->next;
            before->next = node;
            size++;
        }
    }

    //index范围[0...size-1]
    void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return;
        }
        ListNode* before = findBefore(index);
        //如果删除最后一个结点，需要处理尾结点
        if (index == size - 1) {
            tail = before;
        }
        ListNode* delNode = before->next;
        before->next = delNode->next;
        size--;
    }

    //输出链表
    void printList() {
        //p指向头结点后面的首个数据结点
        ListNode* p = head->next;
        while (p != nullptr) {
            cout << p->val << " ";
            p = p->next;
        }
        cout << endl;
    }
};

int main() {
    MyLinkedList ml;
    ml.addAtHead(1);
    ml.addAtTail(3);
    ml.printList();

    ml.deleteAtIndex(0);
    ml.printList();
    cout << ml.get(0) << endl;
    
    //cout << ml.getSize();
}