一. 题目

二. 理论

1. 数组模拟版

2. 类指针版

• 单链表是一种常见的数据结构，它由一系列节点（Node）组成，每个节点包含两个部分：

• 数据域（Data Field）：存储节点的数据内容。

• 指针域（Pointer/Next Field）：存储指向下一个节点的指针。不用指针就是整个副本，开销很大，且会导致递归包含，类包含自己了！！！

• 单链表的特点是节点之间通过指针连接，形成一个线性结构。头节点指向链表的第一个节点，尾节点的指针为 null（表示链表的终止）。与数组不同，单链表的大小可以动态调整，因为不需要连续的内存空间。

• 

三. 代码

1. 数组模拟版

class SingleLinkedList
{
public:
    //数组模拟单链表版
    static const int N=1e5+10;
    int h[N], e[N], ne[N], idx;
public:
    static void initIO()
    {
        // 关闭输入输出缓存，使效率提升
        ios::sync_with_stdio(false);
        // 解除cin和cout的默认绑定，来降低IO的负担使效率提升
        cin.tie(nullptr);
        cout.tie(nullptr);
    }

    SingleLinkedList()
    {
        /**
         * 初始化
         * idx代表边的编号
         * h代表头结点数组，h[x]代表第x节点的链表，x是节点编号，h[x]的值是x链表第一条边的编号
         * ne[b], b是边的编号，ne[b]的值也是边的编号，ne[b]表示边的编号为b的边所指的节点的下一条边的编号
         * e[c], c是边的编号，e[c]表示边c所指的点的点的编号
         */
        idx=0;
        fill(e, e+N, 0);
        fill(h, h+N, -1);
        fill(ne, ne+N, 0);
    }

    /**
     * 头插法
     * 点a向点b接一条边
     * @param a
     * @param b
     */
    void addHead(int a, int b)
    {
        e[idx]=b, ne[idx]=h[a], h[a]=idx++;
    }
};

SingleLinkedList L;//创建单链表数组

int main()
{
    L.addHead(1, 2);
    L.addHead(1, 3);
}

class SingleLinkedList
{
    static final int N = (int) 1e5 + 10;
    int[] h = new int[N], e = new int[N], ne = new int[N];
    int idx;

    void init()
    {
        idx = 0;
        Arrays.fill(h, -1);
        Arrays.fill(e, 0);
        Arrays.fill(ne, 0);
    }

    void add(int a, int b)
    {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
}

public class Main
{
    static final SingleLinkedList L = new SingleLinkedList();

    public static void main(String[] args)
    {
        L.add(1, 2);
    }
}

2. 类指针版

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=1e5+10;

class SingleLinkedList
{
public:
    class SingleLinkedNode
    {
        public:
            int val;
            SingleLinkedNode *next;
        public:
            SingleLinkedNode(int val_):val(val_), next(nullptr) {}
    };
public:
    //头结点值为-1，方便处理链表中没有节点的情况。
    //实际链表头是head.next
    SingleLinkedNode head;
public:
    static void initIO()
    {
        // 关闭输入输出缓存，使效率提升
        ios::sync_with_stdio(false);
        // 解除cin和cout的默认绑定，来降低IO的负担使效率提升
        cin.tie(nullptr);
        cout.tie(nullptr);
    }

    SingleLinkedList():head(-1) {}

    /**
     * 头插法
     * @param val 节点值
     */
    void add_to_head(int val)
    {
        SingleLinkedNode *node=new SingleLinkedNode(val);
        node->next=head.next;
        head.next=node;
    }

    ~SingleLinkedList()
    {
        //p表示前一个，q表示后一个
        SingleLinkedNode *p=head.next, *q;
        while(p != nullptr)
        {
            q=p->next;
            delete p;
            p=q;
        }
    }
};

int main()
{
    SingleLinkedList::initIO();
    SingleLinkedList list;//创建一个单链表
}

class SingleLinkedList
{
    static class SingleLinkedListNode
    {
        int val;
        SingleLinkedListNode next;

        public SingleLinkedListNode(int val)
        {
            this.val = val;
        }
    }

    //头结点, 实际链表头是head.next
    SingleLinkedListNode head;

    //头插
    void add(int val)
    {
        SingleLinkedListNode newNode = new SingleLinkedListNode(val);
        newNode.next = head.next;
        head.next = newNode;
    }
}

public class Main
{
    static final SingleLinkedList L = new SingleLinkedList();

    public static void main(String[] args)
    {
        L.add(1);
    }
}