WebGL2.0从入门到精通-2、数据结构与算法（三、双向循环链表的封装）

三、双向循环链表的封装

JS/TS 内置了动态数组 Array 对象，随着元素的加入，它的内部机制会自行扩容空间以容纳新元素。JS/TS 又内置了静态类型数组（如 Float32Array 等），这些静态类型数组一旦在构造函数中设定元素的个数后，就不能改变了。

为了让静态类型数组像 JS/TS 动态数组 Array 一样能够自动扩容，我们封装了动态化类型数组（TypedArrayList），它的原理是：如果当前元素个数 length 大于容量 capacity，则重新翻倍地分配一块连续的内存区块，然后将旧元素原封不动地一一搬往新分配的内存区块中，最后回收原来的那块内存。

通过上述描述可以发现，不管是内置的 Array 对象，还是二次封装的动态类型数组，在使用的过程中，有非常大的可能存在浪费内存的现象。

假设当前有个 float32 的动态类型数组，其容量为 10 个元素，如果插入第 11 个元素时则会发生扩容，复制原来的 10 个元素到新的数组中并且插入第 11 个元素，而后续我们不在插入其他元素，则会有 9 个未使用的元素其内存浪费着。

如果要避免上述内存浪费的现象，可以使用另外一种数据结构：链表。

相对于动态数组而言，链表的最大好处是当每次插入或删除一个元素时，就会分配或释放一个元素的内存空间。因此链表这种数据结构对内存的运用非常精准，一点也不浪费。

同时与动态数组相比，对于任何位置的插入或删除，链表永远是常数时间。

当然，链表最大的缺点就是无法快速地随机访问某个索引处的元素。

由于 JS/TS 中并没有内置链表这种数据结构，因而需要自行封装实现链表结构。

双向循环列表是由一个 头部节点 + 实际数据节点 组成的，实际数据节点可以为空，即当初始化 LinkList 时，可以只有头部节点，当执行了 push （数据插入后）就有了实际数据节点，实际数据节点的最后一个节点指向头部节点，头部节点的 data 值 是 undefined。

export class LinkNode<T> {
  public next: LinkNode<T> | null; // 指向下一个节点，自引用，指向当前 ListNode 的后驱
  public prev: LinkNode<T> | null; // 指向前一个节点，自引用，指向当前 ListNode 的前驱
  public data: T | undefined; // 当前节点实际存储的数据，ListNode 所持有的数据
 
  public constructor(data: T | undefined = undefined) {
    // 初始化时 当前 ListNode 的前驱和后驱都设置为 null
    this.next = this.prev = null; // next 、prev 指向的是当前整个节点 而不是当前整个节点（一个 LinkNode）的 prev 或 next
    this.data = data;
  }
}
 
export class LinkList<T> {
  private _header: LinkNode<T>; // 记录头节点 用头节点作为双向循环节点的开始（如从头节点开始进行数据的录入、删除等）
  private _length: number;
 
  public constructor() {
    this._header = new LinkNode<T>();
    this._header.next = this._header; // 初始化时 头节点指向自身
    this._header.prev = this._header; // 初始化时 头节点指向自身
    this._length = 0; // 初始化时元素个数为 0 ，头节点作为哨兵节点不计算在内
  }
}

List 初始化时，头部节点状态图：

使用 push 方法后，即进行了数据的录入后，状态图为：

因此，双向循环链表的概念可以总结为：

• 双向：是指每个ListNode的后驱指针next指向下一个ListNode，每个ListNode的前驱指针prev指向前一个ListNode。可以通过通过next和prev指针进行从前到后或者从后到前的双向遍历操作。

• 循环：我们通过List的头节点和最后一个节点（数字为2的节点）可以了解到，头节点h的前驱指针指向最后一个节点（尾节点），而最后一个节点（尾节点）的后驱指针next指向头节点h，从而首尾相连，形成一个闭环。

