# 鏈表 > 原文： [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(); } ```