C 语言通用链表

2024年8月28日 | 14 分钟阅读

链表是一种线性数据集合，其元素的顺序由其在内存中的物理位置决定，而不是由其物理顺序决定。相反，每个元素都指向下一个元素。它是一种由节点组成的数据结构，这些节点代表一个序列。因此，在最基本的形式中，每个节点都包含数据和一个指向序列中下一个节点的引用（链接）。在迭代过程中，这种结构可以有效地从序列中的任何位置插入和删除元素。更复杂的变体包含额外的链接，可以更有效地在任意位置插入和删除节点。

链表的一个缺点是访问时间是线性的，并且难以流水线化。无法提供更快的访问，例如随机访问。与链表相比，数组具有更好的缓存局部性。

链表是最基本且广泛使用的数据结构之一。它们可用于实现各种其他流行的抽象数据类型，例如列表、堆栈、队列、关联数组和 S 表达式；但是，直接实现这些数据结构而不使用链表作为基础或底层数据结构也并不罕见。

与传统数组相比，链表的主要优点是可以在不重新分配或重组整个结构的情况下轻松插入或删除列表元素，因为数据项不需要在内存或磁盘上连续存储，而运行时重组数组是一个成本更高的操作。通过在列表遍历过程中保留被添加或删除链接之前的链接，链表可以在常数次操作中在列表的任何位置添加和删除节点。然而，由于简单的链表不支持数据随机访问或高效索引，许多基本操作，例如获取列表的最后一个节点、定位包含给定数据的节点或定位应插入新节点的the位置，可能需要遍历大部分或所有列表元素。使用链表的优点和缺点列在下面。

动态数组是一种数据结构，它在内存中以连续方式分配所有元素，并跟踪当前元素的数量。如果动态数组的分配空间超出，它将被重新分配并（可能）复制，这是一个昂贵的操作。与动态数组相比，使用链表有几个优点。在列表的特定位置插入或删除元素是一个恒定时间操作（除非我们已经为要删除的节点之前或插入点之前的节点建立了指针）。相比之下，在动态数组的随机位置插入平均需要移动一半的元素，在最坏的情况下需要移动所有元素。虽然可以通过将数组槽标记为“空闲”来在恒定时间内“删除”数组中的元素，但这会导致碎片化，从而影响迭代性能。

根据指针的类型，链表的节点具有链表节点指针的方向。

链表类型

链表有不同的类型，其中一些主要的链表类型是：

单向链表
双向链表
循环链表
双向循环链表

单向链表

在单向链表中，单向链表的节点指向存储下一个节点的内存位置的地址。同样，以这种方式，所有节点都存储各自下一个节点的地址。除了最后一个节点，最后一个节点的指针中的地址为 NULL，表示它是链表的最后一个节点。

代码

现在让我们看一个示例代码，用于在 C 编程语言中创建单向链表，向列表中添加元素，然后遍历单向链表。

