链表

原文： https://javabeginnerstutorial.com/data-structure/linked-list/

什么是链表？

链表是另一种数据结构，也是一种常见的数据结构，它包括按顺序分为两组的一组节点，每个节点由数据和下一个节点的地址部分组成，并形成一个链。 它用于创建树和图。

链表 - 图1

优点

  • 本质上是动态的，并在需要时分配内存。

  • 有两个可以在链表中轻松实现的操作，即插入和删除。

  • 减少访问时间。

**缺点 **

  • 内存浪费了，因为指针需要额外的存储空间。

  • 该元素不能随机访问，可以顺序访问。

  • 在链表中，反向遍历很困难。

在哪里使用链表？

  1. 它们用于实现栈，队列，图形等。

  2. 它们使您可以在列表的开头和结尾插入元素。

  3. 在此不需要事先知道大小。

链表的类型

单链表

这种类型的列表包含具有数据部分和地址部分的节点，即next，它指向给定节点序列中的下一个节点。 我们可以对单链列表执行的操作包括插入，删除和遍历。

链表 - 图2

双链表

在这种类型的列表中，每个节点包含两个链接，第一个链接将指向序列中的上一个节点，下一个链接将指向序列中的下一个节点。

链表 - 图3

循环链表 - 在这种类型的列表中，列表的最后一个节点包含第一个节点的地址，并将形成一个循环链。

链表 - 图4

单链表

单链表是其中每个节点仅包含一个指向下一个节点的链接字段的列表。 在这种情况下，节点分为两部分，第一部分是数据部分，另一部分是包含下一个节点地址的链接部分。 第一个节点是标头节点，其中包含下一个节点的数据和地址，依此类推。 单链列表也称为单向列表，因为它只能从左到右遍历，而另一种方式则是不可能的。

链表 - 图5

在哪里使用单链表？

单链列表可以在使用后进先出概念的栈中使用。 此列表维护与列表中头节点的链接，每个节点都指向列表中的下一个节点。 它也可以用于先入先出的队列中。

在 C 中实现单链表

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. typedef struct Node
  4. {
  5.         int data;
  6.         struct Node *next;
  7. }node;
  8. void insert(node *ptr, int data)
  9. {
  10.         while(ptr->next!=NULL)
  11.         {
  12.                 ptr = ptr -> next;
  13.         }
  15.         ptr->next = (node *)malloc(sizeof(node));
  16.         ptr = ptr->next;
  17.         ptr->data = data;
  18.         ptr->next = NULL;
  19. }
  20. int find(node *ptr, int key)
  21. {
  22.         ptr =  ptr -> next;
  24.         while(ptr!=NULL)
  25.         {
  26.                 if(ptr->data == key)
  27.                 {
  28.                         return 1;
  29.                 }
  30.                 ptr = ptr -> next;
  31.         }
  33.         return 0;
  34. }
  35. void delete(node *ptr, int data)
  36. {
  38.         while(ptr->next!=NULL && (ptr->next)->data != data)
  39.         {
  40.                 ptr = ptr -> next;
  41.         }
  42.         if(ptr->next==NULL)
  43.         {
  44.                 printf("Element %d is not present in the list\n",data);
  45.                 return;
  46.         }
  48.         node *temp;
  49.         temp = ptr -> next;
  50.         ptr->next = temp->next;
  51.         free(temp);
  53.         return;
  54. }
  55. void print(node *ptr)
  56. {
  57.         if(ptr==NULL)
  58.         {
  59.                 return;
  60.         }
  61.         printf("%d ",ptr->data);
  62.         print(ptr->next);
  63. }
  64. int main()
  65. {
  66.         node *start,*temp;
  67.         start = (node *)malloc(sizeof(node));
  68.         temp = start;
  69.         temp -> next = NULL;
  71.         printf("1. Insert\n");
  72.         printf("2. Delete\n");
  73.         printf("3. Print\n");
  74.         printf("4. Find\n");
  75.         while(1)
  76.         {
  77.                 int option;
  78.                 scanf("%d",&option);
  79.                 if(option==1)
  80.                 {
  81.                         int data;
  82.                         scanf("%d",&data);
  83.                         insert(start,data);
  84.                 }
  85.                 else if(option==2)
  86.                 {
  87.                         int data;
  88.                         scanf("%d",&data);
  89.                         delete(start,data);
  90.                 }
  91.                 else if(option==3)
  92.                 {
  93.                         printf("The list is ");
  94.                         print(start->next);
  95.                         printf("\n");
  96.                 }
  97.                 else if(option==4)
  98.                 {
  99.                         int data;
  100.                         scanf("%d",&data);
  101.                         int result = find(start,data);
  102.                         if(result)
  103.                         {
  104.                                 printf("The element is found \n");
  105.                         }
  106.                         else
  107.                         {
  108.                                 printf("The element is not found\n");
  110.                         }
  111.                 }
  112.         }
  115. }

