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

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

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

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

這些都是在技術(shù)面試中經(jīng)常被問到的數(shù)據(jù)結(jié)構(gòu)，所以讓我們開始吧。

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

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

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

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

節(jié)點的值

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

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

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

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

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

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

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

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

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

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

構(gòu)造函數(shù)中需要三個信息:

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

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

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

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

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

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

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

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指針都設(shè)置為新節(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方法需要檢查以下兩項內(nèi)容：

檢查鏈表是否為空

檢查鏈表中是否只有一項

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

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

我們?nèi)绾沃梨湵碇兄挥幸粋€節(jié)點? 如果 head 和tail 指向同一個節(jié)點。但是在這種情況下我們需要做什么呢? 刪除唯一的節(jié)點意味著我們實際上要重新設(shè)置鏈表。

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

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

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

它看起來像這樣:

    1  let currentNode = this.head;
    2  let secondToLastNode;
    3
    4  //從前面開始并迭代直到找到倒數(shù)第二個節(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 移動到倒數(shù)第二個節(jié)點
   17  this.tail = secondToLastNode;
   18  this.length--;
   19 
   20  // 初始化 this.tail
   21   return nodeToRemove;

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

第6-10行:如果鏈表中的下一個節(jié)點是最后一個項，那么這個當(dāng)前項目就是新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設(shè)置為鏈表中的下一個值，減小長度，并返回我們剛剛刪除的值。

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

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

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

   增加索引值

   將前一個和當(dāng)前指針向上移動一個

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

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

如果下一個值為 `null`

   將`tail`設(shè)置為新的最后一個節(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ù)分享好東西的動力，歡迎點贊！