/* A sample C code to perform the following functions on Singly Linked list Insert, Delete, Display and Count Operations */
/* All Operations Example Program Using Functions in C*/
// stdio library is included to use the input output functionalities in the program
#include <stdio.h>
// the malloc library is included to dynamically allocate memory to the nodes of the Singly Linked list
#include <malloc.h>
#include <stdlib.h>
// a struct named node is defined that will represent the node of the Singly Linked list
// the struct object has two variables in it named value and next
struct node {
  // the value variable is of integer type and will be used to store the value associated with that particular node of the Singly Linked list
  int value;
  // the next variable is of struct node* type and will be used to store the address of the next node of the Singly Linked list
  struct node *next;
};
void insert();
void display();
void delete();
int count();
// the struct object named node is typedef with DATA_NODE for easier interpretation 
typedef struct node DATA_NODE;
// An object of the DATA_NODE (which is struct node) named head_node is created and initialized with 0 that acts as the head node of the Singly Linked list. 
DATA_NODE *head_node = 0;
// An object of the DATA_NODE (struct node) named first_node is created and initialized with 0, which acts as the first node of the Singly Linked list.
DATA_NODE *first_node = 0;
// An object of the DATA_NODE (which is struct node) named temp_node is created and initialized with 0 that will be used to store the node of the Singly Linked list temporarily.
DATA_NODE *temp_node = 0;
// An object of the DATA_NODE (which is struct node) named next_node,prev_node is created that will be used to temproray store the node of Singly Linked list.
DATA_NODE *prev_node;
DATA_NODE next_node;
// a variable named data of integer type is created to store the value associated with that particular node of the Singly Linked list 
int data;
// A function named insert is written to add a new node to the Singly Linked list 
void insert() {
  // Data to be associate with that particular node of the Singly Linked list is taken as input from the user
  printf("\nEnter Element for Insert Linked list : \n");
  // the data enetred by the user is stored in the data variable
  scanf("%d", &data);
  // a temporary node is created with the added new data by the user, and this new temporary node is allocated memory by using the malloc function 
  temp_node = (DATA_NODE *) malloc(sizeof (DATA_NODE));
  // now the data added by the user is associated with this particular new temproray node
  temp_node->value = data;
  // while inserting a new node to the Singly linked list, it is checked whether the first_node is zero or not,
  // if first_node is zero, that means there are no nodes present in the Singly Linked list at that time, so that
  // new node is added at the start of the Singly Linked list, which will act as the head of the Linked list
  // if the first_node is not zero, then the new node is added after that already existing node   
  // this if condition will check the value of first_node varible
  if (first_node == 0) {
    // if value of first_node varible is zero then it will become the head of the Singly Linked list
    first_node = temp_node;
  } else {
    // if the value is not zero, then the address of this new node will be added to the pointer of the already last existing node in the Singly Linked list
    head_node->next = temp_node;
  }
  // and the address that is stored in the newly added node is 0 representing it to be the last node of the Singly Linked list   
  temp_node->next = 0;
  head_node = temp_node;
  fflush(stdin);
}//end of the insert function
// A function named delete was written to delete a node from the Singly Linked list
void delete() {
  int countvalue = 0;
  int pos = 0;
  int i = 0;
  countvalue = count();
  temp_node = first_node;
  printf("\nDisplay Linked list : \n");
  // The position of the node that we want to delete from the Singly Linked list is taken as input from the user
  printf("\nEnter Position for Delete Element : \n");
  // The position of the node that we want to delete from the Singly Linked list entered by the user is stored in the pos variable
  scanf("%d", &pos);
  // Now, for deleting a node from the Singly Linked list, first we need to traverse to that position and then delete that node from the Singly Linked list  
  // By deleting, we mean to add the pointer of the previous node to the next node of the node whose position is entered by the user.
  if (pos > 0 && pos <= countvalue) {    
    // this is the case when the user wants to delete the head node of the Singly Linked list
    if (pos == 1) {
      temp_node = temp_node -> next;
      first_node = temp_node;
      // Once the node is deleted a message is displayed to the user
      printf("\nDeleted Successfully \n\n");
    } else {
      while (temp_node != 0) {
        if (i == (pos - 1)) {
          prev_node->next = temp_node->next;
          if(i == (countvalue - 1))
          {
			  head_node = prev_node;
		  }
          // Once the node is deleted a message is displayed to the user
          printf("\nDeleted Successfully \n\n");
          break;
        } else {
          i++;
          prev_node = temp_node;
          temp_node = temp_node -> next;
        }
      }
    }
    // if the position that is entered by the user is out of the range of the length of the  Singly Linked list then an error message saying Invalid position is displayed
  } else
    printf("\nInvalid Position \n\n");
}// end of delete function
// A function named display is written to print the data in the nodes of the Singly Linked list 
void display() {
  //an integer variable named count is initialized with zero that will keep the total count of the number of nodes in the Singly Linked list 
  int count = 0;
  // the temp_node variable is initialized with the first_node variable, which is the first node of the Singly Linked list
  temp_node = first_node;
  printf("\nDisplay Linked list : \n");
  // The Singly Linked list is traversed untill the last element of the Singly Linked list is encountered
  while (temp_node != 0) {
    // while traversing the Singly Linked list the data present in the each node of the Singly Linked list is printed
    printf("# %d # ", temp_node->value);    
    // the count variable is incremented after traversing each node of the Singly Linked list 
    count++;
    temp_node = temp_node -> next;
  }  
  // after traversing each node of the Singly Linked list, the total count of the number of nodes in the Singly Linked list is printed
  printf("\nNo Of Items In Linked list : %d\n", count);
}// end of display function
// A function named count is written to count the total number of nodes in the Singly Linked list
int count() {  
  //an integer variable named count is initialized with zero that will keep the total count of the number of nodes in the Singly Linked list 
  int count = 0;
  // the temp_node variable is initialized with the first_node variable, which is the first node of the Singly Linked list
  temp_node = first_node;
  // The Singly Linked list is traversed until the last element of the Singly Linked list is encountered
  while (temp_node != 0) {
    // the count varible is incremented after traversing each node of the Singly Linked list
    count++;
    temp_node = temp_node -> next;
  }
  // after traversing each node of the Singly Linked list, the total count of the number of nodes in the Singly Linked list is printed
  printf("\nNo Of Items In Linked list : %d\n", count);
  return count;
}// end of count function
// main function is written to call all the functionalities functions of the Singly Linked list written above
int main() {
  char ch;
            // Do-while loop
            // Do part for performing actions
            do
            // Menu is displayed
            // Users enter 'y' to continue 'n' if
            // entered by user , the program terminates
            {
                  // Menu
                  // Display messages
                  printf("Please Choose one of the Operations::\n");
                  printf("1. To Insert Data in the Singly Linked list.\n");
                  printf("2. To Delete Data from the Singly Linked list.\n");
                  printf("3. To Display Data present in the Singly Linked list.\n");
                  printf("4. To Display the count of nodes in the Singly Linked list.\n");
                  printf("\n");
                  int choice;
                  scanf("%d",&choice);
                  // Switch case
                  switch (choice) {
                  // Case 1
                  case 1:
                        insert();
                        // Display message
                        printf("Data Added Sucessfully.\n");
                        // Break statement to terminate a case
                        break;
                  // Case 2
                  case 2:
                        // Display message
                        delete();
                        // Break statement to terminate a case
                        break;
                  // Case 3
                  case 3:
                        // Display message
                        display();
                        // Break statement to terminate a case
                        break;
                  // Case 2
                  case 4 :
                        // Display message
                        count();
                        // Break statement to terminate a case
                        break;
                  default:
                        // Print statement
                        printf("Please enter a valid option from the menu to proceed further.\n \n");
                        // Break statement
                        break;
                  }
                  printf("\nType [N or n] to terminate the program.\nType [Y or y] to continue the program.\n");
                  scanf(" %c",&ch);                  
            } while (!(ch == 'N' || ch == 'n'));
  return 0;
}// end of main function