双链表

双链列表也称为双向列表或双向链。 在双向链表中，两个链接字段被保留，而不是像在单个链表中那样保留一个链接字段。 双链表是一个线性数据结构，其中每个节点都有两个链接，其中第一个链接用于指向前一个节点，下一个链接指向下一个节点。 在双向链表上执行的操作是插入，删除，搜索和遍历。

链表 - 图6

在哪里使用双链表？

  1. 用于表示游戏中的纸牌。

  2. 在具有“最近使用”列表的应用中使用。

  3. 在 Word 或 Photoshop 中用作撤消功能。

  4. 在浏览器缓存中使用，它使我们可以单击后退按钮。

使用 C 实现双向链表

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. typedef struct Node
  4. {
  5.         int data;
  6.         struct Node *next;
  7.         struct Node *prev;
  8. }node;
  9. void insert(node *ptr, int data)
  10. {
  12.         while(ptr->next!=NULL)
  13.         {
  14.                 ptr = ptr -> next;
  15.         }
  17.         ptr->next = (node *)malloc(sizeof(node));
  18.         (ptr->next)->prev = ptr;
  19.         ptr = ptr->next;
  20.         ptr->data = data;
  21.         ptr->next = NULL;
  22. }
  23. int find(node *ptr, int key)
  24. {
  25.         ptr =  ptr -> next;
  27.         while (ptr!=NULL)
  28.         {
  29.                 if(ptr->data == key)
  30.                 {
  31.                         return 1;
  32.                 }
  33.                 ptr = ptr -> next;
  34.         }
  36.         return 0;
  37. }
  38. void delete(node *ptr, int data)
  39. {
  41.         while(ptr->next!=NULL && (ptr->next)->data != data)
  42.         {
  43.                 ptr = ptr -> next;
  44.         }
  45.         if(ptr->next==NULL)
  46.         {
  47.                 printf("The element %d is not present in the list\n",data);
  48.                 return;
  49.         }
  51.         node *temp;
  52.         temp = ptr -> next;  
  53.         ptr->next = temp->next;
  54.         temp->prev =  ptr;
  55.         free(temp);
  56.         return;
  57. }
  58. void print(node *ptr)
  59. {
  60.         if(ptr==NULL)
  61.         {
  62.                 return;
  63.         }
  64.         printf("%d ",ptr->data);
  65.         print(ptr->next);
  66. }
  67. int main()
  68. {
  69.         node *start,*temp;
  70.         start = (node *)malloc(sizeof(node));
  71.         temp = start;
  72.         temp -> next = NULL;
  73.         temp -> prev = NULL;
  75.         printf("1. Insert\n");
  76.         printf("2. Delete\n");
  77.         printf("3. Print\n");
  78.         printf("4. Find\n");
  79.         while(1)
  80.         {
  81.                 int option;
  82.                 scanf("%d",&option);
  83.                 if(option==1)
  84.                 {
  85.                         int data;
  86.                         scanf("%d",&data);
  87.                         insert(start,data);
  88.                 }
  89.                 else if(option==2)
  90.                 {
  91.                         int data;
  92.                         scanf("%d",&data);
  93.                         delete(start,data);
  94.                 }
  95.                 else if(option==3)
  96.                 {
  97.                         printf("The list is ");
  98.                         print(start->next);
  99.                         printf("\n");
  100.                 }
  101.                 else if(option==4)
  102.                 {
  103.                         int data;
  104.                         scanf("%d",&data);
  105.                         int result = find(start,data);
  106.                         if(result)
  107.                         {
  108.                                 printf("The element is found\n");
  109.                         }
  110.                         else
  111.                         {
  112.                                 printf("The element is not found\n");
  114.                         }
  115.                 }
  116.         }
  119. }

