DSA LinkedList

使用链接列表

关键概念

• 链接列表是类似于数组的线性数据结构。但是，与数组不同，元素未存储在特定的内存位置或索引中。而是每个元素都是一个单独的对象，其中包含指针或指向该列表中下一个对象的链接。
• 节点是列表中每个元素的名称。它们包含两个项目：存储的数据和下一个节点的链接。数据可以是任何有效的数据类型。
• 头是链接列表的切入点。头是对链接列表中第一个节点的引用。列表上的最后一个节点指向null。如果列表为空，则头为空引用。

利弊

• 可以轻松地从链接列表中删除或添加节点，而无需重新组织整个数据结构。这是比阵列具有的优势之一。
• 链接列表中的搜索操作很慢。与数组不同，不允许随机访问数据元素。从第一个节点开始依次访问节点。
• 由于指针的存储，它使用的是比数组更多的内存。

链接列表的类型

• 单链接列表- 每个节点仅包含一个指向下一个节点的指针。
• 双链接列表- 每个节点包含两个指针，一个指向下一个节点的指针和指向上一个节点的指针。
• 循环链接列表- 循环链接列表是链接列表的变体，其中最后一个节点指向第一个节点或其他节点，从而形成循环。

JavaScript代码示例

列表节点类

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

链接列表类

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

创建链接列表

 let node1 = new ListNode(2)
let node2 = new ListNode(5)
node1.next = node2
let list = new LinkedList(node1)

console.log(list.head.next.data) //returns 5

链接列表方法

• 大小- 此方法返回链接列表中存在的节点数量。

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

• 显示- 此方法显示列表中的所有节点。

 const ListFunctions = {
  display: (linkedList) => {
    items = [];

    if (linkedList.head === null) {
      return "The list is empty";
    } else {

      let currNode = linkedList.head;

      while (currNode.next !== null) {
        items.push(currNode.data);
        currNode = currNode.next;
      }

      items.push(currNode.data);
    }

    return `Linked List Items: ${items.join("->")}`;
  }

• ISEMPTY-此方法检查是否在不使用size（）方法的情况下查看列表是否为空。

  isEmpty: (linkedList) => {
    if (linkedList.head === null) {
      return `This list is empty`;
    }
    return `There are items in this list`;
  }

• 查找- 此方法在列表中找到一个节点。

  find(item) {
    let currNode = this.head;

    if (!this.head) {
      return null;
    }

    while (currNode.data !== item) {
      if (currNode.next === null) {
        return null;
      } else {
        currNode = currNode.next;
      }
    }
    return currNode;
  }
}

• 清除- 此方法清空列表。

 clear() {
    this.head = null;
}

• 删除- 此方法从列表中删除节点。

  remove(item) {
    if (!this.head) {
      return null;
    }

    if (this.head.data === item) {
      this.head = this.head.next;
      return;
    }

    let currNode = this.head;
    let previousNode = this.head;

    while (currNode !== null && currNode.data !== item) {
      previousNode = currNode;
      currNode = currNode.next;
    }

    if (currNode === null) {
      return;
    }
    previousNode.next = currNode.next;
  }

• 首先插入- 此方法将节点插入链接列表的第一个位置。

 insertFirst(item) {
    this.head = new _Node(item, this.head);
  }

• Insertlast-此方法将节点插入链接列表的最后一个位置。

  insertLast(item) {
    if (this.head === null) {
      this.insertFirst(item);
    } else {
      let tempNode = this.head;
      while (tempNode.next !== null) {
        tempNode = tempNode.next;
      }
      tempNode.next = new _Node(item, null);
    }
  }

• 插入之前- 此方法在链接列表中的目标节点之前插入一个节点。

 insertBefore(item, key) {
    if (!this.head) {
      return;
    }

    if (this.head.data === key) {
      this.insertFirst(item);
      return;
    }

    let currNode = this.head;
    let previousNode = this.head;

    while (currNode !== null && currNode.data !== key) {
      previousNode = currNode;
      currNode = currNode.next;
    }

    if (currNode === null) {
      console.log(`key value not found`);
      return;
    }

    previousNode.next = new _Node(item, currNode);
  }

• insertafter-此方法在链接列表中插入一个目标节点后的节点。

  insertAfter(item, key) {

    if (!this.head) {
      return;
    }

    if (this.head.data === key) {
      this.insertFirst(item);
      return;
    }

    let currNode = this.head;
    let nextNode = this.head;

    while (currNode !== null && currNode.data !== key) {
      currNode = nextNode;
      nextNode = nextNode.next;
    }

    if (currNode === null) {
      console.log(`key value not found`);
      return;
    }

    currNode.next = new _Node(item, nextNode);
  }

