Typescript 数据结构：链表

在今天的 Typescript 101 课程中，我们将继续探讨数据结构及其在 Typescript 中的实现。今天的主题是链表。我们将深入讲解如何创建通用、可复用的链表，并探讨 JS 中的递归。欢迎大家加入，一起来学习吧！

什么是链表？

根据维基百科：
在计算机科学中，链表是数据元素的线性集合，其顺序并非由其在内存中的物理位置决定。相反，每个元素都指向下一个元素。它是一种由一系列节点组成的数据结构，这些节点共同构成一个序列。

链表主要有两种类型：

单链表：元素仅引用下一个元素的列表
双向链表：元素链接到下一个元素和前一个元素的列表

今天我们来重点讲一下双向链表的实现。

节点

链表中的每个元素都是一个节点。我们Node先创建一个类。

class Node<T> {
  public next: Node<T> | null = null;
  public prev: Node<T> | null = null;
  constructor(public data: T) {}
}

由于我们正在处理双向链表，因此我们的Node有next和prev字段，它们指向另一个节点或null。此外，还Node包含我们的数据，它具有泛型类型T。

链表的方法

链表的最终版本如下所示。

interface ILinkedList<T> {
  insertInBegin(data: T): Node<T>;
  insertAtEnd(data: T): Node<T>;
  deleteNode(node: Node<T>): void;
  traverse(): T[];
  size(): number;
  search(comparator: (data: T) => boolean): Node<T> | null;
}

插入

我们将从实现插入功能开始。向链表插入数据有多种方法。我们可以在某个节点之后或之前插入数据，或者根据索引插入数据。但在本例中，我们将重点介绍更通用的情况——在链表的开头或结尾插入节点。

插入开始

class LinkedList<T> implements ILinkedList<T> {
  private head: Node<T> | null = null;

  public insertInBegin(data: T): Node<T> {
    const node = new Node(data);
    if (!this.head) {
      this.head = node;
    } else {
      this.head.prev = node;
      node.next = this.head;
      this.head = node;
    }
    return node;
  }
}

这里我们处理两种情况：

列表为空 - 在这种情况下，新添加的元素将成为列表的头部。
列表不为空 - 在这种情况下，新添加的元素将成为列表的头部，并且我们更新前一个头部的链接。

1. list Before insertion:
A <-> B <-> ...
2. list after insertion:
New_Node <-> A <-> B <-> ...

插入到结束处

class LinkedList<T> implements ILinkedList<T> {
  private head: Node<T> | null = null;

  public insertAtEnd(data: T): Node<T> {
    const node = new Node(data);
    if (!this.head) {
      this.head = node;
    } else {
      const getLast = (node: Node<T>): Node<T> => {
        return node.next ? getLast(node.next) : node;
      };

      const lastNode = getLast(this.head);
      node.prev = lastNode;
      lastNode.next = node;
    }
    return node;
  }
}

最终的插入操作会比较棘手，因为我们需要先找到最后一个节点，所以让我们仔细看看发生了什么。与上一种方法类似，我们有两种情况：

列表为空 - 在这种情况下，新添加的元素将成为列表的头部。
列表不为空 - 我们搜索最后一个节点并将其next引用设置为新添加的元素。

A <-> B <-> New_Node

为了找到最后一个节点，我们使用递归函数，该函数遍历列表并返回没有对该next节点的引用的节点：

const getLast = (node: Node<T>): Node<T> => {
  return node.next ? getLast(node.next) : node;
};

删除

删除节点非常简单。我们只需要更新下一个和上一个元素的引用即可。如果该节点是当前头节点，则需要移动链表。

class LinkedList<T> implements ILinkedList<T> {
  private head: Node<T> | null = null;

  public deleteNode(node: Node<T>): void {
    if (!node.prev) {
      this.head = node.next;
    } else {
      const prevNode = node.prev;
      prevNode.next = node.next;
    }
  }
}

遍历

traverse方法将遍历链表并将所有节点返回为 JS 数组。对于此方法，我们还将使用递归函数。

class LinkedList<T> implements ILinkedList<T> {
  private head: Node<T> | null = null;

