TypeScript數(shù)據(jù)結(jié)構(gòu)鏈表結(jié)構(gòu)?LinkedList教程及面試

更新時間：2023年02月05日 09:28:14 作者：前端要努力QAQ

這篇文章主要為大家介紹了TypeScript數(shù)據(jù)結(jié)構(gòu)鏈表結(jié)構(gòu)?LinkedList教程及面試，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

1. 認(rèn)識鏈表

鏈表是一種通過指針的形式把一組存儲單元聯(lián)系在一起的數(shù)據(jù)結(jié)構(gòu)。
js 中沒有鏈表，但可以用 Object 模擬鏈表
鏈表類似于火車：有一個火車頭，火車頭會連接一個節(jié)點，節(jié)點上有乘客（類似于數(shù)據(jù)），并且這個節(jié)點會連接下一個節(jié)點，以此類推

鏈表的火車結(jié)構(gòu)：

鏈表的常見操作：

append(element)：向鏈表尾部添加一個新的項

insert(value, position)：向鏈表的特定位置插入一個新的項

get(position)：獲取對應(yīng)位置的元素

indexOf(element)：返回元素在鏈表中的索引。如果鏈表中沒有該元素則返回 -1

update(position,element)：修改某個位置的元素

removeAt(postion)：從鏈表的特定位置移除一項

remove(element)：從鏈表中移除一項

isEmpty()：如果鏈表中不包含任何元素，返回 true，如果鏈表長度大于等于0返回false

size()：返回鏈表包含的元素個數(shù)。與數(shù)組的length屬性類似

2. 實現(xiàn)鏈表結(jié)構(gòu)的封裝

2.1 基礎(chǔ)框架 v1 版

// 1. 創(chuàng)建 Node 節(jié)點類
class Node<T> {
  value: T;
  next: Node<T> | null = null;
  constructor(value: T) {
    this.value = value;
  }
}
// 2. 創(chuàng)建 LinkedList 的類
class LinkedList<T> {
  private head: Node<T> | null = null;
  private size: number = 0;
  get length() {
    return this.size;
  }
}

代碼解析：

封裝一個 Node 類，用于封裝每一個節(jié)點上的信息（包括和指向下一個節(jié)點的引用），它是一個泛型類
封裝一個 LinkedList 類，用于表示鏈表結(jié)構(gòu)
鏈表中保存兩個屬性，
size：鏈表長度

head：鏈表中的第一個節(jié)點

基礎(chǔ)的框架搭建好了，我們接下來就來一個個添加方法

2.2 添加 append 方法 v2 版

向 LinkedList 添加 append(element) 方法

append 方法的作用是向鏈表尾部添加一個新的項

  append(value: T) {
    // 1. 根據(jù) value創(chuàng)建一個新節(jié)點
    const newNode = new Node(value)
    // 2. 判斷 this.head 是否為 null
    if(!this.head) {
      this.head = newNode
    } else {
      let current = this.head
      while(current.next) {
        current = current.next
      }
      // 此時 current 指向最后一個節(jié)點
      current.next = newNode 
    }
    // 3. size++
    this.size++
  }

2.3 添加 traverse 方法 v3 版

為了方便可以看到鏈表上的每一個節(jié)點，我們實現(xiàn)一個 traverse 方法

向 LinkedList 添加 traverse 方法

traverse 方法的作用是遍歷鏈表

  traverse() {
    const values: T[] = [];
    let current = this.head;
    while (current) {
      values.push(current.value);
      current = current.next;
    }
    console.log(values.join("->"));
  }

測試：

const l = new LinkedList<string>();
l.append("第一個節(jié)點");
l.append("第二個節(jié)點");
l.append("第三個節(jié)點");
l.traverse();  // 第一個節(jié)點->第二個節(jié)點->第三個節(jié)點

2.4 添加 insert 方法 v4 版

向 LinkedList 添加 insert(value, position) 方法

