如之前所说，数组在创建时需要预先分配好空间，且在添加元素或者删除元素的时候需要进行大量的操作，对数组的修改就变得十分浪费时间。因此一种新的数据结构：链表，被设计出来。

我们为什么需要链表？

• 可以动态的分配空间
• 容易插入、删除元素
• 更高的内存利用率（因为不需要预先分配空间，需要多少动态分配）
• 可以通过链表优化其他数据结构：栈、图、哈希表等等

1. 单链表

链表结构

单链表的结构较为简单，由一个head指针指向链表的第一个节点地址，链表的每个节点有两个部分：data和next，其中data是存放数据的部分，next是用于存放下一个节点地址的部分。链表的最后一个节点的next将指向null。

#include <iostream>
using namespace std;
int main() {
    struct Node{
        int data;
        Node* next;
    };
}

以上为使用C++实现的单链表。其中Node为创建的链表结构，data部分使用int类型，next部分使用Node指针类型，因此next是一个Node指针类型的指针，指向下一个Node的地址。

初始化链表

void initNode(struct Node *head) {
    head->next = nullptr;   //定义一个指针，用来指向链表（类似于数组第一个元素的地址）
}

此处的指针用于访问链表，指针指向链表的第一个元素。

从头部插入元素

void frontInsertNode(struct Node *head, int newData) {
    Node *newNode = new Node;
    newNode->next = head->next;
    head->next = newNode;
    newNode->data = newData;
}

• 创建新节点
• 新节点的next指向head的next
• head的next指向新节点
• 给新节点赋值data

从尾部插入节点

void appendNode(struct Node *head, int newData) {
    Node *tailNode = head;
    Node *newNode = new Node;
    newNode->next = nullptr;
    while (tailNode->next != nullptr) {
        tailNode = tailNode->next;
    }
    tailNode->next = newNode;
    newNode->data = newData;
}

• 创建一个节点指针tailNode用来遍历
• 创建要插入的新节点
• 新节点的next指向空
• 利用新创建的指针去从头部遍历找到尾部的位置
• 尾部节点的next指向新节点
• 给新节点赋值data

从中间插入节点

其原理与上述尾部插入节点相似，只需要在遍历的时候添加条件匹配要插入的位置即可，此处不再赘述。

2. 双向链表

链表结构

双向链表只是在单链表的基础之上增加了prev节点，用于指向该节点的上一个节点，这意味着双向链表可以反向遍历。双向链表的插入效率、删除效率更高（遍历效率高）。

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

其结构在单向链表的基础之上多了一个prev指针用于指向上一个节点。

初始化链表

void initNode(struct Node *head) {
    head->next = nullptr;   //定义一个指针，用来指向链表（类似于数组第一个元素的地址）
    head->prev = nullptr;
}

从中间插入双向链表

void insertNode(struct Node *head, int newData, int position) {
    Node *index = head;
    Node *newNode = new Node;
    for (int i = 0; i < position; ++i) {
        index = index->next;
        if (index->next == nullptr) {
            cout << "ERROR, out of index";
            return;
        }
    }
    newNode->next = index->next;
    newNode->prev = index;
    newNode->next->prev = newNode;
    index->next = newNode;
    newNode->data = newData;
}

• 创建一个index指针，用于遍历
• 创建一个要插入的新节点
• 遍历双向链表，找到需要插入的位置
• 新节点的next指向插入位置节点的下一个节点
• 新节点的prev指向插入位置节点
• 新节点下一个节点的prev指向新节点
• 插入位置节点的next指向新节点
• 给新节点赋值data

其他节点操作基本一致，基本是遍历与指针的重新链接操作，此处不再赘述。