链表 | 阿走

静态链表

静态链表是指用两个数组来表示链表，不使用指针。相对于常见的动态链表，静态链表的大小在创建时就被确定，不会在运行时进行动态调整。

静态链表主要由两个数组组成：一个数组用于存储数据，另一个数组用于存储下一个结点的索引。这样的结构使得静态链表在实现上更加简单，但也带来了一些限制，例如无法动态增加或减少结点。所以静态链表的效率比结构体的链表更高，比较适用于解算法题，而不适用于解决工程问题。

在之后的图数据结构中的邻接表也是使用静态链表来实现。

单链表（静态数组实现）

题目描述

实现一个单链表，链表初始为空，支持三种操作：

向链表头插入一个数；
删除第 k 个插入的数后面的一个数；
在第 k 个插入的数后插入一个数。

现在要对该链表进行 M 次操作，进行完所有操作后，从头到尾输出整个链表。

代码展示

#include <iostream>

using namespace std;
const int N = 1e5 + 10;

int h = -1; //最开始的时候，链表的头节点要指向-1，
int ne[N], e[N], idx; //idx在我看来扮演两个角色，第一个是在一开始的时候，作为链表的下标，让我们好找
				    //第二在链表进行各种插入，删除等操作的时候，作为一个临时的辅助性的所要操作的元素的下
				    //标来帮助操作。并且是在每一次插入操作的时候，给插入元素一个下标，给他一个窝，感动！

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

void rm(int x)
{
  ne[x] = ne[ne[x]];
}
//将x插入到头节点上
void insert_head(int v)
{
  e[idx] = v; ne[idx] = h; h = idx++; 
}

int main()
{
  int m;
  cin >> m;
  while( m -- )
  {
    char op;
    cin >> op;
    int x, k;
    if( op == 'H' )
    {
      cin >> x;
      insert_head(x);
    }
    else if( op == 'D' )
    {
      cin >> k;
      if( !k )h = ne[h];
      else rm(k - 1);
    }
    else{
      cin >> k >> x;
      insert(k - 1, x);
    }
  }
  
  for(int i = h; i != -1; i = ne[i])
  {
    cout << e[i] << ' ';
  }
  return 0;
}

双链表

题目描述

实现一个双链表，双链表初始为空，支持 5 种操作：

在最左侧插入一个数；
在最右侧插入一个数；
将第 k 个插入的数删除；
在第 k 个插入的数左侧插入一个数；
在第 k 个插入的数右侧插入一个数

现在要对该链表进行 M 次操作，进行完所有操作后，从左到右输出整个链表。

代码实现

#include <iostream>

using namespace std;
const int N = 1e5 + 10;

int l[N], r[N], e[N], idx;

void init()
{
  r[0] = 1, l[1] = 0;
  idx = 2;
}

void remove(int k)
{
  r[l[k]] = r[k];
  l[r[k]] = l[k];
}

void add_l(int x)
{
  e[idx] = x, l[idx] = 0, r[idx] = r[0], l[r[0]] = idx, r[0] = idx++;
}

void add_r(int x)
{
  e[idx] = x, r[idx] = 1, l[idx] = l[1], r[l[1]] = idx, l[1] = idx++;
}

void insert_l(int x, int k)
{
  e[idx] = x, l[idx] = l[k], r[idx] = k, r[l[k]] = idx, l[k] = idx++;
}

void insert_r(int x, int k)
{
  e[idx] = x, l[idx] = k, r[idx] = r[k], l[r[k]] = idx, r[k] = idx++;
}

int main()
{
  init();
  int n;
  cin >> n;
  while( n -- )
  {
    int x, k;
    string op;
    cin >> op;
    if( op == "D" )
    {
      cin >> k;
      remove(k + 1);
    }else if( op == "R" )
    {
      cin >> x;
      add_r(x);
    }else if( op == "L" )
    {
      cin >> x;
      add_l(x);
    }else if( op == "IL" )
    {
      cin >> k >> x;
      insert_l(x, k + 1);
    }else
    {
      cin >> k >> x;
      insert_r(x, k + 1);
    }
  }
  
  for(int i = r[0]; i != 1; i = r[i])
    cout << e[i] << " ";
  
  return 0;
}