insert方法的作用是向鏈表的特定位置插入一個新的項

  insert(value: T, position: number): boolean {
    // 1. 越界判斷
    if (position < 0 || position >= this.size) return false;
    // 2. 根據(jù) value 創(chuàng)建新的節(jié)點
    const newNode = new Node(value);
    // 3. 判斷是否需要插入頭部
    if (position === 0) {
      newNode.next = this.head;
      this.head = newNode;
    } else {
      let current = this.head;
      let previous: Node<T> | null = null;
      let index = 0;
      while (index++ < position && current) {
        previous = current;
        current = current.next;
      }
      // index === position
      newNode.next = current;
      previous!.next = newNode;
    }
    return true;
  }

測試：

const l = new LinkedList<string>();
l.append("aaa");
l.append("bbb");
l.append("ccc");
// l.insert("ddd", 0); // 插入頭部位置 ddd->aaa->bbb->ccc
// l.insert("ddd", 2); // 插入第二個位置  aaa->bbb->ddd->ccc
// l.insert("ddd", 3); // 插入尾部 aaa->bbb->ccc->ddd
l.traverse();

2.5 添加 removeAt 方法 v5 版

向 LinkedList 添加 removeAt(postion) 方法

removeAt方法的作用是從鏈表的特定位置移除一項

  removeAt(position: number): T | null {
    // 1. 越界判斷
    if (position < 0 || position > this.size) return null;
    // 2. 判斷是否刪除第一個節(jié)點
    let current = this.head;
    if (position === 0) {
      this.head = current?.next ?? null;
    } else {
      let previous: Node<T> | null = null;
      let index = 0;
      while (index++ < position && current) {
        previous = current;
        current = current.next;
      }
      previous!.next = current?.next ?? null;
    }
    this.size--;
    return current?.value ?? null;
  }

測試：

const l = new LinkedList<string>();
l.append("aaa");
l.append("bbb");
l.append("ccc");
// console.log(l.removeAt(0)); // aaa
// console.log(l.removeAt(1)); // bbb
// console.log(l.removeAt(2)); // ccc
// console.log(l.removeAt(3)); // null
l.traverse();

2.6 添加 get 方法 v6 版

向 LinkedList 添加 get(postion) 方法

get方法的作用是獲取對應(yīng)位置的元素

  get(position: number): T | null {
    // 越界問題
    if (position < 0 || position >= this.size) return null;
    // 2. 查找元素
    let index = 0;
    let current = this.head;
    while (index++ < position && current) {
      current = current?.next;
    }
    // index === position
    return current?.value ?? null;
  }

測試：

const l = new LinkedList<string>();
l.append("aaa");
l.append("bbb");
l.append("ccc");
console.log(l.get(0)); // aaa
console.log(l.get(1)); // bbb
console.log(l.get(2)); // ccc
console.log(l.get(3)); // null

2.7 添加 getNode 方法 v7 版

到這里，我們發(fā)現(xiàn)上面的代碼在通過 position 獲取節(jié)點的邏輯上有很多重復(fù)的地方，現(xiàn)在我們通過添加 getNode 方法來重構(gòu)一下

向 LinkedList 添加 getNode(postion) 私有方法

getNode方法的作用是獲取對應(yīng)位置的節(jié)點

  // 封裝私有方法
  // 根據(jù) position 獲取得到當(dāng)前的節(jié)點
  private getNode(position: number): Node<T> | null {
    let index = 0;
    let current = this.head;
    while (index++ < position && current) {
      current = current?.next;
    }
    return current;
  }

有了這個方法，我們就可以對 get removeAt insert 方法進(jìn)行重構(gòu)了

