数组模拟链表

主要介绍单链表和双链表

  • 单链表即中用的最多的是邻接表，用来存储图和树
  • 双链表用来优化某些问题

为什么用数组模拟链表呢？
因为new一个链表是非常耗时的，如果数据过多会直接超时，所以用数组去表示更为合适

一、单链表

1、表示方法

一个节点的值用e[n]表示，指向下一个节点的指针用ne[n]表示，e和ne用数组下标来绑定
image.png
所以需要创建两个数组，一个e[]，一个ne[]。因为这个数组是用下标模拟指针指向，故不需要将节点按照第一个结点第二个结点这样按顺序放入其中。故需要再有一个idx指向数组的下一个可用的元素

2、模板代码

  1. // head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
  2. int head, e[N], ne[N], idx;
  4. // 初始化
  5. void init()
  6. {
  7.     head = -1;
  8.     idx = 0;
  9. }
  11. // 在链表头插入一个数a
  12. void insert(int a)
  13. {
  14.     e[idx] = a; //相当于Node n = new Node() n.setVal(a)
  15.     ne[idx] = head; // n指向head指向的结点 n.setNext(head.getNext()) 
  16.     head = idx ++ ; // head指向新建的节点，完成头插。idx往后移一位
  17. }
  19. // 将x插入k后
  20. void add(int k, int x) 
  21. {
  22.     e[idx] = x; // 相当于Node n = new Node() n.setVal(x)
  23.     ne[idx] = ne[k]; // n指向k指向的结点 n.setNext(k.getNext()) 
  24.     ne[k] = idx; // k指向新建的节点，完成头插
  25.     idx ++; // idx往后移一位
  26. }
  28. // 将k结点删除
  29. void remove()
  30. {
  31.     ne[k] = ne[ne[k]];
  32. }

二、双链表

双链表用数组表示的时候，每个节点的值还用e[]表示，指针可以定义两个数组l[]``r[]，一个表示左边是谁，一个表示右边是谁。为了方便，我们定义下表为0表示head指针，下标为1表示tail指针

模板代码

  1. // e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
  2. int e[N], l[N], r[N], idx;
  4. // 初始化
  5. void init()
  6. {
  7.     //0是左端点，1是右端点
  8.     r[0] = 1, l[1] = 0;
  9.     idx = 2;
  10. }
  12. // 在节点a的右边插入一个数x
  13. void insert(int a, int x)
  14. {
  15.     e[idx] = x;
  16.     l[idx] = a, r[idx] = r[a];
  17.     l[r[a]] = idx, r[a] = idx ++ ;
  18. }
  20. // 删除节点a
  21. void remove(int a)
  22. {
  23.     l[r[a]] = l[a];
  24.     r[l[a]] = r[a];
  25. }