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

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

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

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

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

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

鏈表只是一系列節(jié)點(diǎn)，所以讓我們從 Node 對(duì)象開(kāi)始。

一個(gè)節(jié)點(diǎn)有兩條信息

指向鏈表中下一項(xiàng)的指針或引用(對(duì)于單鏈表)

節(jié)點(diǎn)的值

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

注意，我們可以只聲明 value 而不是 value: value。這是因?yàn)樽兞棵Q相同(ES6 語(yǔ)法)

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

節(jié)點(diǎn)鏈表將包含五個(gè)方法：

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

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

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

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

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

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

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

head:對(duì)鏈表開(kāi)頭節(jié)點(diǎn)的引用

tail:對(duì)鏈表末尾節(jié)點(diǎn)的引用

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

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

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

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

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

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

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

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

head 指針為空

對(duì)于這個(gè)例子，我們使用 head是否為null來(lái)判斷鏈表是否為空。

如果鏈表中沒(méi)有項(xiàng)，我們可以簡(jiǎn)單地將head 指針和tail指針都設(shè)置為新節(jié)點(diǎn)并更新鏈表的長(zhǎng)度。

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

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

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

將 tail 指向新節(jié)點(diǎn)

更新鏈表長(zhǎng)度

以下是完整的 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++;
}

在刪除鏈表中的最后一項(xiàng)之前，我們的pop方法需要檢查以下兩項(xiàng)內(nèi)容：

檢查鏈表是否為空

檢查鏈表中是否只有一項(xiàng)

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

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

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

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

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

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

它看起來(lái)像這樣:

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

如果你無(wú)法想象這一點(diǎn)，那么讓我們來(lái)看看它。

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

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

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

secondToLastNode.next = null;

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

this.tail = secondToLastNode;

第18行：更新鏈表的長(zhǎng)度，因?yàn)槲覀儎倓h除了一個(gè)節(jié)點(diǎn)。

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

以下是完整的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方法必須檢查三種情況：

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

鏈表是否為空

查詢第一個(gè)元素

如果鏈表中不存在請(qǐng)求的索引，則返回null。

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

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

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

如果我們請(qǐng)求第一個(gè)元素，返回 head。

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

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

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方法需要考慮到三個(gè)地方

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

鏈表是否為空

我們想要?jiǎng)h除 head

如果鏈表中不存在我們要?jiǎng)h除的索引，則返回 null。

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

如果我們想刪除head，將head設(shè)置為鏈表中的下一個(gè)值，減小長(zhǎng)度，并返回我們剛剛刪除的值。

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

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

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

   增加索引值

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

將當(dāng)前值保存為要?jiǎng)h除的節(jié)點(diǎn)

更新上一個(gè)節(jié)點(diǎn)的指針以指向下一個(gè)節(jié)點(diǎn)

如果下一個(gè)值為 `null`

   將`tail`設(shè)置為新的最后一個(gè)節(jié)點(diǎn)

更新鏈表長(zhǎng)度

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

如果你需要可視化圖片，請(qǐng)參考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;
}

你的點(diǎn)贊是我持續(xù)分享好東西的動(dòng)力，歡迎點(diǎn)贊！