對 removeAt 進(jìn)行重構(gòu)

  removeAt(position: number): T | null {
    // 1. 越界判斷
    if (position < 0 || position > this.size) return null;
    // 2. 判斷是否刪除第一個節(jié)點
    let current = this.head;
    if (position === 0) {
      this.head = current?.next ?? null;
    } else {
-      let previous: Node<T> | null = null;
-      let index = 0;
-
-      while (index++ < position && current) {
-        previous = current;
-        current = current.next;
-      }
-      previous!.next = current?.next ?? null;
+      let previous = this.getNode(position - 1);
+      current = previous?.next ?? null;
+      previous!.next = previous?.next?.next ?? null;
    }
    this.size--;
    return current?.value ?? null;
  }

對 get 進(jìn)行重構(gòu)

  get(position: number): T | null {
    // 越界問題
    if (position < 0 || position >= this.size) return null;
    // 2. 查找元素
-    let index = 0;
-    let current = this.head;
-    while (index++ < position && current) {
-      current = current?.next;
-    }
+    let current = this.getNode(position);
    return current?.value ?? null;
  }

對 insert 進(jìn)行重構(gòu)

  insert(value: T, position: number): boolean {
    // 1. 越界判斷
    if (position < 0 || position > this.size) return false;
    // 2. 根據(jù) value 創(chuàng)建新的節(jié)點
    const newNode = new Node(value);
    // 3. 判斷是否需要插入頭部
    if (position === 0) {
      newNode.next = this.head;
      this.head = newNode;
    } else {
-      let current = this.head;
-      let previous: Node<T> | null = null;
-      let index = 0;
-
-      while (index++ < position && current) {
-        previous = current;
-        current = current.next;
-      }
-
-      // index === position
-      newNode.next = current;
-      previous!.next = newNode;
+      const previous = this.getNode(position - 1);
+      newNode.next = previous?.next ?? null;
+      previous!.next = newNode;
    }
    return true;
  }

測試一把，都沒問題

const l = new LinkedList<string>();
l.append("aaa");
l.append("bbb");
l.append("ccc");
// console.log(l.removeAt(0)); // aaa
// console.log(l.removeAt(1)); // bbb
// console.log(l.removeAt(2)); // ccc
// console.log(l.removeAt(3)); // null
// console.log(l.get(0)) // aaa
// console.log(l.get(1)) // bbb
// console.log(l.get(2)) // ccc
// console.log(l.get(3)) // null
// l.insert("ddd", 0); // ddd->aaa->bbb->ccc
// l.insert("ddd", 1); // aaa->ddd->bbb->ccc
// l.insert("ddd", 2); // aaa->bbb->ddd->ccc
// l.insert("ddd", 3); // aaa->bbb->ccc->ddd
// l.insert("ddd", 4); // aaa->bbb->ccc
l.traverse();

2.8 添加 update 方法 v8 版

向 LinkedList 添加 update(position,element) 方法

update方法的作用是修改某個位置的元素

  update(value: T, position: number):boolean {
    if (position < 0 || position >= this.size) return false;
    // 獲取對應(yīng)位置的節(jié)點，直接更新即可
    const currentNode = this.getNode(position)
    currentNode!.value = value
    return true
  }

測試：

const l = new LinkedList<string>();
l.append("aaa");
l.append("bbb");
l.append("ccc");
l.traverse(); // aaa->bbb->ccc
l.update("ddd", 1); // aaa->ddd->ccc
l.traverse();

2.9 添加 indexOf 方法 v9 版

向 LinkedList 添加 indexOf(element) 方法

indexOf方法的作用是返回元素在鏈表中的索引。如果鏈表中沒有該元素則返回 -1

  indexOf(value: T) {
    // 從第一個節(jié)點開始，向后遍歷
    let current = this.head;
    let index = 0;
    while (current) {
      if (current.value === value) {
        return index;
      }
      current = current.next;
      index++;
    }
    return -1;
  }

測試：

const l = new LinkedList<string>();
l.append("aaa");
l.append("bbb");
l.append("ccc");
console.log(l.indexOf("aaa"));
console.log(l.indexOf("bbb"));
console.log(l.indexOf("ccc"));

