一、數組

數組是一種線性數據結構，它是由一組連續的內存單元組成的，用于存儲相同類型的數據。在JavaScript中，數組可以包含任意類型的數據，不只限于基本數據類型。

1.存儲方式

在內存中，數組的元素是連續存儲的，通過下標來訪問數組中的元素。例如，一個包含整型數據的數組可以用類似以下方式來表示：

let arr = [1, 2, 3, 4, 5];

2.訪問方式

通過數組下標來訪問數組中的元素，數組下標從0開始。例如，要訪問數組中的第三個元素，可以使用以下方式：

console.log(arr[2]); // 輸出3

3.時間復雜度

• 訪問：由于數組中的元素是連續存儲的，通過下標訪問數組中的元素的時間復雜度是O(1)。因為可以直接通過下標計算出元素的內存地址。

4.插入刪除操作的復雜度

-== 插入和刪除操作對數組的時間復雜度為O(n)==。因為在插入或刪除一個元素時，需要將數組中的元素進行移動以保持元素的連續性，這將導致額外的時間開銷。例如，在數組的開頭插入一個元素將需要將之后的元素全部向后移動一個位置，這將是一個線性操作。

綜上所述，數組是一種靈活的數據結構，可以用于存儲和訪問大量元素。訪問操作的時間復雜度是固定的O(1)，但插入和刪除操作的時間復雜度取決于操作的位置，可能是O(n)。

二、鏈表

鏈表是一種數據結構，它由多個節點組成，每個節點包含數據和指向下一個節點的指針。

從存儲方式來看，鏈表的節點是通過指針相連接的方式存儲在內存中。每個節點都包含一個指針，指向下一個節點的地址，這樣就形成了節點之間的連接。

舉例來說，可以用JavaScript實現一個簡單的鏈表節點：

class Node {constructor(data) {this.data = data;this.next = null;}
}

接著可以創建一個鏈表, 將多個節點連接起來：

let node1 = new Node(1);
let node2 = new Node(2);
node1.next = node2;

從訪問方式來看，鏈表的訪問是通過依次遍歷節點來訪問元素的。為了訪問特定位置的元素，需要從鏈表的頭節點開始順著指針找到對應位置的節點。

訪問鏈表的時間復雜度為O(n)，其中n為鏈表的長度。

對于插入和刪除操作，鏈表的復雜度取決于要插入或刪除的位置。如果要在鏈表頭部插入或刪除元素，時間復雜度為O(1)；如果要在鏈表尾部插入或刪除元素，仍然是O(n)。

綜上所述，鏈表是一種靈活的數據結構，適合頻繁進行插入或刪除操作。

三、數組和鏈表的區別

數組和鏈表是兩種常見的數據結構，它們之間的主要區別在于數據的存儲方式和訪問方式。

1. 存儲方式：

• 數組是一種連續的內存結構，所有元素在內存中相鄰存儲。數組的大小在創建時就確定了，可以通過下標來訪問任意位置的元素。
• 鏈表是一種非連續的內存結構，元素在內存中通過指針相連。鏈表的大小可以動態增長或減少，每個節點保存了下一個節點的指針，通過遍歷來訪問元素。

2. 訪問方式：

• 數組的元素可以直接通過下標來訪問，時間復雜度為O(1)。但插入或刪除元素時，需要移動其他元素，時間復雜度為O(n)。
• 鏈表的元素需要通過遍歷從頭節點開始找到目標節點，時間復雜度為O(n)。但插入或刪除元素時，只需要修改指針，時間復雜度為O(1)。

綜上所述，數組適合需要頻繁隨機訪問元素的情況，而鏈表適合需要頻繁插入、刪除元素的情況。在實際應用中，我們根據具體的需求選擇不同的數據結構。

四、用js實現鏈表

// 定義節點類
class Node {// 節點類構造函數，接收數據作為參數constructor(data) {this.data = data; // 節點存儲的數據this.next = null; // 指向下一個節點的指針}
}// 定義鏈表類
class LinkedList {// 鏈表類構造函數constructor() {this.head = null; // 鏈表的頭節點}// 添加節點到鏈表末尾append(data) {let newNode = new Node(data); // 創建新節點if (this.head === null) { // 如果鏈表為空this.head = newNode; // 新節點就是頭節點} else { // 如果鏈表不為空let current = this.head; // 從頭節點開始while (current.next !== null) { // 遍歷鏈表current = current.next; // 移動到下一個節點}current.next = newNode; // 將新節點添加到鏈表末尾}}// 刪除指定值的節點delete(data) {if (this.head === null) { // 如果鏈表為空return; // 直接返回}if (this.head.data === data) { // 如果頭節點就是要刪除的節點this.head = this.head.next; // 頭節點指向下一個節點return;}let current = this.head; // 從頭節點開始let prev = null; // 記錄當前節點的前一個節點while (current !== null) { // 遍歷鏈表if (current.data === data) { // 如果找到要刪除的節點prev.next = current.next; // 前一個節點指向當前節點的下一個節點return;}prev = current; // 記錄當前節點current = current.next; // 移動到下一個節點}}// 查找指定值的節點find(data) {let current = this.head; // 從頭節點開始while (current !== null) { // 遍歷鏈表if (current.data === data) { // 如果找到指定值的節點return current; // 返回該節點}current = current.next; // 移動到下一個節點}return null; // 如果沒有找到，返回 null}// 修改指定節點的值update(data, newData) {let node = this.find(data); // 查找指定值的節點if (node !== null) { // 如果找到該節點node.data = newData; // 修改該節點的值}}// 打印鏈表print() {let current = this.head; // 從頭節點開始let arr = [];while (current !== null) { // 遍歷鏈表arr.push(current.data); // 將節點的數據添加到數組中current = current.next; // 移動到下一個節點}console.log(arr.join('=>')); // 打印鏈表}
}// 測試鏈表功能
let list = new LinkedList();
list.append(1); // 添加節點 1
list.append(2); // 添加節點 2
list.append(3); // 添加節點 3console.log("Initial Linked List:");
list.print(); // 打印鏈表list.delete(2); // 刪除節點 2
console.log("After deleting '2':");
list.print(); // 打印鏈表list.update(3, 4); // 將節點 3 的值修改為 4
console.log("After updating '3' to '4':");
list.print(); // 打印鏈表let newNode = new Node(1); 
console.log(newNode); // 輸出 Node { data: 1, next: null }