JavaScript 中的计算机科学:双向链表

时间:2020-03-01 10:30:01 来源:新浪网 当前位置:小布丁线报 > 新车 > 手机阅读

在我之前的一篇文章(https://humanwhocodes.com/blog/2019/01/computer-science-in-javascript-linked-list/)中,讨论了在 JavaScript 中创建单向链表(如果您还未读过之前那篇文章,我建议您先去阅读一下)。单向链表由节点组成,每个节点都有一个指向列表中后一个节点的指针。单向链表的操作通常需要遍历整个列表,所以性能一般较差。而在链表中每个节点上添加指向前一个节点的指针可以提高其性能。每个节点有分别指向前一个节点和后一个节点的指针的链表就称为双向链表。

双向链表的设计

与单向链表一样,双向链表也是由一系列节点组成。每一个节点包含数据域、指向后一个节点的指针以及指向前一个节点的指针。这里看一个在 JavaScript 中简单应用的例子:

  1. class DoublyLinkedListNode {

  2. constructor(data) {

  3. this.data = data;

  4. this.next = null;

  5. this.previous = null;

  6. }

  7. }

DoublyLinkedListNode 类中,属性 data 包含链表项存储的值,属性 next 是指向列表中后一项的指针,而属性 previous 是指向列表中前一项的指针。 nextprevious 指针初始都为 null,因为在类实例化时后一个节点和前一个节点都还未知。您可以像下面这样使用 DoublyLinkedListNode 类创建双向链表:

  1. // create the first node

  2. const head = new DoublyLinkedListNode(12);


  3. // add a second node

  4. const secondNode = new DoublyLinkedListNode(99);

  5. head.next = secondNode;

  6. secondNode.previous = head;


  7. // add a third node

  8. const thirdNode = new DoublyLinkedListNode(37);

  9. secondNode.next = thirdNode;

  10. thirdNode.previous = secondNode;


  11. const tail = thirdNode;

同样与单向链表一样,双向链表中的第一个节点称为头节点,然后分别给后面的第二个和第三个节点设置 nextprevious 。这样就生成了如下图所示的数据结构:

您可以访问每个节点上的 next ,以与单向链表相同的方式遍历双向链表,例如:

  1. let current = head;


  2. while (current !== null) {

  3. console.log(current.data);

  4. current = current.next;

  5. }

双向链表通常也跟踪列表中最后一个节点,这个节点被称作尾节点。尾节点更便于新节点的插入以及从尾节点开始访问 previous 来实现链表逆向查找。执行下面的代码,控制台依次输出双向链表反向遍历之后的每一个值:

  1. let current = tail;


  2. while (current !== null) {

  3. console.log(current.data);

  4. current = current.previous;

  5. }

双向链表相较于单向链表的一个优势在于可以双向遍历列表。

DoublyLinkedList 类

与单链表一样,双向链表中节点的操作最好封装在一个类中。这里有一个简单的例子:

  1. const head = Symbol("head");

  2. const tail = Symbol("tail");


  3. class DoublyLinkedList {

  4. constructor() {

  5. this[head] = null;

  6. this[tail] = null;

  7. }

  8. }

双向链表 DoublyLinkedList 类包含与链表中数据进行交互的方法。属性 headtail 分别用于定位列表中的第一个和最后一个节点。与单链表一样, headtail 不推荐在类外访问。

双向链表中数据的添加

将元素添加到双向链表和添加到单向链表非常类似。在这两种数据结构中,都需要先找到列表中最后一个节点,然后在其后面添加一个新节点。在单向链表中,必须要遍历整个列表以定位最后一个节点,而在双向链表中,直接使用 this[tail] 定位最后一个节点。以下是 DoublyLinkedList 类的 add() 方法:

  1. class DoublyLinkedList {


  2. constructor() {

  3. this[head] = null;

  4. this[tail] = null;

  5. }


  6. 上一篇今夏最火的维希格纹,这样穿才够时髦

    下一篇博伊刀的前世今生,战术刀之王,美国特种兵的精神象征

相关文章:

新车本月排行

新车精选