2.10 添加 remove 方法 v10 版

向 LinkedList 添加 remove(element) 方法

remove方法的作用是從鏈表中移除一項

  remove(value: T): T | null {
    const index = this.indexOf(value);
    return this.removeAt(index);
  }

測試：

const l = new LinkedList<string>();
l.append("aaa");
l.append("bbb");
l.append("ccc");
l.remove('bbb')
l.traverse() // aaa->ccc

2.11 添加方法 isEmpty v11 版

向 LinkedList 添加 isEmpty() 方法

isEmpty方法的作用是如果鏈表中不包含任何元素，返回 true，如果鏈表長度大于等于 0 返回 false

  isEmpty(): boolean {
    return this.size === 0;
  }

3. 面試題一：設(shè)計鏈表

這是 Leetcode 上的第 707 道題，難度為：中等

3.1 題目描述

設(shè)計鏈表的實現(xiàn)。您可以選擇使用單鏈表或雙鏈表。單鏈表中的節(jié)點應(yīng)該具有兩個屬性：val 和 next。val 是當(dāng)前節(jié)點的值，next 是指向下一個節(jié)點的指針/引用。如果要使用雙向鏈表，則還需要一個屬性 prev 以指示鏈表中的上一個節(jié)點。假設(shè)鏈表中的所有節(jié)點都是 0-index 的。

在鏈表類中實現(xiàn)這些功能：

get(index)：獲取鏈表中第 index 個節(jié)點的值。如果索引無效，則返回-1。
addAtHead(val)：在鏈表的第一個元素之前添加一個值為 val 的節(jié)點。插入后，新節(jié)點將成為鏈表的第一個節(jié)點。
addAtTail(val)：將值為 val 的節(jié)點追加到鏈表的最后一個元素。
addAtIndex(index,val)：在鏈表中的第 index 個節(jié)點之前添加值為 val 的節(jié)點。如果 index 等于鏈表的長度，則該節(jié)點將附加到鏈表的末尾。如果 index 大于鏈表長度，則不會插入節(jié)點。如果index小于0，則在頭部插入節(jié)點。
deleteAtIndex(index)：如果索引 index 有效，則刪除鏈表中的第 index 個節(jié)點。

示例：

MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2);   //鏈表變?yōu)?-&gt; 2-&gt; 3
linkedList.get(1);            //返回2
linkedList.deleteAtIndex(1);  //現(xiàn)在鏈表是1-&gt; 3
linkedList.get(1);            //返回3

提示：

0 <= index, val <= 1000
請不要使用內(nèi)置的 LinkedList 庫。
get, addAtHead, addAtTail, addAtIndex 和 deleteAtIndex 的操作次數(shù)不超過 2000。

3.2 解答

這道題的答案在第二章就已經(jīng)給出了，我們只需要進(jìn)行一些修改即可

class Node {
  value: number;
  next: Node | null = null;
  constructor(value: number) {
    this.value = value;
  }
}
class MyLinkedList {
  private head: Node | null = null;
  private size: number = 0;
  constructor() {}
  private getNode(position: number): Node | null {
    let index = 0;
    let current = this.head;
    while (index++ < position && current) {
      current = current?.next;
    }
    return current;
  }
  get(index: number): number {
    if (index < 0 || index >= this.size) return -1;
    let current = this.getNode(index);
    return current!.value;
  }
  addAtHead(val: number): void {
    const newNode = new Node(val);
    if (!this.head) {
      this.head = newNode;
    } else {
      newNode.next = this.head;
      this.head = newNode;
    }
    this.size++;
  }
  addAtTail(val: number): void {
    const newNode = new Node(val);
    if (!this.head) {
      this.head = newNode;
    } else {
      let current = this.getNode(this.size - 1);
      current!.next = newNode;
    }
    this.size++;
  }
  addAtIndex(index: number, val: number): void {
    if (index > this.size) return;
    if (index <= 0) {
      this.addAtHead(val);
    } else {
      const newNode = new Node(val);
      const previous = this.getNode(index - 1);
      newNode.next = previous?.next ?? null;
      previous!.next = newNode;
    }
    this.size++;
  }
  deleteAtIndex(index: number): void {
    if (index < 0 || index >= this.size) return;
    let current = this.head;
    if (index === 0) {
      this.head = current?.next ?? null;
    } else {
      const previous = this.getNode(index - 1);
      previous!.next = previous?.next?.next ?? null;
    }
    this.size--;
  }
}

