摘要：相反，雙向鏈表具有指向其前后元素的節(jié)點。另外，可以對鏈表進行排序。這個實用程序方法用于打印鏈表中的節(jié)點，僅用于調試目的。第行將更新為，這是從鏈表中彈出最后一個元素的行為。如果鏈表為空，則返回。

單鏈表是表示一系列節(jié)點的數據結構，其中每個節(jié)點指向鏈表中的下一個節(jié)點。 相反，雙向鏈表具有指向其前后元素的節(jié)點。

與數組不同，鏈表不提供對鏈表表中特定索引訪問。 因此，如果需要鏈表表中的第三個元素，則必須遍歷第一個和第二個節(jié)點才能到得到它。

鏈表的一個好處是能夠在固定的時間內從鏈表的開頭和結尾添加和刪除項。

這些都是在技術面試中經常被問到的數據結構，所以讓我們開始吧。

另外，可以對鏈表進行排序。 這意味著當每個節(jié)點添加到鏈表中時，它將被放置在相對于其他節(jié)點的適當位置。

鏈表只是一系列節(jié)點，所以讓我們從 Node 對象開始。

一個節(jié)點有兩條信息

指向鏈表中下一項的指針或引用(對于單鏈表)

節(jié)點的值

對于我們的節(jié)點，我們只需要創(chuàng)建一個函數，該函數接受一個值，并返回一個具有上面兩個信息的對象:指向下一個節(jié)點的指針和該節(jié)點的值。

注意，我們可以只聲明 value 而不是 value: value。這是因為變量名稱相同(ES6 語法)

現(xiàn)在，讓我們深入研究 NodeList 類,以下就是節(jié)點鏈表樣子。

節(jié)點鏈表將包含五個方法：

push(value): 將值添加到鏈表的末尾

pop() ：彈出鏈表中的最后一個值

get(index)：返回給定索引中的項

delete(index)：從給定索引中刪除項

isEmpty(): 返回一個布爾值，指示鏈表是否為空

printList():不是鏈表的原生方法，它將打印出我們的鏈表，主要用于調試

構造函數中需要三個信息:

head:對鏈表開頭節(jié)點的引用

tail:對鏈表末尾節(jié)點的引用

length:鏈表中有多少節(jié)點

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

isEmpty() 方法是一個幫助函數，如果鏈表為空，則返回true。

isEmpty() {
  return this.length === 0;
}

這個實用程序方法用于打印鏈表中的節(jié)點，僅用于調試目的。

printList () {
  const nodes = [];
  let current = this.head;
  while (current) {
    nodes.push(current.value);
    current = current.next;
  }
  return nodes.join(" -> ");
}

在添加新節(jié)點之前，push 方法需要檢查鏈表是否為空。如何知道鏈表是否為空? 兩種方式：

isEmpty()方法返回true(鏈表的長度為零)

head 指針為空

對于這個例子，我們使用 head是否為null來判斷鏈表是否為空。

如果鏈表中沒有項，我們可以簡單地將head 指針和tail指針都設置為新節(jié)點并更新鏈表的長度。

if (this.head === null) {
  this.head = node;
  this.tail = node;
  this.length++;
  return node;
}

如果鏈表不是空的，我們必須執(zhí)行以下操作：

將tail.next 指向新節(jié)點

將 tail 指向新節(jié)點

更新鏈表長度

以下是完整的 push 方法：

push(value) {
  const node = Node(value);
  // The list is empty
  if (this.head === null) {
    this.head = node;
    this.tail = node;
    this.length++;
    return node;
  }
  this.tail.next = node;
  this.tail = node;
  this.length++;
}

在刪除鏈表中的最后一項之前，我們的pop方法需要檢查以下兩項內容：

檢查鏈表是否為空

檢查鏈表中是否只有一項

可以使用isEmpty方法檢查鏈表是否包含節(jié)點。

if (this.isEmpty()) {
  return null;
}

我們如何知道鏈表中只有一個節(jié)點? 如果 head 和tail 指向同一個節(jié)點。但是在這種情況下我們需要做什么呢? 刪除唯一的節(jié)點意味著我們實際上要重新設置鏈表。

if (this.head === this.tail) {
  this.head = null;
  this.tail = null;
  this.length--;
  return nodeToRemove;
}

如果鏈表中有多個元素，我們可以執(zhí)行以下操作

當鏈表中有節(jié)點時，
 如果鏈表中的下一個節(jié)點是 tail 
   更新 tail 指向當前節(jié)點
   當前節(jié)點設置為 null，
   更新鏈表的長度
   返回前一個 tail 元素

