Linked List revisited -Part 1
In this multipart of series of blog posts, I aim to revisit one of the most dreaded data structure by computer engineering students, i.e., linked list. In this first article, I briefly introduce this data structure and go on to explain addition of a node at the beginning of a linked list.
I have been teaching the data structures for quite a few years now. Through my experience, I found that most of the students find it difficult to understand the linked list. But the linked list is not that tough, it’s just manipulation of addresses. If you understand the basic concepts of how a node is represented and how to manipulate the addresses, you can become a master in writing the code for linked list.
What is linked list?
A linked list is a set of nodes, where each node consists of two parts i.e. info and link. The info part consists of the data whereas the link part consists of the address of the next node in the linked list. There will be a designated pointer called head that consists of the address of the first node in the list.
Defining a node in ‘C’:
As mentioned above a node consists of two parts data and link. While data can be of any data type since the link part needs to store the address of the next node, we’ll need to use a pointer data type for this field. Therefore a structure can be used to implement a node consisting of heterogeneous data.
Adding a new node at the beginning:
Let’s take look at an example. Consider four nodes with their data parts consisting of 2, 3, 4, 5 respectively and let’s say they are stored in some random memory addresses shown in the figure below.
Let’s now add a node with the data 1 at the beginning. This new node has to be created first. This can be done by creating a new pointer variable say, `temp`, of the type struct node that we previously defined. We then need to allocate the memory to this new variable and assign 1 to it’s data part and simply NULL to it’s link part for now.
This new node has to be added at the beginning of the originally defined linked list. Some quick visualization of how these addresses need to be manipulated to add this as the first node makes it very simple:
i) The head pointer must consist of the address of the first node, so the address of the new node we created (i.e.6789) which we now intend to be the first node must be stored in the head pointer.
ii) This new node must link to the previous first node (i.e. 1234). Let’s go ahead and add that address to the new node’s link part.
iii)The overall linked list should now look like this:
The following code accomplishes this.
To make this interactive and test it out, let’s put all codes snippets we specified above into a full-fledged ‘C’ program that accepts user input and creates a new node to be added at the beginning of a link list.
Program to add a node at the beginning of a linked list:
Conclusion:
In summary, the link list when visualized properly is in fact very easy to implement. In the next couple of articles, I will be explaining some other operations that can be performed on a linked list. I will be happy to answer any questions you may have, just leave them as comments.