復(fù)雜度分析：

時間復(fù)雜度：

初始化消耗 O(1)

get 消耗 O(index)

addAtHead 消耗 O(1)

addAtTail 消耗 O(n)，其中 n 為鏈表當(dāng)前長度

addAtIndex 消耗 O(index)

deleteAtIndex 消耗 O(index - 1)

空間復(fù)雜度：所有函數(shù)的單詞調(diào)用空間復(fù)雜度均為 O(1)，總體空間復(fù)雜度為 O(n)，

4. 面試題二：刪除鏈表中的節(jié)點

這是 Leetcode 上的第 237 道題，難度為：中等

4.1 題目描述

有一個單鏈表的 head，我們想刪除它其中的一個節(jié)點 node。

給你一個需要刪除的節(jié)點 node 。你將無法訪問第一個節(jié)點 head。

鏈表的所有值都是唯一的，并且保證給定的節(jié)點 node 不是鏈表中的最后一個節(jié)點。

刪除給定的節(jié)點。注意，刪除節(jié)點并不是指從內(nèi)存中刪除它。這里的意思是：

給定節(jié)點的值不應(yīng)該存在于鏈表中。
鏈表中的節(jié)點數(shù)應(yīng)該減少 1。
node 前面的所有值順序相同。
node 后面的所有值順序相同。

自定義測試：

對于輸入，你應(yīng)該提供整個鏈表 head 和要給出的節(jié)點 node。node 不應(yīng)該是鏈表的最后一個節(jié)點，而應(yīng)該是鏈表中的一個實際節(jié)點。
我們將構(gòu)建鏈表，并將節(jié)點傳遞給你的函數(shù)。
輸出將是調(diào)用你函數(shù)后的整個鏈表。

示例 1：

輸入： head = [4,5,1,9], node = 5
輸出： [4,1,9]
解釋：指定鏈表中值為 5 的第二個節(jié)點，那么在調(diào)用了你的函數(shù)之后，該鏈表應(yīng)變?yōu)?4 -> 1 -> 9

示例 2：

輸入： head = [4,5,1,9], node = 1
輸出： [4,5,9]
解釋：指定鏈表中值為 1 的第三個節(jié)點，那么在調(diào)用了你的函數(shù)之后，該鏈表應(yīng)變?yōu)?4 -> 5 -> 9

提示：

鏈表中節(jié)點的數(shù)目范圍是 [2, 1000]
-1000 <= Node.val <= 1000
鏈表中每個節(jié)點的值都是唯一的
需要刪除的節(jié)點 node 是鏈表中的節(jié)點，且不是末尾節(jié)點

4.2 解答

刪除節(jié)點的操作我們其實之前就已經(jīng)實現(xiàn)了的，我們只要拿到要刪除節(jié)點的前一個節(jié)點，將前一個節(jié)點的 next 指向要刪除節(jié)點的下一個節(jié)點即可。但是這道題有一個問題就是，我們拿不到要刪除前點的上一個節(jié)點。

思路：

我們可以將要刪除的節(jié)點的值賦值成它的下一個節(jié)點就行了，這樣就將問題從刪除某個節(jié)點轉(zhuǎn)換成了刪除某個節(jié)點的后一個節(jié)點，這樣的好處就是我們能拿到要刪除節(jié)點的前一個節(jié)點。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
/**
 Do not return anything, modify it in-place instead.
 */
