Importance of this Section#
Because the singly linked list is a very basic data structure, once you learn how to describe a singly linked list using the C language, describing other data structures such as heaps, stacks, doubly linked lists, and hash tables will be a piece of cake. If you are a beginner, it is highly recommended that you type the code yourself.
Nodes of a Singly Linked List#
As shown in the figure, a node in a singly linked list consists of a data field and a pointer field. They can be considered as a whole and are called nodes. Later, we will use a structure to represent a node.
The data field, as the name suggests, is where the data is stored.
The pointer field is used to store the address of the next node.
Representation of a Singly Linked List#
A singly linked list is a linked representation and implementation of a linear list. The nodes are linked together to form a singly linked list.
Definition of the Structure Representing a Node#
How do we describe a node using the C language? Here we use struct.
struct node {
/* Next node */
struct node *next;
/* Value */
int data;
};
First, we define a structure, and the tag of the structure is node.
Second, it has two attributes: one is the data of type int, which is the data field mentioned earlier. The other is the pointer field.
How do we understand struct node *next?
Remember, the pointer field is used to store pointer variables, and this variable is called next. Also, because this pointer points to the address of the next node, in other words, this pointer points to a structure we defined to represent a node. Therefore, the type of this pointer variable is struct node. The asterisk * indicates that it is a pointer variable. So when combined, it becomes struct node *next.
Finally, for convenience, we can use the typedef keyword to give an alias to struct node.
typedef struct node {
/* Next node */
struct node *next;
/* Value */
int data;
} list;
This way, in the subsequent code writing, list is equivalent to struct node.
For example, when we use this structure to create a new node, list *new_node is equivalent to struct node *new_node.
Creating a Singly Linked List#
list * create_list()
{
/* Create a new node, and since we used the typedef keyword, node *head is equivalent to struct node *head */
list *head = (list *)malloc(sizeof(list));
if(head==NULL) return NULL;
/* Initialize the node */
head->data = 0; // The data field of the head node is used to represent the length of the linked list
head->next = NULL;
return head;
}
This function creates a singly linked list and returns the head pointer.
The head pointer is a pointer that points to the address of the head node, and it is of the same type as the pointer that points to the next node in the node.
First, we allocate a block of memory of size list using the malloc function and return a pointer to the first address of this memory block, which is then assigned to the head pointer variable.
Then, we check if this pointer is NULL. If it is NULL, it means that the memory allocation failed (which is generally unlikely).
Next, we initialize the node.
Finally, the function returns the head pointer and ends.
Why set a head node?
The data field of the head node is generally meaningless. It is set here for the convenience of later insertion and deletion operations, and the head node is not necessary for a linked list.
The first element node after the head node is called the first element node.
Inserting into a Singly Linked List#
Consider the following situation: a new node n needs to be inserted after node x.
The dashed line in the figure represents a disconnection, the same below.
According to the general idea, it might be:
x->next = n;
n->next = x->next;
Obviously, this is incorrect because after executing x->next = n, n->next = x->next is equivalent to n->next = n, so the correct approach should be:
n->next = x->next;
x->next = n;
Complete version of the insertion function:
The insertion function takes three parameters: the pointer head to the linked list of the node to be inserted, the data of the new node, and the position to be inserted pos.
list * list_insert_node(list *head, int data, int pos)
{
int i;
list *curr = head;
/* If the position to be inserted is greater than the length of the linked list, it is an illegal operation */
if(pos > curr->data) return NULL;
/* Create a node and initialize it */
list *node = (list *)malloc(sizeof(list));
if(node==NULL) return NULL;
node->data = data;
node->next = NULL;
/* Traverse the linked list and find the position to be inserted */
for(i=0;i<pos;i++){
curr = curr->next;
}
/* Insertion */
node->next = curr->next;
curr->next = node;
/* Increase the length of the linked list by 1 */
head->data++;
return head;
}
You can call it for testing in the main function:
list *l = create_list();
printf("Current length of the linked list: %d\n", l->data);
list_insert_node(l, 1, 0);
printf("Current length of the linked list: %d\n", l->data);
Compile and output using gcc:
gcc -fsanitize=address -fno-omit-frame-pointer -g linked_list.c && ./a.out
The output is normal and there are no memory error messages:
Current length of the linked list: 0
Current length of the linked list: 1
Traversing a Singly Linked List#
It is relatively simple, and no further explanation is needed.
/* Print the data in the linked list, excluding the data of the head node */
void print_list(list *head)
{
list *curr = head->next;
while (curr)
{
printf("%d \t", curr->data);
curr = curr->next;
}
printf("\n");
}
Deleting from a Singly Linked List#
Assuming that the node after the head needs to be deleted, simply let head->next = head->next->next, but don't forget to free the memory of the deleted node.
Based on this idea:
list *list_delete_data(list *head, int pos)
{
int i;
list *curr = head;
/* If the position to be deleted is greater than the length of the linked list, it is an illegal operation */
if(pos > curr->data) return NULL;
/* Traverse the linked list and find the pointer to the node before the node to be deleted */
for(i=0;i<pos;i++){
curr = curr->next;
}
// Temporarily record the node to be deleted
list *temp = curr->next;
// Delete the node
curr->next = curr->next->next;
// Free the memory of the deleted node
free(temp);
head->data--;
return head;
}
Testing the Singly Linked List#
In this way, a basic linked list is written, and you can test it in the main function.
int main()
{
int i;
list *l = create_list();
// Insert data multiple times
for(i=0;i<5;i++){
list_insert_node(l, i, 0);
print_list(l);
}
list_delete_data(l, 0);
print_list(l);
return 0;
}
Compile and output:
# gcc -fsanitize=address -fno-omit-frame-pointer -g linked_list.c && ./a.out
0
1 0
2 1 0
3 2 1 0
4 3 2 1 0
3 2 1 0
Complete Code#
For the complete code, please refer to the code listing.
https://github.com/austin2035/learn-data-structures