Linked List in C: Learning it the Ideal Way

Udemy Editor

While learning C, the linked list is a topic which is at one time perplexing for many beginners. Much of it also has to do with the way it is taught. Instead of actually looking at the day to day usefulness of the linked list and why they were introduced, most of the tutorials end up giving huge lengths of code which only scare the beginners. However you can be sure of one thing: if you are in school or college for programming, linked list is one of the topics which is the most likely to be covered.

Keep reading to find an easy way of understanding the linked list topic in C. We will look at how pointers are important within linked lists, how structures are created, and how dynamic data storage is created to ensure that efficient allocation of memory space is done to store data. We will also note how the linked list is different from arrays, and also go over the various advantages and disadvantages within linked lists.

For further in depth knowledge of linked lists and their working you can look at this C programming for beginners course.

Linked List 101

A linked list is a method for allocating of memory dynamically. Many students ask that if arrays can be used much more easily. Most of them are correct in this assumption. Frankly, it boils down to the task at hand. Arrays require allocation of memory in the start, whereas linked lists allocate and use memory on the go.

A small code to create a linked list:

struct test_linkedlist
{
    int val;
    struct test_linkedlist *next;
};

This would create a structure containing a value ‘val’ and a pointer which points to a similar structure.

A brief knowledge of pointers is required for linked lists. A pointer points at a location in memory. Linked list consist of node which have their own value or data they must carry and there is a pointer attached which “POINTS” to the next node. To view it in a simple format:

Here, the hexadecimal information is not important. It is just a random location within the memory at which the next node starts and to which the current pointer is pointing.

A Linked List Example

You can find good examples of how this works within the learn C the hard way course, but let’s take a look at an easy-to-understand example.

If you were to store the names of people working within a given building it would be fairly easy to guess the number of people in it. If information regarding them needs to be stored, it would be much simpler to use simple arrays. However if you were to store the information regarding various goods in your neighboring grocers shop, here the sheer variety would be huge, so a linked list might make more sense.

On top of that, back in the dinosaur days of the computer industry the electronic devices did not have huge spares of memory. In order to use each and every part of available memory resource judiciously it was important to have dynamic allocation. In this case a simple linked list, which is made of structures storing information regarding the various goods in the grocery shop, can be made.

Let us say that information required is name, price, and quantity. Now there can be 100 to 10,000 different types of goods and more importantly, new goods are always getting introduced and other goods are getting phased out. Instead of directly bringing high level code let us look at how this can be achieved efficiently in a simple diagram format.

Unlike arrays, structures within a linked list are not numbered but they are linked together using pointers which give the address of the next structure. Hence if you have the address of the first structure you can go to any part of linked list through iteration.

First gives the address of the first structure whereas NULL denotes that it is the end of the linked list. Also it is important to have a deeper knowledge of Pointers. You can read the material on C function pointers for complete knowledge.

Advantages and Disadvantages of Linked Lists in C

Linked lists are not right in every situation. Here’s a rundown of the pros and cons:

Advantages

It is dynamic memory structure that is it can expand or shrink at run time.
We can perform various operations like insert, delete, edit much more easily.
No need to pre-allocate memory and hence very efficient usage of memory.

Disadvantages

Waste of memory because of usage of pointers. They end up taking extra space unlike arrays hence if exact number of structures is known it is preferable to use arrays.
Random access is not possible. In arrays a simple a[n] call is suffice to get the value however in linked list traversing through the entire linked list becomes necessary.
Because the memory locations are not contiguous it makes higher time complexity in getting to them. In arrays the access time is O(1) whereas in linked list it is O(n).
Traversing in reverse direction is difficult in singly linked list. Even when using doubly linked list there is an extra overhead of back pointers.

We are aware of the various features of linked list by now. Let us see few of the functionalities of linked list and how they can be achieved.

Removing an Item from a Linked List

Let us say that the third item in our example above is no longer sold by the store. In that case it would need to be deleted and the used memory be freed up. We can do this by simply pointing the NEXT pointer of item 2 to the head of Item 4.

Adding an item:

If an item needs to be added it can be done by at any place within the list simply by pointing the NEXT pointer of previous item to its head and its own pointer to the next item on the list. You can add an item this way at any point in the linked list. If the shop grows over 4-5 years from a simple 100 item shop to having 10,000 items it would be very easy to go adding or removing items in real time.

If any further information regarding linked list or higher topics is required you can view it in the data structures and algorithm lesson designed for beginners.

Normal

false

EN-US

X-NONE

/* Style Definitions */

table.MsoNormalTable

{mso-style-name:”Table Normal”;

mso-tstyle-rowband-size:0;

mso-tstyle-colband-size:0;

mso-style-noshow:yes;

mso-style-priority:99;

mso-style-parent:””;