输出

上面的代码产生以下输出：

Please Choose one of the Operations::
1. To Insert Data in the Singly Linked list.
2. To Delete Data from the Singly Linked list.
3. To Display Data present in the Singly Linked list.
4. To Display the count of nodes in the Singly Linked list.
1
Enter Element for Insert Linked list: 
2
Data Added Successfully.
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations::
1. To Insert Data in the Singly Linked list.
2. To Delete Data from the Singly Linked list.
3. To Display Data present in the Singly Linked list.
4. To Display the count of nodes in the Singly Linked list.
1
Enter Element for Insert Linked list: 
3
Data Added Successfully.
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations::
1. To Insert Data in the Singly Linked list.
2. To Delete Data from the Singly Linked list.
3. To Display Data present in the Singly Linked list.
4. To Display the count of nodes in the Singly Linked list.
1
Enter Element for Insert Linked list: 
6
Data Added Successfully.
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations::
1. To Insert Data in the Singly Linked list.
2. To Delete Data from the Singly Linked list.
3. To Display Data present in the Singly Linked list.
4. To Display the count of nodes in the Singly Linked list.
1
Enter Element for Insert Linked list: 
89
Data Added Successfully.
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations::
1. To Insert Data in the Singly Linked list.
2. To Delete Data from the Singly Linked list.
3. To Display Data present in the Singly Linked list.
4. To Display the count of nodes in the Singly Linked list.
1
Enter Element for Insert Linked list: 
56
Data Added Successfully.
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations::
1. To Insert Data in the Singly Linked list.
2. To Delete Data from the Singly Linked list.
3. To Display Data present in the Singly Linked list.
4. To Display the count of nodes in the Singly Linked list.
1
Enter Element for Insert Linked list: 
31
Data Added Successfully.
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations::
1. To Insert Data in the Singly Linked list.
2. To Delete Data from the Singly Linked list.
3. To Display Data present in the Singly Linked list.
4. To Display the count of nodes in the Singly Linked list.
1 
Enter Element for Insert Linked list: 
78
Data Added Successfully.
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations::
1. To Insert Data in the Singly Linked list.
2. To Delete Data from the Singly Linked list.
3. To Display Data present in the Singly Linked list.
4. To Display the count of nodes in the Singly Linked list.
3
Display Linked list: 
# 2 # # 3 # # 6 # # 89 # # 56 # # 31 # # 78 # 
No Of Items In Linked list: 7
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations::
1. To Insert Data in the Singly Linked list.
2. To Delete Data from the Singly Linked list.
3. To Display Data present in the Singly Linked list.
4. To Display the count of nodes in the Singly Linked list.
2
No of Items In Linked list: 7
Display Linked list: 
Enter Position for Delete Element: 
4
Deleted Successfully 
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations::
1. To Insert Data in the Singly Linked list.
2. To Delete Data from the Singly Linked list.
3. To Display Data present in the Singly Linked list.
4. To Display the count of nodes in the Singly Linked list.
3
Display Linked list: 
# 2 # # 3 # # 6 # # 56 # # 31 # # 78 # 
No Of Items In Linked list: 6
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations::
1. To Insert Data in the Singly Linked list.
2. To Delete Data from the Singly Linked list.
3. To Display Data present in the Singly Linked list.
4. To Display the count of nodes in the Singly Linked list.
4
No of Items in Linked list: 6
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
n