• getlast-此方法返回链接列表的最后一个节点。

 getLast() {
    let lastNode = this.head;
    if (lastNode) {
        while (lastNode.next) {
            lastNode = lastNode.next
        }
    }
    return lastNode
}

• getFirst-此方法返回链接列表的第一个节点。

 getFirst() {
    return this.head;
}

• FindPrevious-此方法在您在链接列表中寻找的项目之前返回上一个节点。

  findPrevious: (linkedList, key) => {

    if (linkedList.head === null) {
      return null;
    }
    let prevNode;
    let currNode = linkedList.head;

    while (currNode.data !== key) {
      prevNode = currNode;
      currNode = currNode.next;
    }

    return `The previous node is ${prevNode.data}`;
  }

演习概述

在这些演习中，您将练习创建一个链接的列表，实施其核心和一些补充操作。您还将使用链接列表来解决面试问题。不要忘记评估这些练习中的每一个。通过说明1个或更多样本输入和输出来开始每个问题。

1。创建一个链接列表类

从头开始编写一个链接的列表类和这些核心功能（插入First，insertlast，remove，find）。

2。创建一个单独的链接列表

• 写一个函数主。在功能中，使用上面的链接列表类，创建一个带有名称SLL的链接列表，然后将以下项目添加到您的链接列表中：Apollo，Boomer，Helo，Helo，Husker，Starbuck。
• 将tauhida添加到列表中。
• 从列表中删除松鼠。
• 在类中实现一个称为insertbefore（）的函数，该函数在包含密钥的给定节点之前插入新节点。
• 在类中实现一个称为insertafter（）的函数，该函数在包含密钥的节点后插入新节点。
• 实现一个称为insertat（）的函数，该函数将项目插入链接列表中的特定位置。
• 使用您的insertbefore（）函数在Boomer之前添加Athena。
• 使用insertafter（）方法添加HELO后添加热狗。
• 使用insertat（）方法在列表的第三位置插入KAT。
• 从列表中删除Tauhida。

3。链接列表的补充功能

在您的链接列表类中实现以下功能。请注意，这些应该是免费功能，而不是链接列表类的方法，因此在链接列表类中实现它们。使用练习1中创建的列表测试每个功能。

• 显示：显示链接列表
• 尺寸：返回链接列表的大小
• ISEMPTY：查找列表是否为空（不使用size（）函数）
• Findprevious：在您要寻找的项目之前找到节点
• Findlast：返回链接列表中的最后一个节点

4。神秘程序

分析以下功能（不在IDE中运行它）以确定要解决的问题。该算法的时间复杂性是多少？

 function WhatDoesThisProgramDo(lst) {
    let current = lst.head;
    while (current !== null) {
        let newNode = current;
        while (newNode.next !== null) {
            if (newNode.next.value === current.value) {
                newNode.next = newNode.next.next;
            }
            else {
                newNode = newNode.next;
            }
        }
        current = current.next;
    }
}

5。反向列表

编写算法以扭转链接列表。算法的时间复杂性应为线性（O（n））。在此练习中，请注意，我们不要求您仅在反向中打印链接列表，也不会使用另一个链接列表以相反的顺序存储该值。您的程序应扭转给定单链接列表的方向。换句话说，所有指针都应向后指向。奖励：使用递归和迭代算法解决此问题。

6.从末端第三

编写一个算法以从链接列表的末尾找到第三元素。请注意，您可能很想在链接列表类中添加长度属性。长度属性不是链接列表的典型属性，因此不要对提供给您的链接列表类进行任何修改。

7。清单中间

编写算法以找到链接列表的中间元素。请注意，您可能很想在链接列表类中添加长度属性。长度属性不是链接列表的典型属性，因此不要对提供给您的链接列表类进行任何修改。此外，使用size（）函数找到链接列表的大小，然后将其除以一半，将找不到链接列表的正确中间。因此，不要使用这两种方法。

8。列表中的循环

编写一种算法以查找链接列表是否具有周期（即，列表中的节点是否具有下一个值指向列表中的一个节点的下一个值）。对于此练习，创建一个名称Cyclelist的链接列表。请确保将节点插入列表中，以使其具有一个周期。然后使用Cyclelist功能测试您的程序。

9。双重链接列表

实现双重链接列表。双链接列表的主要功能将是插入（首先，最后，之前，之后和at），删除并查找。编写一个函数aintll，并在其中创建双重链接的列表DLL，然后添加以下项目：Aquaria，caprica，gemenon，picon，picon，sagittaron。

• 将牛龙添加到列表中
• 从列表中删除picon

10。反向DLL

给定上面的双重链接列表，编写一个逆转双重链接列表的程序。这种实现与逆转单链接列表有何不同？