单链表

#include <iostream>
using namespace std;
const int N = 100010;
int head, e[N], ne[N], idx;

//初始化单链表
void init()
{
    head = -1;
    idx = 0;
}

//在头节点后插入一个节点
void add_to_head(int x)
{
    e[idx] = x;
    ne[idx] = head;
    head = idx;
    idx++;
}

//在第k个节点后插入一个节点
void add(int k, int x)
{
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx++;
}

//删除第k个节点后面的一个节点
void remove(int k)
{
    ne[k] = ne[ne[k]];
}

//从头打印所有节点的值
void printAllNode()
{
    int current = head;
    while (current != -1)
    {
        cout << e[current] << " ";
        current = ne[current];
    }
}

int main()
{
    init();
    add_to_head(3);
    add_to_head(1);
    add_to_head(2);
    add(2,5);
    remove(2);

    printAllNode();
    return 0;
}

双链表

#include <iostream>
using namespace std;
const int N = 100010;
int head, e[N], l[N], r[N], idx;

//初始化双链表
void init()
{
    r[0] = 1;
    l[1] = 0;
    idx = 2;
}

//在第k个节点的右边插入x
//想在第k个节点的左边插入x需使k = l[k]
void add(int k, int x)
{
    e[idx] = x;
    r[idx] = r[k];
    l[idx] = k;
    l[r[k]] = idx;
    r[k] = idx;
    idx++;
}

//删除第k个节点
void remove(int k)
{
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

//正向遍历输出
void printForward()
{
    int current = 0;
    while (true)
    {
        current = r[current];
        if (current == 1)
            break;
        cout << e[current] << " ";
    }
}

//反向遍历输出
void printBackward()
{
    int current = 1;
    while (true)
    {
        current = l[current];
        if (current == 0)
            break;
        cout << e[current] << " ";
    }
}

int main()
{
    init();
    add(0, 1);
    add(2, 2);
    add(3, 3);

    printForward();
    cout << "\n";
    printBackward();

    cout << "\n";
    remove(2);
    printForward();

    return 0;
}
最后修改:2025 年 02 月 28 日
如果觉得我的文章对你有用,请随意赞赏