# 鏈表 > 原文： [https://www.programiz.com/dsa/linked-list](https://www.programiz.com/dsa/linked-list) #### 在本教程中，您將學習鏈表及其應用。 您還將學習如何在鏈表上創建和執行不同的操作。 在尋寶游戲中，您首先要尋找第一個線索。 當您找到它時，它不再具有寶藏，而是具有下一條線索的位置，依此類推。 您會一直遵循這些線索，直到找到寶藏為止。 鏈表類似。 它是一系列連接的“節點”，包含下一個節點的“地址”。 每個節點可以存儲一個數據點，該數據點可以是數字，字符串或任何其他類型的數據。 * * * ## 鏈表表示  鏈表表示 您必須從某個地方開始，所以我們給第一個節點的地址一個特殊的名稱，叫做`HEAD`。 另外，由于鏈表的下一個節點指向`NULL`，因此可以確定鏈表中的最后一個節點。 * * * ## 如何引用下一個節點？ 涉及一些指針魔術。 讓我們考慮一下每個節點包含的內容： * 數據項 * 另一個節點的地址 我們將數據項和下一個節點引用都包裝在一個結構中，如下所示： ``` struct node { int data; struct node *next; }; ``` 了解鏈表節點的結構是掌握鏈表節點的關鍵。 每個結構節點都有一個數據項和一個指向另一個結構節點的指針。 讓我們創建一個包含三個項目的簡單鏈表，以了解其工作原理。 ``` /* Initialize nodes */ struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Allocate memory */ one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); /* Assign data values */ one->data = 1; two->data = 2; three->data=3; /* Connect nodes */ one->next = two; two->next = three; three->next = NULL; /* Save address of first node in head */ head = one; ``` 如果您不懂上述任何幾行，則只需要對[指針和結構](/c-programming/c-structures-pointers)進行復習。 僅需幾個步驟，我們就創建了一個包含三個節點的簡單鏈表。  具有三個節點的簡單鏈表 鏈表的功能來自斷開鏈并重新加入鏈的能力。 例如。 如果您想將元素 4 放在 1 和 2 之間，則步驟為： * 創建一個新的`struct node`并為其分配內存。 * 將其數據值添加為 4 * 將其下一個指針指向包含 2 作為數據值的`struct node` * 將下一個指針更改為我們剛剛創建的節點“1”。 在數組中執行類似的操作將需要移動所有后續元素的位置。 在 python 和 Java 中，可以使用下面的代碼所示的類來實現鏈表。 * * * ## 鏈表工具 列表是最流行和最有效的數據結構之一，可以在每種編程語言（例如 C，C++ ，Python，Java 和 C# ）中實現。 除此之外，鏈表是學習指針如何工作的好方法。 通過練習如何操作鏈表，您可以準備學習更高級的數據結構，例如圖形和樹。 * * * ## Python，Java 和 C/C++ 示例 ```py # Linked list implementation in Python class Node: # Creating a node def __init__(self, item): self.item = item self.next = None class LinkedList: def __init__(self): self.head = None if __name__ == '__main__': linked_list = LinkedList() # Assign item values linked_list.head = Node(1) second = Node(2) third = Node(3) # Connect nodes linked_list.head.next = second second.next = third # Print the linked list item while linked_list.head != None: print(linked_list.head.item, end=" ") linked_list.head = linked_list.head.next ``` ```java // Linked list implementation in Java class LinkedList { // Creating a node Node head; static class Node { int value; Node next; Node(int d) { value = d; next = null; } } public static void main(String[] args) { LinkedList linkedList = new LinkedList(); // Assign value values linkedList.head = new Node(1); Node second = new Node(2); Node third = new Node(3); // Connect nodess linkedList.head.next = second; second.next = third; // printing node-value while (linkedList.head != null) { System.out.print(linkedList.head.value + " "); linkedList.head = linkedList.head.next; } } } ``` ```c // Linked list implementation in C #include <stdio.h> #include <stdlib.h> // Creating a node struct node { int value; struct node *next; }; // print the linked list value void printLinkedlist(struct node *p) { while (p != NULL) { printf("%d ", p->value); p = p->next; } } int main() { // Initialize nodes struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; // Allocate memory one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); // Assign value values one->value = 1; two->value = 2; three->value = 3; // Connect nodes one->next = two; two->next = three; three->next = NULL; // printing node-value head = one; printLinkedlist(head); } ``` ```cpp // Linked list implementation in C++ #include <bits/stdc++.h> using namespace std; // Creating a node class Node { public: int value; Node* next; }; int main() { Node* head; Node* one = NULL; Node* two = NULL; Node* three = NULL; // allocate 3 nodes in the heap one = new Node(); two = new Node(); three = new Node(); // Assign value values one->value = 1; two->value = 2; three->value = 3; // Connect nodes one->next = two; two->next = three; three->next = NULL; // print the linked list value head = one; while (head != NULL) { printf("%d ", head->value); head = head->next; } } ``` * * * ## 鏈表復雜度 時間復雜度 | ? | 最壞情況 | 平均情況 | | --- | --- | --- | | **搜索** | `O(n)` | `O(n)` | | **插入** | `O(1)` | `O(1)` | | **刪除** | `O(1)` | `O(1)` | 空間復雜度：`O(n)` * * * ## 鏈表應用 * 動態內存分配 * 實現棧和隊列 * 軟件中的撤消功能 * 哈希表，圖