循环链表

循环链表是有点复杂的链接数据结构。 在此列表中，我们可以在列表中的任何位置插入元素，而在数组中，我们不能在列表中的任何位置插入元素，因为它在连续内存中。 在此列表中，上一个元素存储下一个元素的地址，最后一个元素存储第一个元素的地址。 列表中的元素以圆形的方式相互指向，形成圆形的链。 该列表具有动态大小，这意味着可以在需要时分配内存。

链表 - 图7

在哪里使用循环链表？

使用此列表的实际应用是在其上运行多个应用的​​PC。 循环链表在操作系统中很常见，因为它会将正在运行的应用放在列表中，并且当列表即将到达其末端时，操作系统很容易使用循环链表，因为操作系统可以循环运行到列表的最前面。 将该时隙分配给列表中的每个应用。

在 C 中实现循环链​​表

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. struct node
  4. {
  5.         int data;
  6.         struct node *next;
  7. }node;
  8. void insert(node *pointer, int data)
  9. {
  10.         node *start = pointer;
  11.         while(pointer->next!=start)
  12.         {
  13.                 pointer = pointer -> next;
  14.         }
  15.         pointer->next = (node *)malloc(sizeof(node));
  16.         pointer = pointer->next;
  17.         pointer->data = data;
  18.         pointer->next = start;
  19. }
  20. void delete(node *pointer, int data)
  21. {
  22.         node *start = pointer;
  23.         while(pointer->next!=start && (pointer->next)->data != data)
  24.         {
  25.                 pointer = pointer -> next;
  26.         }
  27.         if(pointer->next==start)
  28.         {
  29.                 printf("Element %d is not present in the list\n",data);
  30.                 return;
  31.         }
  32.         node *temp;
  33.         temp = pointer -> next;
  34.         pointer->next = temp->next;
  35.         free(temp);
  36.                    free( )
  37.           return;
  38. }
  39. void display(node *start,node *pointer)
  40. {
  41.         if(pointer = = start)
  42.         {
  43.                 return;
  44.         }
  45.         printf("%d ",pointer->data);
  46.         display(start,pointer->next);
  47. }
  48. void main()
  49. {
  50.         node *start,*temp;
  51.         start = (struct node *)malloc(sizeof(struct node));
  52.         temp = start;
  53.         temp -> next = start;
  54.         printf("1. Insert\n");
  55.         printf("2. Delete\n");
  56.         printf("3. Display\n");
  57.         while(1)
  58.         {
  59.                 int query;
  60.                 scanf("%d",&query);
  61.                 if(query==1)
  62.                 {
  63.                         int data;
  64.                         scanf("%d",&data);
  65.                         insert(start,data);
  66.                 }
  67.                 else if(query==2)
  68.                 {     int data;
  69.                         scanf("%d",&data);
  70.                         delete(start,data);
  71.                 }
  72.                 else if(query==3)
  73.                 {      printf("The list is ");
  74.                         display(start,start->next);
  75.                         printf("\n");
  76.                 }        }
  77. getch( );
  78. }

线性链表

在链表中，我们可以通过三种方式插入元素：

  • 插入列表的开头。

  • 插入列表的中间。

  • 插入到列表的末尾。

在将节点插入列表之前，我们将使用关键字struct创建一个结构。 例如：

  1. struct node
  3. { int data;
  5. struct node *next;
  7. };
  9. struct employee *start=NULL, *temp,*q;

并且在定义了结构之后，在从列表中插入或删除节点的同时，给出了特定的功能定义或功能原型。 例如：

  1. void insertbeg( );
  3. void insertmiddle( );
  5. void insertlast( );
  7. void deletebeg( );