• 当初始化时，List中的头节点h的后驱指针next和前驱指针prev都指向头节点

新建了 LinkList.ts 文件，文件内容如下：

export class LinkNode<T> {
  public next: LinkNode<T> | null; // 指向下一个节点，自引用，指向当前 ListNode 的后驱
  public prev: LinkNode<T> | null; // 指向前一个节点，自引用，指向当前 ListNode 的前驱
  public data: T | undefined; // 当前节点实际存储的数据，ListNode 所持有的数据
 
  public constructor(data: T | undefined = undefined) {
    // 初始化时 当前 ListNode 的前驱和后驱都设置为 null
    this.next = this.prev = null; // next 、prev 指向的是当前整个节点 而不是当前整个节点（一个 LinkNode）的 prev 或 next
    this.data = data;
  }
}
 
// 该结构表示一个双向循环链表，它包含了一个 ListNode<T> 的头节点（哨兵节点），该头节点（_header）在链表初始化时，其 next 和 prev 成员变量都指向自身(_header)
// 头节点和最后一个节点：头节点 _header 的前驱指针 prev 指向最后一个节点（尾节点），而最后一个节点（尾节点）的后驱指针 next 指向头节点 _header
// 从而首尾相连，形成一个闭环
export class LinkList<T> {
  private _header: LinkNode<T>; // 记录头节点 用头节点作为双向循环节点的开始（如从头节点开始进行数据的录入、删除等）
  private _length: number;
 
  public constructor() {
    this._header = new LinkNode();
    this._header.next = this._header; // 初始化时 头节点指向自身
    this._header.prev = this._header; // 初始化时 头节点指向自身
    this._length = 0; // 初始化时元素个数为 0 ，头节点作为哨兵节点不计算在内
  }
  // 获取 List 元素个数
  public get length(): number {
    // 如果当前 List 的 length 为 0，则说明是个空链表
    return this._length;
  }
 
  // 判断是否为空链表（当 this._length = 0 时 也可判断为空链表）
  public empty(): boolean {
    // 当头节点的后驱指针 next 指针指向头节点本身，说明是空链表
    return this._header.next === this._header;
  }
 
  // 在第一个参数 node 前插入一个节点 数据插入操作（在某个节点之前，插入一个节点）
  // 实现步骤为：
  // 1、在 参考节点前先插入一个节点即插入一个新节点
  // 2、将新节点的后驱指向参考节点
  // 3、将新节点的前驱指向参考节点原来的前驱   此时新节点的前驱、后驱指向就明确了
  // 4、修改 参考节点的前驱，使 参考节点的前驱指向新节点，此时参考节点的前驱、后驱指向也就明确了
  // 5、修改插入之前，参考节点的前驱指向的节点（上一个节点）的后驱需要修改为指向新插入的节点
  // 6、至此，新插入的节点的前后两个节点（参考节点的上一个节点，参考节点），这三个节点的前驱、后驱指向就都明确了
  private insertBefore(node: LinkNode<T>, data: T | undefined): LinkNode<T> {
    // 新建一个要插入的新节点
    let ret: LinkNode<T> = new LinkNode<T>(data);
    // 设置新节点的后驱指针和前驱指针
    ret.next = node; // 新节点的后驱即为当前参考节点
    ret.prev = node.prev; // 新节点的前驱 即为 当前参考节点原来的前驱
 
    // 设置好新节点的前后驱指针后
    // 还要调整 参考节点 的前后驱指针
 
    // 将当前参考节点的前一个节点的 后驱改为指向新节点
    if (node.prev !== null) {
      node.prev.next = ret;
    }
    // 将当前参考节点的前驱指向 新节点
    node.prev = ret;
 
    // 插入成功后 元素计数加 1
    this._length++;
    // 返回新插入的那个节点
    return ret;
  }
 
