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

給定上面的雙重鏈接列表，編寫一個逆轉雙重鏈接列表的程序。這種實現與逆轉單鏈接列表有何不同？