墨滴

源墨

V1

2023/05/04阅读：18主题：萌绿

前端需要掌握的数据结构之-链表

什么是链表？

链表是一种常见的数据结构，它由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。链表的特点是可以动态地增加或删除节点，而不需要移动其他节点。

链表分为单向链表和双向链表。单向链表每个节点只有一个指向下一个节点的指针，而双向链表每个节点有一个指向下一个节点和一个指向上一个节点的指针。在本教程中，我们将讨论单向链表。

链表相关的图示

如何实现链表？

我们可以使用js来实现链表。首先，我们需要定义一个节点类，它包含一个数据元素和一个指向下一个节点的指针。

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

接下来，我们可以定义一个链表类，它包含一个头节点和一个尾节点。头节点是链表中第一个节点，而尾节点是链表中最后一个节点。

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }
}

链表类还应该包含一些方法，例如添加节点、删除节点、查找节点等。

如何添加节点？

我们可以使用addNode方法来添加节点。如果链表为空，我们将新节点设置为头节点和尾节点。否则，我们将新节点添加到链表的末尾。

class LinkedList {
  // ...
  addNode(data) {
    const node = new Node(data);
    if (!this.head) {
      this.head = node;
      this.tail = node;
    } else {
      this.tail.next = node;
      this.tail = node;
    }
  }
}

如何删除节点？

我们可以使用removeNode方法来删除节点。首先，我们需要找到要删除的节点。如果要删除的节点是头节点，我们将下一个节点设置为新的头节点。否则，我们需要找到要删除节点的前一个节点，并将它的next指针指向要删除节点的下一个节点。

class LinkedList {
  // ...
  removeNode(data) {
    if (!this.head) {
      return;
    }
    if (this.head.data ===== data) {
      this.head = this.head.next;
      return;
    }
    let node = this.head;
    while (node.next) {
      if (node.next.data ===== data) {
        node.next = node.next.next;
        return;
      }
      node = node.next;
    }
  }
}

如何查找节点？

我们可以使用findNode方法来查找节点。我们可以使用一个循环来遍历链表中的所有节点，直到找到包含指定数据的节点为止。

class LinkedList {
  // ...
  findNode(data) {
    let node = this.head;
    while (node) {
      if (node.data ===== data) {
        return node;
      }
      node = node.next;
    }
    return null;
  }
}

如何打印链表？

我们可以使用printList方法来打印链表。我们可以使用一个循环来遍历链表中的所有节点，并将它们的数据元素打印出来。

class LinkedList {
  // ...
  printList() {
    let node = this.head;
    while (node) {
      console.log(node.data);
      node = node.next;
    }
  }
}

如何使用链表？

现在我们已经实现了链表类，我们可以使用它来创建链表并执行操作。

const list = new LinkedList();
list.addNode(1);
list.addNode(2);
list.addNode(3);
list.printList(); // 输出1, 2, 3
list.removeNode(2);
list.printList(); // 输出1, 3
const node = list.findNode(3);
console.log(node.data); // 输出3

总结

  • 链表是一种常见的数据结构，它由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。
  • 在js中，我们可以使用类来实现链表，并包含添加节点、删除节点、查找节点、打印链表等方法。
  • 链表可以动态地增加或删除节点，而不需要移动其他节点，因此它非常适合用于需要频繁插入或删除元素的情况。

常考算法题

  1. 反转链表：给定一个单向链表，将其反转。

  2. 链表中倒数第k个节点：给定一个单向链表和一个整数k，找出链表中倒数第k个节点。

  3. 合并两个有序链表：给定两个有序链表，将它们合并成一个有序链表。

  4. 删除链表中的重复元素：给定一个单向链表，删除其中重复的元素，使得每个元素只出现一次。

  5. 判断链表是否有环：给定一个单向链表，判断其中是否存在环。

这些问题都是经典的链表问题，可以通过遍历、双指针、递归等方式解决。在解决这些问题时，需要注意链表的特点，如指针的指向、链表长度、链表是否有环等。

关注我不迷路

分类：

前端

标签：

数据结构与算法

作者介绍

源墨
V1