# 鏈表
> 原文: [https://javabeginnerstutorial.com/data-structure/linked-list/](https://javabeginnerstutorial.com/data-structure/linked-list/)
## 什么是鏈表?
鏈表是另一種數據結構,也是一種常見的數據結構,它包括按順序分為兩組的一組節點,每個節點由數據和下一個節點的地址部分組成,并形成一個鏈。 它用于創建樹和圖。

**優點**
* 本質上是動態的,并在需要時分配內存。
* 有兩個可以在鏈表中輕松實現的操作,即插入和刪除。
* 減少訪問時間。
**缺點 **
* 內存浪費了,因為指針需要額外的存儲空間。
* 該元素不能隨機訪問,可以順序訪問。
* 在鏈表中,反向遍歷很困難。
## 在哪里使用鏈表?
1. 它們用于實現棧,隊列,圖形等。
2. 它們使您可以在列表的開頭和結尾插入元素。
3. 在此不需要事先知道大小。
## 鏈表的類型
### 單鏈表
這種類型的列表包含具有數據部分和地址部分的節點,即`next`,它指向給定節點序列中的下一個節點。 我們可以對單鏈列表執行的操作包括插入,刪除和遍歷。

### 雙鏈表
在這種類型的列表中,每個節點包含兩個鏈接,第一個鏈接將指向序列中的上一個節點,下一個鏈接將指向序列中的下一個節點。

循環鏈表 - 在這種類型的列表中,列表的最后一個節點包含第一個節點的地址,并將形成一個循環鏈。

## 單鏈表
單鏈表是其中每個節點僅包含一個指向下一個節點的鏈接字段的列表。 在這種情況下,節點分為兩部分,第一部分是數據部分,另一部分是包含下一個節點地址的鏈接部分。 第一個節點是標頭節點,其中包含下一個節點的數據和地址,依此類推。 單鏈列表也稱為單向列表,因為它只能從左到右遍歷,而另一種方式則是不可能的。

### 在哪里使用單鏈表?
單鏈列表可以在使用后進先出概念的棧中使用。 此列表維護與列表中頭節點的鏈接,每個節點都指向列表中的下一個節點。 它也可以用于先入先出的隊列中。
**在 C 中實現單鏈表**
```c
#include<stdio.h>
#include<stdlib.h>
typedef struct Node
{
int data;
struct Node *next;
}node;
void insert(node *ptr, int data)
{
while(ptr->next!=NULL)
{
ptr = ptr -> next;
}
ptr->next = (node *)malloc(sizeof(node));
ptr = ptr->next;
ptr->data = data;
ptr->next = NULL;
}
int find(node *ptr, int key)
{
ptr = ptr -> next;
while(ptr!=NULL)
{
if(ptr->data == key)
{
return 1;
}
ptr = ptr -> next;
}
return 0;
}
void delete(node *ptr, int data)
{
while(ptr->next!=NULL && (ptr->next)->data != data)
{
ptr = ptr -> next;
}
if(ptr->next==NULL)
{
printf("Element %d is not present in the list\n",data);
return;
}
node *temp;
temp = ptr -> next;
ptr->next = temp->next;
free(temp);
return;
}
void print(node *ptr)
{
if(ptr==NULL)
{
return;
}
printf("%d ",ptr->data);
print(ptr->next);
}
int main()
{
node *start,*temp;
start = (node *)malloc(sizeof(node));
temp = start;
temp -> next = NULL;
printf("1. Insert\n");
printf("2. Delete\n");
printf("3. Print\n");
printf("4. Find\n");
while(1)
{
int option;
scanf("%d",&option);
if(option==1)
{
int data;
scanf("%d",&data);
insert(start,data);
}
else if(option==2)
{
int data;
scanf("%d",&data);
delete(start,data);
}
else if(option==3)
{
printf("The list is ");
print(start->next);
printf("\n");
}
else if(option==4)
{
int data;
scanf("%d",&data);
int result = find(start,data);
if(result)
{
printf("The element is found \n");
}
else
{
printf("The element is not found\n");
}
}
}
}
```
## 雙鏈表
雙鏈列表也稱為雙向列表或雙向鏈。 在雙向鏈表中,兩個鏈接字段被保留,而不是像在單個鏈表中那樣保留一個鏈接字段。 雙鏈表是一個線性數據結構,其中每個節點都有兩個鏈接,其中第一個鏈接用于指向前一個節點,下一個鏈接指向下一個節點。 在雙向鏈表上執行的操作是插入,刪除,搜索和遍歷。

### 在哪里使用雙鏈表?
1. 用于表示游戲中的紙牌。
2. 在具有“最近使用”列表的應用中使用。
3. 在 Word 或 Photoshop 中用作撤消功能。
4. 在瀏覽器緩存中使用,它使我們可以單擊后退按鈕。
**使用 C 實現雙向鏈表**
```c
#include<stdio.h>
#include<stdlib.h>
typedef struct Node
{
int data;
struct Node *next;
struct Node *prev;
}node;
void insert(node *ptr, int data)
{
while(ptr->next!=NULL)
{
ptr = ptr -> next;
}
ptr->next = (node *)malloc(sizeof(node));
(ptr->next)->prev = ptr;
ptr = ptr->next;
ptr->data = data;
ptr->next = NULL;
}
int find(node *ptr, int key)
{
ptr = ptr -> next;
while (ptr!=NULL)
{
if(ptr->data == key)
{
return 1;
}
ptr = ptr -> next;
}
return 0;
}
void delete(node *ptr, int data)
{
while(ptr->next!=NULL && (ptr->next)->data != data)
{
ptr = ptr -> next;
}
if(ptr->next==NULL)
{
printf("The element %d is not present in the list\n",data);
return;
}
node *temp;
temp = ptr -> next;
ptr->next = temp->next;
temp->prev = ptr;
free(temp);
return;
}
void print(node *ptr)
{
if(ptr==NULL)
{
return;
}
printf("%d ",ptr->data);
print(ptr->next);
}
int main()
{
node *start,*temp;
start = (node *)malloc(sizeof(node));
temp = start;
temp -> next = NULL;
temp -> prev = NULL;
printf("1. Insert\n");
printf("2. Delete\n");
printf("3. Print\n");
printf("4. Find\n");
while(1)
{
int option;
scanf("%d",&option);
if(option==1)
{
int data;
scanf("%d",&data);
insert(start,data);
}
else if(option==2)
{
int data;
scanf("%d",&data);
delete(start,data);
}
else if(option==3)
{
printf("The list is ");
print(start->next);
printf("\n");
}
else if(option==4)
{
int data;
scanf("%d",&data);
int result = find(start,data);
if(result)
{
printf("The element is found\n");
}
else
{
printf("The element is not found\n");
}
}
}
}
```
## 循環鏈表
循環鏈表是有點復雜的鏈接數據結構。 在此列表中,我們可以在列表中的任何位置插入元素,而在數組中,我們不能在列表中的任何位置插入元素,因為它在連續內存中。 在此列表中,上一個元素存儲下一個元素的地址,最后一個元素存儲第一個元素的地址。 列表中的元素以圓形的方式相互指向,形成圓形的鏈。 該列表具有動態大小,這意味著可以在需要時分配內存。

### 在哪里使用循環鏈表?
使用此列表的實際應用是在其上運行多個應用的??PC。 循環鏈表在操作系統中很常見,因為它會將正在運行的應用放在列表中,并且當列表即將到達其末端時,操作系統很容易使用循環鏈表,因為操作系統可以循環運行到列表的最前面。 將該時隙分配給列表中的每個應用。
**在 C 中實現循環鏈??表**
```c
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
}node;
void insert(node *pointer, int data)
{
node *start = pointer;
while(pointer->next!=start)
{
pointer = pointer -> next;
}
pointer->next = (node *)malloc(sizeof(node));
pointer = pointer->next;
pointer->data = data;
pointer->next = start;
}
void delete(node *pointer, int data)
{
node *start = pointer;
while(pointer->next!=start && (pointer->next)->data != data)
{
pointer = pointer -> next;
}
if(pointer->next==start)
{
printf("Element %d is not present in the list\n",data);
return;
}
node *temp;
temp = pointer -> next;
pointer->next = temp->next;
free(temp);
free( )
return;
}
void display(node *start,node *pointer)
{
if(pointer = = start)
{
return;
}
printf("%d ",pointer->data);
display(start,pointer->next);
}
void main()
{
node *start,*temp;
start = (struct node *)malloc(sizeof(struct node));
temp = start;
temp -> next = start;
printf("1. Insert\n");
printf("2. Delete\n");
printf("3. Display\n");
while(1)
{
int query;
scanf("%d",&query);
if(query==1)
{
int data;
scanf("%d",&data);
insert(start,data);
}
else if(query==2)
{ int data;
scanf("%d",&data);
delete(start,data);
}
else if(query==3)
{ printf("The list is ");
display(start,start->next);
printf("\n");
} }
getch( );
}
```
## 線性鏈表
在鏈表中,我們可以通過三種方式插入元素:
* 插入列表的開頭。
* 插入列表的中間。
* 插入到列表的末尾。
在將節點插入列表之前,我們將使用關鍵字`struct`創建一個結構。 例如:
```c
struct node
{ int data;
struct node *next;
};
struct employee *start=NULL, *temp,*q;
```
并且在定義了結構之后,在從列表中插入或刪除節點的同時,給出了特定的功能定義或功能原型。 例如:
```c
void insertbeg( );
void insertmiddle( );
void insertlast( );
void deletebeg( );
```
上面給出的函數定義在`main`函數之前定義,即`void main()`或`int main()`。
**在開頭的插入元素**
在開始時插入節點的步驟:
1. 創建一個新節點。
2. 在數據部分輸入數據。
3. 將地址部分或下一部分設為`NULL`。
4. 現在將這個新創建的節點附加到起始或頭部。
5. 現在,將此起始節點設為起始節點或標頭節點。
**在中間的插入元素**
在中間插入節點的步驟:
1. 將要添加的新節點的數據寫入列表及其位置。
2. 通過調用`malloc()`創建一個新的空節點。
3. 將數據插入新節點的數據部分。
4. 將此新節點添加到列表中的所需位置。
5. 轉到步驟 1,直到您在列表中添加了所有值。
**實現**
```c
void insertmiddle()
{ int pos,i,num;
if(start==NULL)
{ printf("\nList is empty!! Sorry...");
}
temp=(struct node*)malloc(sizeof(struct node));
printf("\nEnter the details:");
scanf("%d",num);
printf("\nEnter position:");
scanf("%d",&pos);
temp->data=num;
q=start
for(i=1;i<pos-1;pos++)
{
if(q->next==NULL)
{ printf("\nLess elements in the list");
}
q=q->next;
}
temp->next=q->next;
q->next=temp;
getch();
}
```
**在列表的末尾插入元素:**
最后插入節點的步驟:
1. 創建新節點。
2. 將數據輸入到節點的數據部分。
3. 將節點的下一部分設為`NULL`。
4. 要在最后一個位置插入節點,因此我們必須遍歷到最后一個節點。
5. 在最后一個節點和新節點之間建立鏈接。
**實現**
```c
void insertlast()
{ int num;
temp=(struct node*)malloc(sizeof(struct node));
printf("\nEnter the details:");
scanf("%d",&num);
temp->data=num;
temp->next=NULL;
if(start==NULL) //If list is empty
{
start=temp;
}
else
{
q=start;
while(q->next!=NULL)
q=q->next;
q->next=temp;
}
}
```
**刪除**
可以通過三種方式刪除該元素:
* 從列表的開頭刪除。
* 從列表的中間刪除。
* 從列表末尾刪除。
**從開頭刪除元素**
```c
Implementation
void deletebeg()
{ if(start==NULL)
{ printf("\nThe list is empty...");
}
else
{
q=start;
start=start->next;
free(q);
printf("\nElement deleted...");
}
}
```
**從中間刪除元素**
實現
```c
void deletemiddle()
{ int pos,i;
if(start==NULL)
{ printf("\nThe list is empty...");
}
printf("\nEnter position to delete:");
scanf("%d",&pos);
for(i=1;i<pos-1;pos++)
{
if(q->next==NULL)
{
printf("\nLess elements...");
getch();
}
q=q->next;
}
temp=q->next;
q->next=temp->next;
free(temp);
printf("\nElement deleted...");
getch();
}
```
**從末尾刪除元素**
實現
```c
void deletelast()
{ if(start==NULL)
{
printf("\nThe list is empty...");
}
else
{
q=start;
while(q->next->next!=NULL)
q=q->next;
temp=q->next;
q->next=NULL;
free(temp);
printf("\nElement deleted...");
}
}
```
**顯示**
在執行任何操作后顯示列表的元素。
```c
void display()
{ struct node *q;
q=start;
while(q!=NULL)
{
printf("%d\t",q->data);
q=q->next;
}
getch();
}
```
- JavaBeginnersTutorial 中文系列教程
- Java 教程
- Java 教程 – 入門
- Java 的歷史
- Java 基礎知識:Java 入門
- jdk vs jre vs jvm
- public static void main(string args[])說明
- 面向初學者的 Java 類和對象教程
- Java 構造器
- 使用 Eclipse 編寫 Hello World 程序
- 執行順序
- Java 中的訪問修飾符
- Java 中的非訪問修飾符
- Java 中的數據類型
- Java 中的算術運算符
- Java 語句初學者教程
- 用 Java 創建對象的不同方法
- 內部類
- 字符串構建器
- Java 字符串教程
- Java 教程 – 變量
- Java 中的變量
- Java 中的局部變量
- Java 中的實例變量
- Java 引用變量
- 變量遮蓋
- Java 教程 – 循環
- Java for循環
- Java 教程 – 異常
- Java 異常教程
- 異常處理 – try-with-resources語句
- Java 異常處理 – try catch塊
- Java 教程 – OOPS 概念
- Java 重載
- Java 方法覆蓋
- Java 接口
- 繼承
- Java 教程 – 關鍵字
- Java 中的this關鍵字
- Java static關鍵字
- Java 教程 – 集合
- Java 數組教程
- Java 集合
- Java 集合迭代器
- Java Hashmap教程
- 鏈表
- Java 初學者List集合教程
- Java 初學者的Map集合教程
- Java 初學者的Set教程
- Java 初學者的SortedSet集合教程
- Java 初學者SortedMap集合教程
- Java 教程 – 序列化
- Java 序列化概念和示例
- Java 序列化概念和示例第二部分
- Java 瞬態與靜態變量
- serialVersionUID的用途是什么
- Java 教程 – 枚舉
- Java 枚舉(enum)
- Java 枚舉示例
- 核心 Java 教程 – 線程
- Java 線程教程
- Java 8 功能
- Java Lambda:初學者指南
- Lambda 表達式簡介
- Java 8 Lambda 列表foreach
- Java 8 Lambda 映射foreach
- Java 9
- Java 9 功能
- Java 10
- Java 10 獨特功能
- 核心 Java 教程 – 高級主題
- Java 虛擬機基礎
- Java 類加載器
- Java 開發人員必須知道..
- Selenium 教程
- 1 什么是 Selenium?
- 2 為什么要進行自動化測試?
- 3 Selenium 的歷史
- 4 Selenium 工具套件
- 5 Selenium 工具支持的瀏覽器和平臺
- 6 Selenium 工具:爭霸
- 7A Selenium IDE – 簡介,優點和局限性
- 7B Selenium IDE – Selenium IDE 和 Firebug 安裝
- 7C Selenium IDE – 突破表面:初探
- 7D Selenium IDE – 了解您的 IDE 功能
- 7E Selenium IDE – 了解您的 IDE 功能(續)。
- 7F Selenium IDE – 命令,目標和值
- 7G Selenium IDE – 記錄和運行測試用例
- 7H Selenium IDE – Selenium 命令一覽
- 7I Selenium IDE – 設置超時,斷點,起點
- 7J Selenium IDE – 調試
- 7K Selenium IDE – 定位元素(按 ID,名稱,鏈接文本)
- 7L Selenium IDE – 定位元素(續)
- 7M Selenium IDE – 斷言和驗證
- 7N Selenium IDE – 利用 Firebug 的優勢
- 7O Selenium IDE – 以所需的語言導出測試用例
- 7P Selenium IDE – 其他功能
- 7Q Selenium IDE – 快速瀏覽插件
- 7Q Selenium IDE – 暫停和反射
- 8 給新手的驚喜
- 9A WebDriver – 架構及其工作方式
- 9B WebDriver – 在 Eclipse 中設置
- 9C WebDriver – 啟動 Firefox 的第一個測試腳本
- 9D WebDriver – 執行測試
- 9E WebDriver – 用于啟動其他瀏覽器的代碼示例
- 9F WebDriver – JUnit 環境設置
- 9G WebDriver – 在 JUnit4 中運行 WebDriver 測試
- 9H WebDriver – 隱式等待
- 9I WebDriver – 顯式等待
- 9J WebDriver – 定位元素:第 1 部分(按 ID,名稱,標簽名稱)
- 9K WebDriver – 定位元素:第 2 部分(按className,linkText,partialLinkText)
- 9L WebDriver – 定位元素:第 3a 部分(按cssSelector定位)
- 9M WebDriver – 定位元素:第 3b 部分(cssSelector續)
- 9N WebDriver – 定位元素:第 4a 部分(通過 xpath)
- 9O WebDriver – 定位元素:第 4b 部分(XPath 續)
- 9P WebDriver – 節省時間的捷徑:定位器驗證
- 9Q WebDriver – 處理驗證碼
- 9R WebDriver – 斷言和驗證
- 9S WebDriver – 處理文本框和圖像
- 9T WebDriver – 處理單選按鈕和復選框
- 9U WebDriver – 通過兩種方式選擇項目(下拉菜單和多項選擇)
- 9V WebDriver – 以兩種方式處理表
- 9W WebDriver – 遍歷表元素
- 9X WebDriver – 處理警報/彈出框
- 9Y WebDriver – 處理多個窗口
- 9Z WebDriver – 最大化窗口
- 9AA WebDriver – 執行 JavaScript 代碼
- 9AB WebDriver – 使用動作類
- 9AC WebDriver – 無法輕松定位元素? 繼續閱讀...
- 10A 高級 WebDriver – 使用 Apache ANT
- 10B 高級 WebDriver – 生成 JUnit 報告
- 10C 高級 WebDriver – JUnit 報表自定義
- 10D 高級 WebDriver – JUnit 報告自定義續
- 10E 高級 WebDriver – 生成 PDF 報告
- 10F 高級 WebDriver – 截屏
- 10G 高級 WebDriver – 將屏幕截圖保存到 Word 文檔
- 10H 高級 WebDriver – 發送帶有附件的電子郵件
- 10I 高級 WebDriver – 使用屬性文件
- 10J 高級 WebDriver – 使用 POI 從 excel 讀取數據
- 10K 高級 WebDriver – 使用 Log4j 第 1 部分
- 10L 高級 WebDriver – 使用 Log4j 第 2 部分
- 10M 高級 WebDriver – 以無頭模式運行測試
- Vue 教程
- 1 使用 Vue.js 的 Hello World
- 2 模板語法和反應式的初探
- 3 Vue 指令簡介
- 4 Vue Devtools 設置
- 5 數據綁定第 1 部分(文本,原始 HTML,JavaScript 表達式)
- 6 數據綁定第 2 部分(屬性)
- 7 條件渲染第 1 部分(v-if,v-else,v-else-if)
- 8 條件渲染第 2 部分(v-if和v-show)
- 9 渲染列表第 1 部分(遍歷數組)
- 10 渲染列表第 2 部分(遍歷對象)
- 11 監聽 DOM 事件和事件修飾符
- 12 監聽鍵盤和鼠標事件
- 13 讓我們使用簡寫
- 14 使用v-model進行雙向數據綁定
- 15 表單輸入綁定
- 18 類綁定
- Python 教程
- Python 3 簡介
- Python 基礎知識 - 又稱 Hello World 以及如何實現
- 如何在 Windows 中安裝 python
- 適用于 Windows,Mac,Linux 的 Python 設置
- Python 數字和字符串
- Python 列表
- Python 集
- Python 字典
- Python 條件語句
- Python 循環
- Python 函數
- 面向對象編程(OOP)
- Python 中的面向對象編程
- Python 3 中的異常處理
- Python 3:猜數字
- Python 3:猜數字 – 回顧
- Python 生成器
- Hibernate 教程
- Hibernate 框架基礎
- Hibernate 4 入門教程
- Hibernate 4 注解配置
- Hibernate 4 的實體關系
- Hibernate 4 中的實體繼承模型
- Hibernate 4 查詢語言
- Hibernate 4 數據庫配置
- Hibernate 4 批處理
- Hibernate 4 緩存
- Hibernate 4 審計
- Hibernate 4 的并發控制
- Hibernate 4 的多租戶
- Hibernate 4 連接池
- Hibernate 自舉