srcmini本文概述
- 链接列表可以定义为随机存储在内存中的称为节点的对象的集合。
- 节点包含两个字段, 即存储在该特定地址的数据和包含存储器中下一个节点的地址的指针。
- 列表的最后一个节点包含指向null的指针。
链表的用途
- 该列表不需要连续存在于内存中。该节点可以驻留在内存中的任何位置, 并链接在一起以创建一个列表。这实现了空间的优化利用。
- 列表大小限于内存大小, 不需要事先声明。
- 空节点不能出现在链接列表中。
- 我们可以将原始类型或对象的值存储在单链表中。
为什么在数组上使用链表？
到目前为止, 我们一直在使用数组数据结构来组织要单独存储在内存中的元素组。但是, Array具有几个优点和缺点, 必须知道这些优点和缺点才能确定将在整个程序中使用的数据结构。
数组包含以下限制：
- 在程序中使用数组之前, 必须事先知道数组的大小。
- 增大阵列的大小是一个耗时的过程。在运行时几乎不可能扩展阵列的大小。
- 数组中的所有元素都需要连续存储在内存中。在数组中插入任何元素都需要移动其所有前任元素。
链表是可以克服数组所有限制的数据结构。使用链表非常有用, 因为,
- 它动态分配内存。链表的所有节点不连续地存储在内存中, 并在指针的帮助下链接在一起。
- 调整大小不再是问题, 因为在声明时我们不需要定义其大小。列表根据程序的需求而增长, 并受限于可用内存空间。
单链表或单向链
单链列表可以定义为元素的有序集合的集合。元素的数量可以根据程序的需要而变化。单链列表中的节点由两部分组成：数据部分和链接部分。节点的数据部分存储将由该节点表示的实际信息, 而节点的链接部分存储其直接后继者的地址。
单向链表或单链表只能在一个方向上遍历。换句话说, 我们可以说每个节点仅包含下一个指针, 因此我们不能反向浏览列表。
考虑一个示例, 该示例将学生在三个主题中获得的分数存储在一个链接列表中, 如图所示。
在上图中, 箭头表示链接。每个节点的数据部分包含学生在不同学科中获得的分数。列表中的最后一个节点由存在于最后一个节点的地址部分中的空指针标识。在列表的数据部分中, 我们可以具有所需的任意多个元素。
复杂
| 数据结构 | 时间复杂度 | 空间兼容性 | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Average | Worst | Worst | |||||||
| Access | Search | Insertion | Deletion | Access | Search | Insertion | Deletion | ||
| 单链表 | θ(n) | θ(n) | θ(1) | θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
单链表上的操作
可以对单链表执行各种操作。下面列出了所有此类操作。
节点创建
struct node
{
int data;
struct node *next;
};
struct node *head, *ptr;
ptr = (struct node *)malloc(sizeof(struct node *));插入
可以在不同位置执行插入到单链接列表的操作。根据要插入的新节点的位置, 将插入分为以下类别。
| 序号 | 运作方式 | 描述 |
|---|---|---|
| 1 | 开始插入 | 它涉及在列表的前面插入任何元素。我们只需要进行一些链接调整, 以使新节点成为列表的头部。 |
| 2 | 在列表末尾插入 | 它涉及在链表的最后插入。新节点可以作为列表中的唯一节点插入, 也可以作为最后一个节点插入。在每种情况下实现不同的逻辑。 |
| 3 | 在指定节点后插入 | 它涉及插入到链表的指定节点之后。我们需要跳过所需的节点数才能到达要在其后插入新节点的节点。 。 |
删除和遍历
从单个链接列表中删除节点可以在不同位置执行。根据要删除的节点的位置, 将操作分为以下类别。
| 序号 | 运作方式 | 描述 |
|---|---|---|
| 1 | 开始删除 | 它涉及从列表的开头删除节点。这是所有操作中最简单的操作。它只需要对节点指针进行一些调整即可。 |
| 2 | 列表末尾删除 | 它涉及删除列表的最后一个节点。该列表可以为空或完整。针对不同的场景实现了不同的逻辑。 |
| 3 | 指定节点后删除 | 它涉及删除列表中指定节点之后的节点。我们需要跳过所需的节点数才能到达该节点, 然后删除该节点。这需要遍历列表。 |
| 4 | Traversing | 在遍历中, 我们只需访问列表的每个节点至少一次以对其执行一些特定操作, 例如, 打印列表中存在的每个节点的数据部分。 |
| 5 | Searching | 在搜索中, 我们将列表的每个元素与给定元素进行匹配。如果在任何位置找到该元素, 则返回该元素的位置, 否则返回null。 。 |
C中的链接列表：菜单驱动程序
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *head;
void beginsert ();
void lastinsert ();
void randominsert();
void begin_delete();
void last_delete();
void random_delete();
void display();
void search();
void main ()
{
int choice =0;
while(choice != 9)
{
printf("\n\n*********Main Menu*********\n");
printf("\nChoose one option from the following list ...\n");
printf("\n===============================================\n");
printf("\n1.Insert in begining\n2.Insert at last\n3.Insert at any random location\n4.Delete from Beginning\n
5.Delete from last\n6.Delete node after specified location\n7.Search for an element\n8.Show\n9.Exit\n");
printf("\nEnter your choice?\n");
scanf("\n%d", &choice);
switch(choice)
{
case 1:
beginsert();
break;
case 2:
lastinsert();
break;
case 3:
randominsert();
break;
case 4:
begin_delete();
break;
case 5:
last_delete();
break;
case 6:
random_delete();
break;
case 7:
search();
break;
case 8:
display();
break;
case 9:
exit(0);
break;
default:
printf("Please enter valid choice..");
}
}
}
void beginsert()
{
struct node *ptr;
int item;
ptr = (struct node *) malloc(sizeof(struct node *));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter value\n");
scanf("%d", &item);
ptr->data = item;
ptr->next = head;
head = ptr;
printf("\nNode inserted");
}
}
void lastinsert()
{
struct node *ptr, *temp;
int item;
ptr = (struct node*)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter value?\n");
scanf("%d", &item);
ptr->data = item;
if(head == NULL)
{
ptr -> next = NULL;
head = ptr;
printf("\nNode inserted");
}
else
{
temp = head;
while (temp -> next != NULL)
{
temp = temp -> next;
}
temp->next = ptr;
ptr->next = NULL;
printf("\nNode inserted");
}
}
}
void randominsert()
{
int i, loc, item;
struct node *ptr, *temp;
ptr = (struct node *) malloc (sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter element value");
scanf("%d", &item);
ptr->data = item;
printf("\nEnter the location after which you want to insert ");
scanf("\n%d", &loc);
temp=head;
for(i=0;i<loc;i++)
{
temp = temp->next;
if(temp == NULL)
{
printf("\ncan't insert\n");
return;
}
}
ptr ->next = temp ->next;
temp ->next = ptr;
printf("\nNode inserted");
}
}
void begin_delete()
{
struct node *ptr;
if(head == NULL)
{
printf("\nList is empty\n");
}
else
{
ptr = head;
head = ptr->next;
free(ptr);
printf("\nNode deleted from the begining ...\n");
}
}
void last_delete()
{
struct node *ptr, *ptr1;
if(head == NULL)
{
printf("\nlist is empty");
}
else if(head -> next == NULL)
{
head = NULL;
free(head);
printf("\nOnly node of the list deleted ...\n");
}
else
{
ptr = head;
while(ptr->next != NULL)
{
ptr1 = ptr;
ptr = ptr ->next;
}
ptr1->next = NULL;
free(ptr);
printf("\nDeleted Node from the last ...\n");
}
}
void random_delete()
{
struct node *ptr, *ptr1;
int loc, i;
printf("\n Enter the location of the node after which you want to perform deletion \n");
scanf("%d", &loc);
ptr=head;
for(i=0;i<loc;i++)
{
ptr1 = ptr;
ptr = ptr->next;
if(ptr == NULL)
{
printf("\nCan't delete");
return;
}
}
ptr1 ->next = ptr ->next;
free(ptr);
printf("\nDeleted node %d ", loc+1);
}
void search()
{
struct node *ptr;
int item, i=0, flag;
ptr = head;
if(ptr == NULL)
{
printf("\nEmpty List\n");
}
else
{
printf("\nEnter item which you want to search?\n");
scanf("%d", &item);
while (ptr!=NULL)
{
if(ptr->data == item)
{
printf("item found at location %d ", i+1);
flag=0;
}
else
{
flag=1;
}
i++;
ptr = ptr -> next;
}
if(flag==1)
{
printf("Item not found\n");
}
}
}
void display()
{
struct node *ptr;
ptr = head;
if(ptr == NULL)
{
printf("Nothing to print");
}
else
{
printf("\nprinting values . . . . .\n");
while (ptr!=NULL)
{
printf("\n%d", ptr->data);
ptr = ptr -> next;
}
}
}输出：
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit
Enter your choice?
1
Enter value
1
Node inserted
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit
Enter your choice?
2
Enter value?
2
Node inserted
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit
Enter your choice?
3
Enter element value1
Enter the location after which you want to insert 1
Node inserted
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit
Enter your choice?
8
printing values . . . . .
1
2
1
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit
Enter your choice?
2
Enter value?
123
Node inserted
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit
Enter your choice?
1
Enter value
1234
Node inserted
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit
Enter your choice?
4
Node deleted from the begining ...
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit
Enter your choice?
5
Deleted Node from the last ...
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit
Enter your choice?
6
Enter the location of the node after which you want to perform deletion
1
Deleted node 2
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit
Enter your choice?
8
printing values . . . . .
1
1
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit
Enter your choice?
7
Enter item which you want to search?
1
item found at location 1
item found at location 2
*********Main Menu*********
Choose one option from the following list ...
===============================================
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit
Enter your choice?
9
评论前必须登录！
注册