function deleteNode(node: ListNode | null): void {
  node.val = node.next.val;
  node.next = node.next.next;
}

復(fù)雜度分析

時間復(fù)雜度：O(1)。
空間復(fù)雜度：O(1)。

5. 面試題三：反轉(zhuǎn)鏈表

這是 Leetcode 上的第 206 道題，難度為：中等

5.1 解一：棧結(jié)構(gòu)

這道題可以用棧來解決，利用棧的后進(jìn)先出的特性。

思路：先依次將數(shù)據(jù) push 進(jìn)棧中，再一次從棧中 pop 出數(shù)據(jù)，拼接 pop 出來的元素成一個新的鏈表。

function reverseList(head: ListNode | null): ListNode | null {
  // head 本身為 null 時 不需要處理
  if (head === null) return null;
  // 只有一個節(jié)點
  if (!head.next) return head;
  // 數(shù)組模擬棧結(jié)構(gòu)
  const stack: ListNode[] = [];
  let current: ListNode | null = head;
  while (current) {
    stack.push(current);
    current = current.next;
  }
  // 依次從棧結(jié)構(gòu)中取出元素，放到一個新的鏈表中
  const newHead: ListNode = stack.pop()!
  let newHeadCurrent = newHead
  while(stack.length) {
    const node = stack.pop()!
    newHeadCurrent.next = node
    newHeadCurrent = newHeadCurrent.next
  }
  newHeadCurrent.next = null
  return newHead
}

復(fù)雜度分析：

時間復(fù)雜度：O(2n) ，n 為鏈表的長度，因為要遍歷兩次鏈表
空間復(fù)雜度：O(n)，額外需要使用棧這種結(jié)構(gòu)

5.2 解二：迭代

假設(shè)鏈表為 1 ?? 2 ?? 3 ?? 4 ?? ∅，我們想要把它改成 ∅ ?? 1 ?? 2 ?? 3 ?? 4

思路：在遍歷鏈表時，將當(dāng)前節(jié)點的 next 指針改為指向前一個節(jié)點。由于節(jié)點沒有引用其前一個節(jié)點，因此必須事先存儲其前一個節(jié)點。在更改引用之前，還需要存儲后一個節(jié)點。最后返回新的頭引用。

function reverseList(head: ListNode | null): ListNode | null {
  // 1. 判斷節(jié)點為 null，或者只要一個節(jié)點，那么直接返回即可
  if (head === null || head.next === null) return head;
  // 2. 反轉(zhuǎn)鏈表結(jié)構(gòu)
  let newHead: ListNode | null = null
  while(head) {
    const current: ListNode | null = head.next
    head.next = newHead
    newHead = head
    head = current
  }
  return newHead
}

復(fù)雜度分析

時間復(fù)雜度：O(n)，其中 n 是鏈表的長度。需要遍歷鏈表一次。
空間復(fù)雜度：O(1)。

5.3 解三：遞歸

遞歸版本稍微復(fù)雜一些，其關(guān)鍵在于反向工作。

思路：

假如我們有一個鏈表 1 -> 2 -> 3 -> 4

如果我們想反轉(zhuǎn) 1 <- 2 就必須先將反轉(zhuǎn) 2 <- 3，因為如果我們將 1 -> 2 反轉(zhuǎn)成 1 <- 2 后，那么 2 后邊的節(jié)點就再也拿不到了。按照上面的邏輯遞歸，我們需要先將最后的 3 -> 4 反轉(zhuǎn)成 3 <- 4 在反轉(zhuǎn)前面的節(jié)點。

function reverseList(head: ListNode | null): ListNode | null {
  // 1. 判斷節(jié)點為 null，或者只要一個節(jié)點，那么直接返回即可
  if (head === null || head.next === null) {
    return head
  };
  const newHead = reverseList(head.next);
  head.next.next = head;
  head.next = null;
  return newHead;
}

復(fù)雜度分析：