TypeScript数据结构链表结构 LinkedList教程及面试

TypeScript数据结构链表结构 LinkedList教程及面试攻略

在程序设计中，链表是一种重要的数据结构，它可以用来存储一系列数据元素，并提供一些类似于数组的操作。 TypeScript是一种JavaScript的超集，它提供了更加丰富的类型系统，使得我们可以更好的使用链表这种数据结构。

本文将会讲解使用TypeScript实现常见的链表结构，并且提供一些关于LinkedList类型的常见面试题目。在讲解具体实现之前，我们先来了解链表的基础知识。

什么是链表？

链表是一种线性数据结构。它由多个节点组成，每个节点包含两个属性：数据和指向下一个节点的指针。通过这种指针的方式，链表将多个节点串联起来，从而形成一个有序的序列。

链表和数组有什么区别？

相比于数组，链表一般不支持随机访问。也就是说，我们无法像数组一样通过下标访问单个元素，而是要从头开始依次遍历节点。

但是，链表有一个优点，那就是支持高效的插入与删除操作。因为链表只需要改变相关的指针即可完成插入和删除操作，而不需要像数组一样将后面的元素向后移位。

实现LinkedList

在TypeScript中，我们可以使用class来实现链表。下面是实现一个简单的单向链表的代码：

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

class LinkedList<T> {
  public head: ListNode<T> | null = null;

  push(data: T) {
    const node = new ListNode(data);
    if (!this.head) {
      this.head = node;
      return;
    }

    let tail = this.head;
    while(tail.next) {
      tail = tail.next;
    }
    tail.next = node;
  }

  insert(data: T, index: number) {
    if (!this.head || index === 0) {
      const newHead = new ListNode(data);
      newHead.next = this.head;
      this.head = newHead;
      return;
    }

    let listNode = this.head;
    while(listNode.next && index > 1) {
      listNode = listNode.next;
      index--;
    }
    const newNode = new ListNode(data);
    newNode.next = listNode.next;
    listNode.next = newNode;
  }

  get(index: number): T|undefined {
    if (!this.head) {
      return undefined;
    }

    let listNode = this.head;
    while(listNode && index > 0) {
      listNode = listNode.next;
      index--;
    }

    if (listNode) {
      return listNode.data;
    }

    return undefined;
  }

  delete(index: number) {
    if (!this.head) {
      return;
    }

    if (index === 0) {
      this.head = this.head.next;
      return;
    }

    let listNode = this.head;

    while(listNode.next && index > 1) {
      listNode = listNode.next;
      index--;
    }

    if (listNode.next) {
      listNode.next = listNode.next.next;
    }
  }

  toArray(): T[] {
    const array = [];
    let listNode = this.head;
    while(listNode) {
      array.push(listNode.data);
      listNode = listNode.next;
    }
    return array;
  }

  size(): number {
    let count = 0;
    let listNode = this.head;
    while(listNode) {
      count++;
      listNode = listNode.next;
    }
    return count;
  }
}

如上面的代码所示，LinkedList类定义了4个常见的操作函数：push、insert、get、delete，以及两个能够获取链表大小和导出链表数组的函数。

面试题目攻略

面试题目1

如何找到链表中间的节点？

解决思路：定义两个指针，两个指针的速度不同，从链表头部开始同时向后移动，当速度较快的指针到达链表末尾时，速度较慢的指针就处于链表中间节点的位置。

function findMiddle<T>(list: LinkedList<T>): ListNode<T> | null {
  let slow = list.head;
  let fast = list.head;
  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next!.next;
  }
  return slow;
}

面试题目2

如何检测链表是否有环？

解决思路：定义两个指针，两个指针的速度不同，从链表头部开始同时向后移动，如果两个指针相遇，那么链表就有环。

function hasCycle<T>(list: LinkedList<T>): boolean {
  let slow = list.head;
  let fast = list.head;

  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next!.next;

    if (slow === fast) {
      return true;
    }
  }

  return false;
}

以上就是LinkedList的基础教程和面试攻略的详细说明。如果想要深入了解链表这一数据结构，可以继续学习双向链表、循环链表等其他类型的链表。