它看起來像這樣:

    1  let currentNode = this.head;
    2  let secondToLastNode;
    3
    4  //從前面開始并迭代直到找到倒數第二個節(jié)點
    5 
    6  while (currentNode) {
    7    if (currentNode.next === this.tail) {
    8      // 將第二個節(jié)點的指針移動到最后一個節(jié)點
    9      secondToLastNode = currentNode;
   10      break;
   11    }
   12    currentNode = currentNode.next;
   13  }
   14  // 彈出該節(jié)點
   15  secondToLastNode.next = null;
   16  // 將 tail 移動到倒數第二個節(jié)點
   17  this.tail = secondToLastNode;
   18  this.length--;
   19 
   20  // 初始化 this.tail
   21   return nodeToRemove;

如果你無法想象這一點，那么讓我們來看看它。

第6-10行:如果鏈表中的下一個節(jié)點是最后一個項，那么這個當前項目就是新tail，因此我們需要保存它的引用。

if (currentNode.next === this.tail) {
  secondToLastNode = currentNode;
}

第15行：將secondToLastNode更新為null，這是從鏈表中“彈出”最后一個元素的行為。

secondToLastNode.next = null;

第17行:更新tail以指向secondToLastNode。

this.tail = secondToLastNode;

第18行：更新鏈表的長度，因為我們剛刪除了一個節(jié)點。

第21行:返回剛剛彈出的節(jié)點。

以下是完整的pop方法：

pop() {
  if (this.isEmpty()) {
    return null;
  }
  const nodeToRemove = this.tail;
  // There"s only one node!
  if (this.head === this.tail) {
    this.head = null;
    this.tail = null;
    this.length--;
    return nodeToRemove;
  }

  let currentNode = this.head;
  let secondToLastNode;

  // Start at the front and iterate until
  // we find the second to last node
  while (currentNode) {
    if (currentNode.next === this.tail) {
      // Move the pointer for the second to last node
      secondToLastNode = currentNode;
      break;
    }
    currentNode = currentNode.next;
  }
  // Pop off that node
  secondToLastNode.next = null;
  // Move the tail to the second to last node
  this.tail = secondToLastNode;
  this.length--;

  // Initialized to this.tail
  return nodeToRemove;
}

get方法必須檢查三種情況：

索引是否超出了鏈表的范圍

鏈表是否為空

查詢第一個元素

如果鏈表中不存在請求的索引，則返回null。

// Index is outside the bounds of the list
if (index < 0 || index > this.length) {
  return null;
}

如果鏈表為空，則返回null。你可以把這些if語句組合起來，但是為了保持清晰，我把它們分開了。

if (this.isEmpty()) {
  return null;
}

如果我們請求第一個元素，返回 head。

// We"re at the head!
if (index === 0 )  {
  return this.head;
}

否則，我們只是一個一個地遍歷鏈表，直到找到要查找的索引。

let current = this.head;
let iterator =  0;

while (iterator < index) {
  iterator++;
  current = current.next;
}

return current;

以下是完整的get(index)方法：

get(index) {
// Index is outside the bounds of the list
if (index < 0 || index > this.length) {
  return null;
}

if (this.isEmpty()) {
  return null;
}

// We"re at the head!
if (index === 0 )  {
  return this.head;
}

let current = this.head;
let iterator =  0;

while (iterator < index) {
  iterator++;
  current = current.next;
}

return current;
}

delete方法需要考慮到三個地方

刪除的索引超出了鏈表的范圍

鏈表是否為空

我們想要刪除 head

如果鏈表中不存在我們要刪除的索引，則返回 null。

// Index is outside the bounds of the list
if (index < 0 || index > this.length) {
  return null;
}

如果我們想刪除head，將head設置為鏈表中的下一個值，減小長度，并返回我們剛剛刪除的值。

if (index === 0) {
  const nodeToDelete = this.head;
  this.head = this.head.next;
  this.length--;
  return nodeToDelete;
}

如果以上都 不是，則刪除節(jié)點的邏輯如下：

循環(huán)遍歷正在查找的索引

   增加索引值

   將前一個和當前指針向上移動一個

將當前值保存為要刪除的節(jié)點

更新上一個節(jié)點的指針以指向下一個節(jié)點

如果下一個值為 `null`

   將`tail`設置為新的最后一個節(jié)點

更新鏈表長度

返回已刪除的節(jié)點

如果你需要可視化圖片，請參考Pop部分中的圖表。

以下是完整的 delete 方法：

delete(index) {
   // Index is outside the bounds of the list
  if (index < 0 || index > this.length - 1) {
    return null;
  }

  if (this.isEmpty()) {
    return null;
  }

  if (index === 0) {
    const nodeToDelete = this.head;
    this.head = this.head.next;
    this.length--;
    return nodeToDelete;
  }

  let current = this.head;
  let previous;
  let iterator = 0;

  while (iterator < index) {
    iterator++;
    previous = current;
    current = current.next;
  }
  const nodeToDelete = current;
  // Re-direct pointer to skip the element we"re deleting
  previous.next = current.next;

  // We"re at the end
  if(previous.next === null) {
    this.tail = previous;
  }

  this.length--;

  return nodeToDelete;
}

你的點贊是我持續(xù)分享好東西的動力，歡迎點贊！