在上面的代码中，我们为链表的各种功能创建了不同的函数，例如向链表中插入新节点，显示链表中所有节点的数据，删除链表中特定位置的特定节点，以及计算链表中节点的总数。

在向单向链表中插入新节点时，会检查第一个节点是否为零，

如果第一个节点为零，则此时单向链表中没有节点，因此新节点将添加到单向链表的开头，它将充当链表的头。
如果第一个节点不为零，则添加新节点。之后，链表中已存在最后一个节点。要删除链表中的节点，首先需要从用户那里获取该节点的索引。一旦我们知道了该节点的位置，下一步就是遍历到该节点，并在到达该节点后，我们要删除的节点的上一个节点存储了该节点的地址，但我们需要将其更改为该位置的下一个节点。要打印所有节点中的数据，我们需要从头节点（第一个节点）开始遍历整个列表，直到最后一个节点，并在遍历每个节点时显示该节点中的数据。对于打印链表中节点的总数，也遵循类似的方法。

下一主题C 语言中的 isalnum() 函数

C 语言通用链表

链表类型

单向链表

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C 语言教程

C 语言控制语句

C 语言函数

C 语言数组

C 语言指针

C 语言动态内存

C 语言字符串

C 语言数学

C 语言结构体和联合体

C 语言文件处理

C 语言预处理器

C 语言命令行

C 语言程序

C 语言面试

选择题

C 语言编程测试

C 语言基础测试

C 语言控制语句测试

C 语言函数测试

C 语言数组测试

C 语言指针测试

C 语言字符串测试

C 语言结构体测试

C 语言预处理器测试

数学

C 语言杂项

C 语言通用链表

链表类型

单向链表

相关帖子

C 语言字符串连接

C 语言逻辑非 (!) 运算符

C 语言 generic 关键字

C 语言高斯-赛德尔迭代法

字符中的数字

C 语言栈

C 语言字符集

C 语言结构体指针

GCC 编译器内置函数

C 语言 ctype.h

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器