单链表是一种基本的线性数据结构，它通过链式存储方式而不是像数组那样是一块连续的内存位置来存储元素。类比数组在内存中是一段连续的空间，但是链表的每个节点可能是在随机的位置，（逻辑上连续，物理上不一定连续），在单链表中，每个元素（或称为节点）包含两部分：数据域和指针域。

数据域用于存储实际的数据，而指针域则存储指向下一个节点的地址。

这样，每个节点都链接到列表中的下一个节点，形成一个链条。

如下图：

作为链表初学者我们一般这样定义节点：

struct Node//构建一个节点
{
	int data;//数据域
	struct Node * next;//指针域
};

创建链表

int main() 
{
    int n;
    scanf("%d", &n); // 输入链表的节点数

    Node* phead = NULL; // 头指针
    Node* ptail = NULL; // 尾指针
    phead = (Node*)malloc(sizeof(Node)); // 头指针指向不存储数据的头节点
    ptail = phead; // 尾指针也指向头节点

    for (int i = 1; i <= n; ++i) 
    { // i == 1是第一个存储数据的节点即首节点
        Node* p = (Node*)malloc(sizeof(Node)); // 动态申请内存空间
        int data;
        scanf("%d", &data); // 输入数据
        p -> data = data; // 存储数据

        ptail -> pnext = p; // 把新节点加到链表的尾部
        ptail = p; // 更新尾指针，指向新节点
        ptail -> pnext = NULL; // 新节点的 pnext 是 NULL
    }
    return 0;
}

遍历链表

    Node* current = phead -> pnext; // 从第一个有效节点开始
    while (current != NULL) 
    {
        printf("%d ", current -> data); // 输出当前节点的数据
        current = current -> pnext; // 移动到下一个节点
    }

头插法

    int data;
    Node* newNode = (Node*)malloc(sizeof(Node));
    scanf("%d", &data);
    newNode -> data = data;
    newNode -> pnext = phead -> pnext; // 新节点的 pnext 指向原来的头节点
    phead -> pnext = newNode; // 更新头指针

尾插法

    // 如果链表为空
    if (phead -> pnext == NULL) 
    {
        phead -> pnext = newNode;
    } else 
    {
        Node* current = phead -> pnext;
        while (current -> pnext != NULL) 
        { // 找到链表的尾部
            current = current -> pnext;
        }
        current -> pnext = newNode; // 将尾节点的 pnext 指向新节点
    }

释放内存

    Node* current = phead;
    while (current != NULL) 
    {
        Node* temp = current;
        current = current -> pnext;
        free(temp); // 释放当前节点
    }

可以发现代码实在太多了，我们学习用数组模拟链表，$head$ 表示头指针，$idx$ 表示为链表中的节点编号，用 $e[idx]$，表示链表节点 $idx$ 的数据域，$ne[idx]$，表示链表节点 $idx$ 的指针域。

#include <iostream>

using namespace std;

const int N = 100010;


// head 指向首节点,此时我们忽略头节点，直接存储数据
// e[i] 表示节点i的值
// ne[i] 表示节点i的next指针是多少
// idx 存储当前已经用到了哪个点
// idx 为零时为首节点.
int head = -1, e[N], ne[N], idx;

// 将x插到第一个有效结点前面
void add_to_head(int x)
{
    e[idx] = x, ne[idx] = head, head = idx++;
}

// 将x插到下标是k的点后面
void add(int k, int x)
{
    e[idx] = x, ne[idx] = ne[k], ne[k] = idx++;
}

// 将下标是k的点后面的点删掉
void remove(int k)
{
    ne[k] = ne[ne[k]];
}

int main()
{
    int m;
    cin >> m;
    while (m--)
    {
        int k, x;
        char op;

        cin >> op;
        if (op == 'H')
        {
            cin >> x;
            add_to_head(x);
        }
        else if (op == 'D')
        {
            cin >> k;
            if (!k) head = ne[head];
            else remove(k - 1);
        }
        else
        {
            cin >> k >> x;
            add(k - 1, x);
        }
    }

    for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
    cout << endl;

    return 0;
}