  // 获取尾节点
  public begin(): LinkNode<T> {
    if (this._header.next === null) {
      throw new Error("头节点的 next 指针必须不为 null");
    }
    // 若是链表不为空，则返回第一个节点
    // 若是链表为空， next 指向头节点本身，因此返回头节点
    // 绝对不可能返回 null 值
    return this._header.next;
  }
 
  // 获取头节点
  public end(): LinkNode<T> {
    return this._header;
  }
 
  // 查询是否包含某个值
  public contains(data: T): boolean {
    for (
      let link: LinkNode<T> | null = this._header.next;
      link !== null && link !== this._header;
      link = link.next
    ) {
      if (link.data !== undefined) {
        if (link.data === data) {
          return true;
        }
      }
    }
    return false;
  }
 
  // 双向遍历操作
  public forNext(cb: (data: T) => void): void {
    for (
      let link: LinkNode<T> | null = this._header.next;
      link !== null && link !== this._header;
      link = link.next
    ) {
      if (link.data !== undefined) {
        cb(link.data); // 调用回调函数
      }
    }
  }
  // 双向遍历操作
  public forPrev(cb: (data: T) => void): void {
    for (
      let link: LinkNode<T> | null = this._header.prev;
      link !== null && link !== this._header;
      link = link.prev
    ) {
      if (link.data !== undefined) {
        cb(link.data); // 调用回调函数
      }
    }
  }
 
  // 删除操作  删除操作是插入操作的逆操作
  public remove(node: LinkNode<T>): void {
    // 获得要删除的 节点 的后驱指针指向的节点
    let next: LinkNode<T> | null = node.next;
    // 获得要删除的 节点 的前驱指针指向的节点
    let prev: LinkNode<T> | null = node.prev;
 
    if (prev !== null) {
      // 修改 删除节点的上一个节点的 后驱为删除节点的后驱
      prev.next = next;
    }
    if (next !== null) {
      // 修改 删除节点的下一个节点的 前驱为删除节点的前驱
      next.prev = prev;
    }
    this._length--;
  }
 
  // 通过 insertBefore 和 remove 方法，结合 begin 和 end 以获得头节点和尾节点的功能，可以实现头尾插入、头尾删除的操作
  // 在尾部添加
  public push(data: T): void {
    this.insertBefore(this.end(), data);
  }
 
  // 在尾部移除
  public pop(): T | undefined {
    let prev: LinkNode<T> | null = this.end().prev;
    if (prev !== null) {
      let ret: T | undefined = prev.data;
      this.remove(prev);
      return ret;
    }
    return undefined;
  }
  // 在头部添加
  public unshift(data: T): void {
    this.insertBefore(this.begin(), data);
  }
  // 在头部移除
  public shift(): T | undefined {
    let ret: T | undefined = this.begin().data;
    this.remove(this.begin());
    return ret;
  }
}

​

插入方法的原理及示例过程：

假如已经有了 List，如下图：

现在要增加一个新节点3，让其添加到节点1的前面，效果如下图所示：

当调用 push 或 unshift 的 insertBefore 方法后，获得的效果如下图：

该方法实现的步骤可以拆分为以下几步：

（1）调整新创建的node3的后驱指针和前驱指针，代码如下：

 // 设置新节点node3的后驱指针和前驱指针
    node3.next = node1;          // node3.next设置为node1
    node3.prev = node1.prev;    // node1.prev是node0，因此node.prev被设置为
                                    node0了

（2）调整node0的后驱指针next，让其指向新创建的node3，代码如下：

    // 设置好新节点的前后驱指针后
    // 还要调整参考节点的前后驱指针
    if ( node1.prev ! == null )
    {
      // node1.prev在未修正前，是指向node0的，再用node0.next指针指向新创建的node3
      node1.prev.next = node3;
    }

（3）调整node1的前驱指针prev，让其指向新创建的node3。

    node1.prev = node3;

demo 运行效果如下：

项目代码版本对应地址

本章参考如下：

《TypeScript 图形渲染实战——基于WebGL的3D架构与实现》