Linked List Implementation in C

In previous post, we have introduced linked list data structure and discussed about various types of linked lists. We have also covered the applications of linked list data structure and its pros and cons with respect to arrays. In this post, we will discuss various Linked List implementation techniques in detail and construct a singly linked list.


 
 

1. Structure of Linked List node –

Let’s start by discussing about structure of a linked list node. Each node of a linked list contains a single data element and a pointer to the next node in the list.

 

 


 

2. Memory allocation of Linked List nodes –

The nodes which will make up the body of the list are allocated in the heap memory. We can allocate dynamic memory in C using malloc() or calloc() function. malloc() takes a single argument (the amount of memory to allocate in bytes), while calloc() needs two arguments (the number of variables to allocate in memory, and the size in bytes of a single variable). malloc() does not initialize the memory allocated, while calloc() guarantees that all bytes of the allocated memory block have been initialized to 0. To deallocate the alloted memory we can use free().

 

 
We can use new operator in C++ for dynamic memory allocation and delete operator to deallocate the alloted memory.

 

 


 

3. Constructing Linked List

This section covers various methods to construct a linked list.
 

Method 1 (Naive) –

Naive solution would be to construct individual linked list nodes first and rearrange their pointers later to build the list.

  linked list implementation

 

Run Complete Code

 


 

Method 2 (Single line) –

Above code can be re-written in a single line by passing next node as an argument to the newNode() function –

  linked list implementation single line

 

Run Complete Code

 


 

Method 3 (Generic) –

Above discussed methods would become a pain if number of nodes required is very large in the linked list. We can construct a linked list easily using iteration if the keys are given in the form of an array or any other data structure (using its iterator). Below is the implementation of the idea.

 

Run Complete Code

 


 

Method 4 (Standard) –

Standard function adds a single node to the head end of any list. This function is called Push() since we’re adding the link to the head end which makes the list look a bit like a stack. Alternately, it could be called InsertAtFront().

Consider below snippet –

 

 

Above code does not work as changes to local parameters are never reflected back in the caller’s memory. The traditional method to allow a function to change its caller’s memory is to pass a pointer to the caller’s memory instead of a copy. So in C, to change an int in the caller, pass a int* instead. In general, to change an X, we pass an X*. So in this case, the value we want to change is struct node*, so we pass a struct node** instead. i.e. the type of the head pointer is “pointer to a struct node.” and in order to change that pointer, we need to pass a pointer to it, which will be a “pointer to a pointer to a struct node”.

 

Correct Push() Code –

 

Run Complete Code

Code in C++ –
 

C++ has its built in “& argument” feature to implement reference parameters for the programmer. The short story is, append an ‘&’ to the type of a parameter, and the compiler will automatically make the parameter operate by reference for you. The type of the argument is not disturbed by this — the types continue to act as they appear in the source, which is the most convenient for the programmer.

 

Run Complete Code

There are two more approaches to solve this problem –
 

1. Make head pointer global

 

Run Complete Code

 

Above approach is not recommended as global variables are usually considered bad practice precisely because of their non-locality: a global variable can potentially be modified from anywhere (unless they reside in protected memory or are otherwise rendered read-only), and any part of the program may depend on it. A global variable therefore has an unlimited potential for creating mutual dependencies, and adding mutual dependencies increases complexity. Global variables also make it difficult to integrate modules because software written by others may use the same global names unless names are reserved by agreement, or by naming convention.

 

2. Return head from the push() function

 

Run Complete Code

 
Exercise: Modify the push() function to add nodes at the “tail” of the list.

Hint –
1. Locate the last node in the list, and then changing its .next field from nullptr to point to the new node, or
2. Maintain a tail pointer along with head pointer to perform insertion in constant time.

 
Linked List Implementation: Part 2 – Insert onto the tail of the singly linked list
 

 
References: http://cslibrary.stanford.edu/103/LinkedListBasics.pdf

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
prashanth
Guest
prashanth

Thnank you 🙂

Amit
Guest
Amit

What are the applications of a linked list?

John
Guest
John

Linked lists are useful when whenever you can’t move around the linked objects in memory. For example, basically every memory allocator is utilizing a linked list of free buffers.

Adam
Guest
Adam

If your operations include insertion/deletion but do not involve iteration/enumeration, linked lists are actually the fastest. Of course, std::list style linked lists are useless and slow. Linux kernel style (“intrusive lists”) are the ones that’re fast.

wpDiscuz