上面给出的函数定义在main函数之前定义，即void main()或int main()。

在开头的插入元素

在开始时插入节点的步骤：

  1. 创建一个新节点。

  2. 在数据部分输入数据。

  3. 将地址部分或下一部分设为NULL。

  4. 现在将这个新创建的节点附加到起始或头部。

  5. 现在，将此起始节点设为起始节点或标头节点。

在中间的插入元素

在中间插入节点的步骤：

  1. 将要添加的新节点的数据写入列表及其位置。

  2. 通过调用malloc()创建一个新的空节点。

  3. 将数据插入新节点的数据部分。

  4. 将此新节点添加到列表中的所需位置。

  5. 转到步骤 1，直到您在列表中添加了所有值。

实现

  1. void insertmiddle()
  3. { int pos,i,num;
  5. if(start==NULL)
  7. { printf("\nList is empty!! Sorry...");
  9. }
  11. temp=(struct node*)malloc(sizeof(struct node));
  13. printf("\nEnter the details:");
  15. scanf("%d",num);
  17. printf("\nEnter position:");
  19. scanf("%d",&pos);
  21. temp->data=num;
  23. q=start
  25. for(i=1;i<pos-1;pos++)
  27. {
  29. if(q->next==NULL)
  31. { printf("\nLess elements in the list");
  33. }
  35. q=q->next;
  37. }
  39. temp->next=q->next;
  41. q->next=temp;
  43. getch();
  45. }

在列表的末尾插入元素：

最后插入节点的步骤：

  1. 创建新节点。
  2. 将数据输入到节点的数据部分。
  3. 将节点的下一部分设为NULL。
  4. 要在最后一个位置插入节点，因此我们必须遍历到最后一个节点。
  5. 在最后一个节点和新节点之间建立链接。

实现

  1. void insertlast()
  3. { int num;
  5. temp=(struct node*)malloc(sizeof(struct node));
  7. printf("\nEnter the details:");
  9. scanf("%d",&num);
  11. temp->data=num;
  13. temp->next=NULL;
  15. if(start==NULL) //If list is empty
  17. {
  19. start=temp;
  21. }
  23. else
  25. {
  27. q=start;
  29. while(q->next!=NULL)
  31. q=q->next;
  33. q->next=temp;
  35. }
  36. }

删除

可以通过三种方式删除该元素：

  • 从列表的开头删除。

  • 从列表的中间删除。

  • 从列表末尾删除。

从开头删除元素

  1. Implementation
  3. void deletebeg()
  5. { if(start==NULL)
  7. { printf("\nThe list is empty...");
  9. }
  11. else
  13. {
  15. q=start;
  17. start=start->next;
  19. free(q);
  21. printf("\nElement deleted...");
  23. }
  25. }

从中间删除元素

实现

  1. void deletemiddle()
  3. { int pos,i;
  5. if(start==NULL)
  7. { printf("\nThe list is empty...");
  9. }
  11. printf("\nEnter position to delete:");
  13. scanf("%d",&pos);
  15. for(i=1;i<pos-1;pos++)
  17. {
  19. if(q->next==NULL)
  21. {
  23. printf("\nLess elements...");
  25. getch();
  27. }
  29. q=q->next;
  31. }
  33. temp=q->next;
  35. q->next=temp->next;
  37. free(temp);
  39. printf("\nElement deleted...");
  41. getch();
  43. }

从末尾删除元素

实现

  1. void deletelast()
  3. { if(start==NULL)
  5. {
  7. printf("\nThe list is empty...");
  9. }
  11. else
  13. {
  15. q=start;
  17. while(q->next->next!=NULL)
  19. q=q->next;
  21. temp=q->next;
  23. q->next=NULL;
  25. free(temp);
  27. printf("\nElement deleted...");
  29. }
  31. }

显示

在执行任何操作后显示列表的元素。

  1. void display()
  3. { struct node *q;
  5. q=start;
  7. while(q!=NULL)
  9. {
  11. printf("%d\t",q->data);
  13. q=q->next;
  15. }
  17. getch();
  19. }