TypeScript數(shù)據(jù)結構鏈表結構?LinkedList教程及面試
更新時間：2023年02月05日 09:28:14 作者：前端要努力QAQ
這篇文章主要為大家介紹了TypeScript數(shù)據(jù)結構鏈表結構?LinkedList教程及面試，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪
1. 認識鏈表
- 鏈表是一種通過指針的形式把一組存儲單元聯(lián)系在一起的數(shù)據(jù)結構。
js中沒有鏈表，但可以用Object模擬鏈表- 鏈表類似于火車：有一個火車頭，火車頭會連接一個節(jié)點，節(jié)點上有乘客（類似于數(shù)據(jù)），并且這個節(jié)點會連接下一個節(jié)點，以此類推
鏈表的火車結構：
鏈表的常見操作：
append(element)：向鏈表尾部添加一個新的項
insert(value, position)：向鏈表的特定位置插入一個新的項
get(position)：獲取對應位置的元素
indexOf(element)：返回元素在鏈表中的索引。如果鏈表中沒有該元素則返回 -1
update(position,element)：修改某個位置的元素
removeAt(postion)：從鏈表的特定位置移除一項
remove(element)：從鏈表中移除一項
isEmpty()：如果鏈表中不包含任何元素，返回 true，如果鏈表長度大于等于0返回false
size()：返回鏈表包含的元素個數(shù)。與數(shù)組的length屬性類似
2. 實現(xiàn)鏈表結構的封裝
2.1 基礎框架 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類，用于表示鏈表結構 - 鏈表中保存兩個屬性，
size：鏈表長度head：鏈表中的第一個節(jié)點
基礎的框架搭建好了，我們接下來就來一個個添加方法
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方法的作用是獲取對應位置的元素
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é)點的邏輯 上有很多重復的地方，現(xiàn)在我們通過添加 getNode 方法來重構一下
向 LinkedList 添加 getNode(postion) 私有方法
getNode方法的作用是獲取對應位置的節(jié)點
// 封裝私有方法
// 根據(jù) position 獲取得到當前的節(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 方法進行重構了
- 對
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;
+ let previous = this.getNode(position - 1);
+ current = previous?.next ?? null;
+ previous!.next = previous?.next?.next ?? null;
}
this.size--;
return current?.value ?? null;
}
- 對
get進行重構
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進行重構
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;
// 獲取對應位置的節(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. 面試題一：設計鏈表
這是 Leetcode 上的第 707 道題，難度為：中等
3.1 題目描述
設計鏈表的實現(xiàn)。您可以選擇使用單鏈表或雙鏈表。單鏈表中的節(jié)點應該具有兩個屬性：val 和 next。val 是當前節(jié)點的值，next 是指向下一個節(jié)點的指針/引用。如果要使用雙向鏈表，則還需要一個屬性 prev 以指示鏈表中的上一個節(jié)點。假設鏈表中的所有節(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)?-> 2-> 3 linkedList.get(1); //返回2 linkedList.deleteAtIndex(1); //現(xiàn)在鏈表是1-> 3 linkedList.get(1); //返回3
提示：
0 <= index, val <= 1000- 請不要使用內(nèi)置的
LinkedList庫。 get,addAtHead,addAtTail,addAtIndex和deleteAtIndex的操作次數(shù)不超過2000。
3.2 解答
這道題的答案在第二章就已經(jīng)給出了，我們只需要進行一些修改即可
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--;
}
}
復雜度分析：
時間復雜度：
初始化消耗 O(1)
get 消耗 O(index)
addAtHead 消耗 O(1)
addAtTail 消耗 O(n)，其中 n 為鏈表當前長度
addAtIndex 消耗 O(index)
deleteAtIndex 消耗 O(index - 1)
- 空間復雜度：所有函數(shù)的單詞調(diào)用空間復雜度均為
O(1)，總體空間復雜度為O(n)，
4. 面試題二：刪除鏈表中的節(jié)點
這是 Leetcode 上的第 237 道題，難度為：中等
4.1 題目描述
有一個單鏈表的 head，我們想刪除它其中的一個節(jié)點 node。
給你一個需要刪除的節(jié)點 node 。你將 無法訪問 第一個節(jié)點 head。
鏈表的所有值都是 唯一的，并且保證給定的節(jié)點 node 不是鏈表中的最后一個節(jié)點。
刪除給定的節(jié)點。注意，刪除節(jié)點并不是指從內(nèi)存中刪除它。這里的意思是：
- 給定節(jié)點的值不應該存在于鏈表中。
- 鏈表中的節(jié)點數(shù)應該減少 1。
node前面的所有值順序相同。node后面的所有值順序相同。
自定義測試：
- 對于輸入，你應該提供整個鏈表
head和要給出的節(jié)點node。node不應該是鏈表的最后一個節(jié)點，而應該是鏈表中的一個實際節(jié)點。 - 我們將構建鏈表，并將節(jié)點傳遞給你的函數(shù)。
- 輸出將是調(diào)用你函數(shù)后的整個鏈表。
示例 1：
輸入： head = [4,5,1,9], node = 5
輸出： [4,1,9]
解釋： 指定鏈表中值為 5 的第二個節(jié)點，那么在調(diào)用了你的函數(shù)之后，該鏈表應變?yōu)?4 -> 1 -> 9
示例 2：
輸入： head = [4,5,1,9], node = 1
輸出： [4,5,9]
解釋： 指定鏈表中值為 1 的第三個節(jié)點，那么在調(diào)用了你的函數(shù)之后，該鏈表應變?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;
}
復雜度分析
- 時間復雜度：
O(1)。 - 空間復雜度：
O(1)。
5. 面試題三：反轉(zhuǎn)鏈表
這是 Leetcode 上的第 206 道題，難度為：中等
5.1 解一：棧結構
這道題可以用棧來解決，利用棧的 后進先出 的特性。
思路：先依次將數(shù)據(jù) push 進棧中，再一次從棧中 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ù)組模擬棧結構
const stack: ListNode[] = [];
let current: ListNode | null = head;
while (current) {
stack.push(current);
current = current.next;
}
// 依次從棧結構中取出元素，放到一個新的鏈表中
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
}
復雜度分析：
- 時間復雜度：
O(2n)，n為鏈表的長度，因為要遍歷兩次鏈表 - 空間復雜度：
O(n)，額外需要使用棧這種結構
5.2 解二：迭代
假設鏈表為 1 ?? 2 ?? 3 ?? 4 ?? ∅，我們想要把它改成 ∅ ?? 1 ?? 2 ?? 3 ?? 4
思路：在遍歷鏈表時，將當前節(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)鏈表結構
let newHead: ListNode | null = null
while(head) {
const current: ListNode | null = head.next
head.next = newHead
newHead = head
head = current
}
return newHead
}
復雜度分析
- 時間復雜度：
O(n)，其中n是鏈表的長度。需要遍歷鏈表一次。 - 空間復雜度：
O(1)。
5.3 解三：遞歸
遞歸版本稍微復雜一些，其關鍵在于反向工作。
思路：
假如我們有一個鏈表 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;
}
復雜度分析：
- 時間復雜度：
O(n)，其中n是鏈表的長度。需要對鏈表的每個節(jié)點進行反轉(zhuǎn)操作。 - 空間復雜度：
O(n)，其中n是鏈表的長度?？臻g復雜度主要取決于遞歸調(diào)用的?？臻g，最多為n層。
以上就是TypeScript數(shù)據(jù)結構鏈表結構 LinkedList教程及面試的詳細內(nèi)容，更多關于TypeScript 鏈表結構的資料請關注腳本之家其它相關文章！
相關文章
高級前端面試手寫扁平數(shù)據(jù)結構轉(zhuǎn)Tree
這篇文章主要為大家介紹了高級前端面試手寫扁平數(shù)據(jù)結構轉(zhuǎn)Tree示例代碼，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-06-06
typescript難學嗎？前端有必要學？該怎么學typescript
TypeScript代碼與?JavaScript?代碼有非常高的兼容性，無門檻，你把?JS?代碼改為?TS?就可以運行。TypeScript?應該不會脫離?JavaScript?成為獨立的語言。學習?TypeScript?應該主要指的是學習它的類型系統(tǒng)。2022-12-12
這篇文章主要為大家介紹了TypeScript中的函數(shù)重載示例分析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-08-08
這篇文章主要為大家介紹了TypeScript?泛型接口具體使用實戰(zhàn),有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-07-07
這篇文章主要為大家介紹了TypeScript中的聯(lián)合類型使用示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-08-08
xterm.js在web端實現(xiàn)Terminal示例詳解
這篇文章主要為大家介紹了xterm.js在web端實現(xiàn)Terminal示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-11-11
這篇文章主要介紹了微信小程序?qū)崙?zhàn)之運維小項目,就是利用微信小程序?qū)崿F(xiàn)了一個類似138的功能，輸入IP就可以查看IP的詳細信心，有需要的朋友可以參考借鑒，下面來一起看看吧。2017-01-01
Manipulation-TypeScript?DOM操作示例解析
這篇文章主要為大家介紹了DOM?Manipulation-TypeScript?DOM操作示例解析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-03-03
TypeScript與JavaScript的區(qū)別分析
TypeScript可以使用JavaScript中的所有代碼和編程概念,TypeScript是為了使JavaScript的開發(fā)變得更加容易而創(chuàng)建的。推薦先精通JS的的前提下再學習TS，這樣更有利于同時學習兩門語言。2022-12-12
網(wǎng)上分享的CKEditor4中文說明很多都只是的部分使用方法，今天為大家分享一下比較完整的CKEditor4中文說明文檔2018-10-10