  public traverse(): T[] {
    const array: T[] = [];
    if (!this.head) {
      return array;
    }

    const addToArray = (node: Node<T>): T[] => {
      array.push(node.data);
      return node.next ? addToArray(node.next) : array;
    };
    return addToArray(this.head);
  }
}

while当我们在开始迭代之前不知道列表的大小时，递归函数可以很好地替代循环来完成遍历等任务。

尺寸

为了跟踪大小，我们可以将当前节点数存储在类字段中，并在每次添加或删除节点时更新它。但是，在这个例子中，我将简单地使用traverse函数并返回数组长度：

...
  public size(): number {
    return this.traverse().length;
  }
...

搜索

当你考虑该类的最终使用者时LinkedList，她可能会对根据某些数据属性搜索节点感兴趣。为了使我们的search方法尽可能灵活地使用，我们将使用控制反转。使用者可以传递一个回调函数，该函数将实现所需的搜索条件：

class LinkedList<T> implements ILinkedList<T> {
  private head: Node<T> | null = null;

  public search(comparator: (data: T) => boolean): Node<T> | null {
    const checkNext = (node: Node<T>): Node<T> | null => {
      if (comparator(node.data)) {
        return node;
      }
      return node.next ? checkNext(node.next) : null;
    };

    return this.head ? checkNext(this.head) : null;
  }
}

全面实施

class LinkedList<T> implements ILinkedList<T> {
  private head: Node<T> | null = null;

  public insertAtEnd(data: T): Node<T> {
    const node = new Node(data);
    if (!this.head) {
      this.head = node;
    } else {
      const getLast = (node: Node<T>): Node<T> => {
        return node.next ? getLast(node.next) : node;
      };

      const lastNode = getLast(this.head);
      node.prev = lastNode;
      lastNode.next = node;
    }
    return node;
  }

  public insertInBegin(data: T): Node<T> {
    const node = new Node(data);
    if (!this.head) {
      this.head = node;
    } else {
      this.head.prev = node;
      node.next = this.head;
      this.head = node;
    }
    return node;
  }

  public deleteNode(node: Node<T>): void {
    if (!node.prev) {
      this.head = node.next;
    } else {
      const prevNode = node.prev;
      prevNode.next = node.next;
    }
  }

  public search(comparator: (data: T) => boolean): Node<T> | null {
    const checkNext = (node: Node<T>): Node<T> | null => {
      if (comparator(node.data)) {
        return node;
      }
      return node.next ? checkNext(node.next) : null;
    };

    return this.head ? checkNext(this.head) : null;
  }

  public traverse(): T[] {
    const array: T[] = [];
    if (!this.head) {
      return array;
    }

    const addToArray = (node: Node<T>): T[] => {
      array.push(node.data);
      return node.next ? addToArray(node.next) : array;
    };
    return addToArray(this.head);
  }

  public size(): number {
    return this.traverse().length;
  }
}

interface Post {
  title: string;
}
const linkedList = new LinkedList<Post>();

linkedList.traverse() // [];

linkedList.insertAtEnd({ title: "Post A" });
linkedList.insertAtEnd({ title: "Post B" });
linkedList.insertInBegin({ title: "Post C" });
linkedList.insertInBegin({ title: "Post D" });

linkedList.traverse() // [{ title : "Post D" }, { title : "Post C" }, { title : "Post A" }, { title : "Post B" }];
linkedList.search(({ title }) => title === "Post A") // Node { data: { title: "Post A" }, prev: Node, next: Node};

概括

今天我们讨论了链表，希望对你有所帮助。如果你想学习 Typescript 的具体知识，或者愿意提出下一个数据结构，请留言，我们一起讨论。

如果您喜欢我的帖子，请传播并在 Twitter 上关注我🚀，以获取有关 Web 开发的更多精彩内容。

文章来源：https://dev.to/glebirovich/typescript-data-structs-linked-list-3o8i

Typescript 数据结构：链表

Typescript 数据结构：链表

目录

什么是链表？

节点

链表的方法

插入

插入开始

插入到结束处

删除

遍历

尺寸

搜索

全面实施

概括