双链表的定义

  • 双向链表,又称为双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。 所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。 一般我们都构造双向循环链表。

  • 简单的来说,双链表中除首尾结点外,都知道其前一个结点(前驱),和后一个结点(后继)。

  • image.png

静态双链表

  • 通过静态的数组,来模拟内存分配。这样就省去动态内存分配所耗费的时间。

  • 变量介绍

    • l[i] -> 表示 i 这个结点的 左边结点(前驱)
    • r[i] -> 表示 i 这个结点的 右边结点(后继)
    • idx -> 用来模拟内存分配,idx 值表示下一个该分配的地址。
  • 双链表的操作

    • 定义单链表

      • 初始化
      • image.png
      • 	const int N = 100005;
        	int l[N], r[N], e[N], idx;
        	// 初始化单链表
        	init() {
        		// 将 数组的 第 0 和 1 个位置 设置成 双链表的头结点和尾结点
        		r[0] = 1;
        		l[1] = 0;
        		idx = 2;	// 因为 0 1 已经被分配了,所以从2开始继续分配
        	}
        
        
    • 链表的插入操作

      • 在第k个插入的元素的 右边 插入一个结点
        • image.png
        • 
          	insertRight(int k, int x) {
          		e[idx] = x;
          		l[idx] = k;		// 将新结点的左指针指向 k
          		r[idx] = r[k];		// 新结点右指针指向 k 的右指针所指向的结点
          
          		l[r[k]] = idx;		// 一定要先更新 k 指向的右结点的左指针的值
          		r[k] = idx;		// 将k的右指针指向idx
          		idx ++;			// idx 到下一个待分配的空间
          	}
          
      • 在第k个元素的 左边 插入一个结点
          1. 你可以仿照上面的写一个
        • 2)在左边插入相当于 insertRight(l[k], x); (也就是在左指针指向的结点右边插入)
    • 删除一个结点

      • image.png
      • 	// 删除第k个插入的结点
        	remove(int k){
        		r[l[k]] = r[k];
        		l[r[k]] = l[k];
        	}
        
    • 遍历双链表

      • 	for (int i = r[0]; i != 1; i = r[i]) {
        		printf("%d ", e[i]);
        	}