Linked Lists: Create a Linked List in C

4 Minute Read

Report Issue Improve Article

It is fundamental for a C programmer to have a good grasp of linked lists. Linked lists allow us to dynamically store various types of information. In order to use and understand the linked list, you should already be familiar with pointers and dynamic memory allocation. Fear not, if these two topics are new to you, because we will cover them to the necessary detail for you to truly comprehend the creation of linked lists.

This tutorial is divided into the following four parts:

1. The necessary prerequisites to understanding linked lists

Linked lists or node lists are much more comprehensible for people, who have encountered and understood such topics as pointers and dynamic memory allocation.

A pointer in C programming language contains an address of another variable. A pointer can also access the value contained in the address it points to. If this sounds a bit obscure, take a look at the illustration below.

Example 1: illustration of a pointer.

An example of a pointer in C

Just to iterate once more, pointers have their own addresses and contain addresses with other variables. Values of these variables, in turn, can be accessed by pointers.

Now, to have a memory address reserved for a pointer in the first place, memory allocation is required. In C programming language, there are two types of memory allocations, that are static and dynamic. Static memory allocation occurs on the stack and it is performed during the compilation of the program. Dynamic memory allocation, on the other hand, happens on the heap during the runtime of the program. To use dynamic memory in C, a programmer can use the malloc function.

Note: improper handling of dynamic memory allocation leads to memory leaks.

2. The creation of a linked list on the stack in C

A linked list in C programming language defines struct nodes linked by pointers. Now you may wonder, what such a struct node looks like in C.

Example 2: struct node in C.

typedef struct node {
int val;
struct node *next;
} node;

As you can see in the example above (example 2), this node contains an integer value (val) and a pointer to a struct node (next). The variable next can, in turn, be pointed to another struct node, whereas another struct node can be pointed to yet another one, and so on. This type of data structure of linked nodes is, in fact, a linked list.

Now that all this is clear, we can look at the example below that demonstrates the creation of a linked list on the stack.

Example 3: Creation and printing of a linked list on the stack

# include <stdio.h>
typedef struct node {
int val;
struct node *next;
} node;
void print_int_linked_list (node *list)
{
node *current = list;
printf ( "Linked list contains: " );
while (current != NULL )
{
printf ( "%d " , current->val);
current = current->next;
}
}
int main ()
{
node first;
node second;
first.next = &second;
first.val = 1;
second.next = NULL ;
second.val = 2;
print_int_linked_list (&first);
return 0; 
}
					

				

			

			

				Possible output:
			

			

				Linked list contains: 1 2

			

			

				Notice the next value of the second node is set to NULL (line 25). This is significant, because a node being
				set to NULL indicates the last node. Many functions, just like
				print_int_linked_list, stop iterating after finding the NULL value (line 12).
			

		

		

			
3. The creation of a linked list on the
				heap in C
			

			

				We have already learned in the first part of this tutorial that heap memory can be allocated with the function malloc. Take a look below,
				to see how the malloc function can be used to create a dynamic
				linked list.
			

			

				Example 4: Creation and printing of a linked list on the stack
			

			

				
				
				

					

						#
						include 
						<stdio.h>
					

					

						#
						include 
						<stdlib.h>
					

					

						
 

					

					

						typedef struct 
						node {
					

					

						
    
int
						val;
					

					

						
    
struct node *next;
					

					

						} node;
					

					

						
 

					

					

						node* 
						create_new_node
						(
						int
						 content)
					

					

						{
					

					

						
    
node* tmp = 
						
						(node*)
						malloc
						(
						sizeof
						(*tmp));
					

					

						
    
if
						(tmp == NULL)
						NULL
						)
					

					

						
    
{
					

					

						
        
return
						(
						NULL
						);
					

					

						
    
}
					

					

						
    
tmp->val = content;
					

					

						
    
tmp->next = 
						NULL
						;
					

					

						
    
return
						(tmp);
					

					

						
}
					

					

						int
						main
						()
					

					

						{
					

					

						
    
node* first = 
						create_new_node
						(1);
					

					

						
    
node* second = 
						create_new_node
						(2);
					

					

						
    
first->next =
							second;
					

					

						
    
//remember to free the dynamic linked list before exiting the program
					

					

						
    
return
						0;
					

					

						
}
					

				

			

			

				Following all the given examples above, you can successfully create linked lists on the stack and on the heap. You are likely more comfortable now with important C programming concepts, such as pointers and dynamic memory allocation, too. Hopefully, all this will enable you to build your own linked list with a better understanding.
			

			
		

		
4. Quiz of reader's knowledge

		

			
Quiz : Create Linked Lists in  C

			

				
1What is a linked list?

				
				
				
			

			

				
2What
						data type is used as a node in C?

				
				
				
			

			

				
3Is the keyword typedef necessary to create a node of a linked list?

				
				
			

			
		

		
		

			
			
quiz completed!

			
Congrats!

			

				
					
						
						Article's certificate
					
				
			

			
Feel free to share your achievement below!