C Linked List Data Structure Explained with an Example C Program

by Himanshu Arora on August 24, 2012

Linked list is one of the fundamental data structures in C.

Knowledge of linked lists is must for C programmers. This article explains the fundamentals of C linked list with an example C program.

Linked list is a dynamic data structure whose length can be increased or decreased at run time.

How Linked lists are different from arrays? Consider the following points :

  • An array is a static data structure. This means the length of array cannot be altered at run time. While, a linked list is a dynamic data structure.
  • In an array, all the elements are kept at consecutive memory locations while in a linked list the elements (or nodes) may be kept at any location but still connected to each other.

When to prefer linked lists over arrays? Linked lists are preferred mostly when you don’t know the volume of data to be stored. For example, In an employee management system, one cannot use arrays as they are of fixed length while any number of new employees can join. In scenarios like these, linked lists (or other dynamic data structures) are used as their capacity can be increased (or decreased) at run time (as an when required).

How linked lists are arranged in memory?

Linked list basically consists of memory blocks that are located at random memory locations. Now, one would ask how are they connected or how they can be traversed? Well, they are connected through pointers. Usually a block in a linked list is represented through a structure like this :

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

So as you can see here, this structure contains a value ‘val’ and a pointer to a structure of same type. The value ‘val’ can be any value (depending upon the data that the linked list is holding) while the pointer ‘next’ contains the address of next block of this linked list. So linked list traversal is made possible through these ‘next’ pointers that contain address of the next node. The ‘next’ pointer of the last node (or for a single node linked list) would contain a NULL.

How a node is created?

A node is created by allocating memory to a structure (as shown in above point) in the following way :

struct test_struct *ptr = (struct test_struct*)malloc(sizeof(struct test_struct));

So, as we can see above, the pointer ‘ptr’ now contains address of a newly created node. If the linked list is empty and first node is created then it is also known as head node.

Once a node is created, then it can be assigned the value (that it is created to hold) and its next pointer is assigned the address of next node. If no next node exists (or if its the last node) then as already discussed, a NULL is assigned. This can be done in following way :

...
...
ptr->val = val;
ptr->next = NULL;
...
...

How to search a node in a linked list?

Searching a node means finding the node that contains the value being searched. This is in fact a very simple task if we talk about linear search (Note that there can be many search algorithms). One just needs to start with the first node and then compare the value which is being searched with the value contained in this node. If the value does not match then through the ‘next’ pointer (which contains the address of next node) the next node is accessed and same value comparison is done there. The search goes on until last node is accessed or node is found whose value is equal to the value being searched. A code snippet for this may look like :

...
...
...
    while(ptr != NULL)
    {
        if(ptr->val == val)
        {
            found = true;
            break;
        }
        else
        {
            ptr = ptr->next;
        }
    }
...
...
...

How a node is deleted?

A node is deleted by first finding it in the linked list and then calling free() on the pointer containing its address. If the deleted node is any node other than the first and last node then the ‘next’ pointer of the node previous to the deleted node needs to be pointed to the address of the node that is just after the deleted node. Its just like if a person breaks away from a human chain then the two persons (between whom the person was) needs to join hand together to maintain the chain.

A Practical C Linked List Example

Here is a practical example that creates a linked list, adds some nodes to it, searches and deletes nodes from it.

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

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

struct test_struct *head = NULL;
struct test_struct *curr = NULL;

struct test_struct* create_list(int val)
{
    printf("\n creating list with headnode as [%d]\n",val);
    struct test_struct *ptr = (struct test_struct*)malloc(sizeof(struct test_struct));
    if(NULL == ptr)
    {
        printf("\n Node creation failed \n");
        return NULL;
    }
    ptr->val = val;
    ptr->next = NULL;

    head = curr = ptr;
    return ptr;
}

struct test_struct* add_to_list(int val, bool add_to_end)
{
    if(NULL == head)
    {
        return (create_list(val));
    }

    if(add_to_end)
        printf("\n Adding node to end of list with value [%d]\n",val);
    else
        printf("\n Adding node to beginning of list with value [%d]\n",val);

    struct test_struct *ptr = (struct test_struct*)malloc(sizeof(struct test_struct));
    if(NULL == ptr)
    {
        printf("\n Node creation failed \n");
        return NULL;
    }
    ptr->val = val;
    ptr->next = NULL;

    if(add_to_end)
    {
        curr->next = ptr;
        curr = ptr;
    }
    else
    {
        ptr->next = head;
        head = ptr;
    }
    return ptr;
}

struct test_struct* search_in_list(int val, struct test_struct **prev)
{
    struct test_struct *ptr = head;
    struct test_struct *tmp = NULL;
    bool found = false;

    printf("\n Searching the list for value [%d] \n",val);

    while(ptr != NULL)
    {
        if(ptr->val == val)
        {
            found = true;
            break;
        }
        else
        {
            tmp = ptr;
            ptr = ptr->next;
        }
    }

    if(true == found)
    {
        if(prev)
            *prev = tmp;
        return ptr;
    }
    else
    {
        return NULL;
    }
}

int delete_from_list(int val)
{
    struct test_struct *prev = NULL;
    struct test_struct *del = NULL;

    printf("\n Deleting value [%d] from list\n",val);

    del = search_in_list(val,&prev);
    if(del == NULL)
    {
        return -1;
    }
    else
    {
        if(prev != NULL)
            prev->next = del->next;

        if(del == curr)
        {
            curr = prev;
        }
        else if(del == head)
        {
            head = del->next;
        }
    }

    free(del);
    del = NULL;

    return 0;
}

void print_list(void)
{
    struct test_struct *ptr = head;

    printf("\n -------Printing list Start------- \n");
    while(ptr != NULL)
    {
        printf("\n [%d] \n",ptr->val);
        ptr = ptr->next;
    }
    printf("\n -------Printing list End------- \n");

    return;
}

int main(void)
{
    int i = 0, ret = 0;
    struct test_struct *ptr = NULL;

    print_list();

    for(i = 5; i<10; i++)
        add_to_list(i,true);

    print_list();

    for(i = 4; i>0; i--)
        add_to_list(i,false);

    print_list();

    for(i = 1; i<10; i += 4)
    {
        ptr = search_in_list(i, NULL);
        if(NULL == ptr)
        {
            printf("\n Search [val = %d] failed, no such element found\n",i);
        }
        else
        {
            printf("\n Search passed [val = %d]\n",ptr->val);
        }

        print_list();

        ret = delete_from_list(i);
        if(ret != 0)
        {
            printf("\n delete [val = %d] failed, no such element found\n",i);
        }
        else
        {
            printf("\n delete [val = %d]  passed \n",i);
        }

        print_list();
    }

    return 0;
}

In the code above :

  • The first node is always made accessible through a global ‘head’ pointer. This pointer is adjusted when first node is deleted.
  • Similarly there is a ‘curr’ pointer that contains the last node in the list. This is also adjusted when last node is deleted.
  • Whenever a node is added to linked list, it is always checked if the linked list is empty then add it as the first node.

Also, as you see from the above Linked list example, it also uses pointers. If you are new to C programming, you should understand the fundamentals of C pointers.

The output of the above code looks like :

$ ./ll

 -------Printing list Start------- 

 -------Printing list End------- 

 creating list with headnode as [5]

 Adding node to end of list with value [6]

 Adding node to end of list with value [7]

 Adding node to end of list with value [8]

 Adding node to end of list with value [9]

 -------Printing list Start------- 

 [5] 

 [6] 

 [7] 

 [8] 

 [9] 

 -------Printing list End------- 

 Adding node to beginning of list with value [4]

 Adding node to beginning of list with value [3]

 Adding node to beginning of list with value [2]

 Adding node to beginning of list with value [1]

 -------Printing list Start------- 

 [1] 

 [2] 

 [3] 

 [4] 

 [5] 

 [6] 

 [7] 

 [8] 

 [9] 

 -------Printing list End------- 

 Searching the list for value [1] 

 Search passed [val = 1]

 -------Printing list Start------- 

 [1] 

 [2] 

 [3] 

 [4] 

 [5] 

 [6] 

 [7] 

 [8] 

 [9] 

 -------Printing list End------- 

 Deleting value [1] from list

 Searching the list for value [1] 

 delete [val = 1]  passed 

 -------Printing list Start------- 

 [2] 

 [3] 

 [4] 

 [5] 

 [6] 

 [7] 

 [8] 

 [9] 

 -------Printing list End------- 

 Searching the list for value [5] 

 Search passed [val = 5]

 -------Printing list Start------- 

 [2] 

 [3] 

 [4] 

 [5] 

 [6] 

 [7] 

 [8] 

 [9] 

 -------Printing list End------- 

 Deleting value [5] from list

 Searching the list for value [5] 

 delete [val = 5]  passed 

 -------Printing list Start------- 

 [2] 

 [3] 

 [4] 

 [6] 

 [7] 

 [8] 

 [9] 

 -------Printing list End------- 

 Searching the list for value [9] 

 Search passed [val = 9]

 -------Printing list Start------- 

 [2] 

 [3] 

 [4] 

 [6] 

 [7] 

 [8] 

 [9] 

 -------Printing list End------- 

 Deleting value [9] from list

 Searching the list for value [9] 

 delete [val = 9]  passed 

 -------Printing list Start------- 

 [2] 

 [3] 

 [4] 

 [6] 

 [7] 

 [8] 

 -------Printing list End-------

As you see from the above output, it does all the fundamental Linked list operations. It creates a linked list, adds some nodes to it, searches and deletes nodes from it.


Linux Sysadmin Course Linux provides several powerful administrative tools and utilities which will help you to manage your systems effectively. If you don’t know what these tools are and how to use them, you could be spending lot of time trying to perform even the basic administrative tasks. The focus of this course is to help you understand system administration tools, which will help you to become an effective Linux system administrator.
Get the Linux Sysadmin Course Now!

If you enjoyed this article, you might also like..

  1. 50 Linux Sysadmin Tutorials
  2. 50 Most Frequently Used Linux Commands (With Examples)
  3. Top 25 Best Linux Performance Monitoring and Debugging Tools
  4. Mommy, I found it! – 15 Practical Linux Find Command Examples
  5. Linux 101 Hacks 2nd Edition eBook Linux 101 Hacks Book

Bash 101 Hacks Book Sed and Awk 101 Hacks Book Nagios Core 3 Book Vim 101 Hacks Book

{ 46 comments… read them below or add one }

1 Mitra Kaseebhotla August 24, 2012 at 10:37 am

Very good article. Reminded my college days.:)

2 TommyZee August 24, 2012 at 1:49 pm

The good old days :(

3 Jalal Hajigholamali August 24, 2012 at 8:24 pm

Hi,
Very good article. I sent it to my students..

4 Sander August 25, 2012 at 5:44 am

Yours is one of the best site to learn *nix/Dev related things!
You should review the organization tough, this way it would be easier to access the articles of a specific subject.

5 Chris August 30, 2012 at 1:26 pm

Found your site a few weeks back, this article came in handy. I am working on learning C by way of implementing things I know in Java. I just finished my third level Data Structures and Algorithm course.

Thanks for all the great articles!

6 dusKO|2scica August 31, 2012 at 11:45 am

Ok but are there people who still use aloc, maloc i realoc

new and delete do it for me….

7 C Dev November 7, 2012 at 4:22 am

You cannot use new and delete in C program. So Malloc and free are required for dynamic memory allocation and release

8 Dusko Koscica November 10, 2012 at 5:46 am

It is good for programer to learn new ways of C++, I don’t say that you should skip the list but there area better ways in C++.
First of all you can create the array with new operator, after you establish the size in memory, for example you can convert the number to binary with stack, and it is very good thing. In some ocasions you can use the vectors, the vector is faster then list and it is a question when to use list or the array.
This expanation might do you more damage than good, even it is true, because when people switch to C++ they keep their old habits, that is the problem, in this disc. Vell we can’t change people, people are what they are… and democratic way sometimes sacks at this, O no I am not saing that it is ok or only way to be comunist it is time to ocupy C++ and C

9 Amar November 14, 2012 at 8:08 am

wat would be the op if we just print ptr??

10 Dusko Kosciac November 15, 2012 at 7:39 am

int *ptrInt = new int[100];

How would you comment this one, Yes it is possible to do it in C, with other comanda

11 Anonymous November 16, 2012 at 4:31 am

@Dusko I’ve checked changes introduced by C11 last standardized C revision and didn’t see any new operator. Please stop confusing C and C++.

12 duskokoscica November 17, 2012 at 3:23 am

oK yOU MIisteR anoNymous is this enough C for YOu and others
double *niz = malloc(vel*sizeof(double));

I would like to hear Your coment on thIsone …

13 duskoKoscica November 19, 2012 at 11:19 am

Well, I see, try this code:
int *n = (int *) malloc(sizeof(int));

The problem for me is this statement:”An array is a static data structure. This means the length of array cannot be altered at run time”.

If you ask the person how manny members of array, or you are able to estimate the size of the array, this can be used…

And also, I hope that my discusion was the contribution to the toppic, it dos’t mean that the article is bad…

Some thihs have changed, and the bigger problem for me is the fact that people don’t accept the change that easy….

Ok

14 DuskoKoscica December 8, 2012 at 1:45 pm

Have I ever told YA about the realloc, pay per view on that one?

15 Pedro Rodrigues January 9, 2013 at 9:06 am

hello,
First of all, thanks for this post.
When i was trying your code i discovered that the delete function have one problem when the list have only one element that is on the same time the current and the head. When this happens, in your code, the pointer “head” will not be modified what can bring a wrong results.
Correct me if I’m wrong!

Regards
Pedro Rodrigues

16 Mittal January 10, 2013 at 3:03 am

really nice n easy to understand… :)

17 elakkiya January 23, 2013 at 11:36 pm

Really good, exp also very easy

18 rahul waghmare February 2, 2013 at 2:21 am

linked list is very interesting part and easy to understand

19 iyappan April 5, 2013 at 2:00 am

explanation very good sir

20 stefan April 8, 2013 at 11:19 am

hi , can somebody here help me solve the following exercise in c programing ?
———
#Lab2 – Double chain lists and Text editing.
Introduction: We want to stock and manipulate texts magnitude in memory.then
in will reprezantojme a text with a double chain list. Each node of the list will contain:
- A table of characters called date, with a magnitude N.
- an integer called the size that determines the number of elements to vendusur in the table.
- A pointer next to Pinto successor node.
- A pointer prev Pinto to preceding node.

Part one

1.Determine constant N avec un # define.
2.Determine node structure to maintain an element.
3.Schedule a text structure to store Text. The structure includes:
. A ponter called head to identify the first node.
. A ponter called tail to identify the last node.
. An integer count to identify the number of elements in the text.
. An integer size to identify the number of characters of text.

Part two
1. Write a iter structure to maintain a cursor in a text (relative position) which
contains:
- A ponter ptr to identify Text node where the cursor.
– an integer ICASA to identify relevant element to the table,
NULL ptr value indicates that the cursor is placed before the first element.

Part three
Basis functions: Write the following functions.
2.node * create_node () creates and returns an empty node.
3.text * create_text () creates and returns an empty text.
4.void free_text (text * t) that frees the text t and the respective nodes that make up.
5.iter * create_iter_at_begin (text * t) that creates a cursor and positioning to
The first character of the Text.
6.void free_iter (iter * pos) that frees the cursor pos.
7.void move_forward_iter (iter * pos, int n), which moves the cursor n characters
to the right.
8.void move_backward_iter (iter * pos, int n), which moves the cursor n characters
left
Cursor movement functions should ensure that the cursor stays always between element
first and last.
9.void append_text (text * t, char * s) that adds a chain s character at the end of
texti. This fonksion should shrytezoje maximum length of vacancies occurring on the last node
Text t.
10.void push_text (text * t, char * s) that adds a chain s character at the beginning of
texti.
11.void show_text (text * t, iter * pos) that displays the Text t with an asterisk [*] in position
where the cursor pos. If pos-> ptr is NULL, the star appears before the first character.
12.void insert_text (text * t, iter * pos, char * s) s after the chain adds
position pos. Besides further update to show the last character entered.
13.void delete_text (text * t, iter * pos, int n) removes n characters before pos.
In this case, but should again be set to update showing the last character that is not deleted..

Main menu of the program:
Written functions will be used to write a program that will read a text file and
further will make the relevant manipulations. Menu should be implemented:

Reading a file. Cursor is placed before the first element.
Display Text reading.
Move kursoni n characters right.
Move kursoni n characters left.
Delete n characters from the position where the cursor.
Enter a character chain starting from the cursor position.
Output from the program.

advice:

Organize project in Visual Studio where:
- File lab2.h, is the file header which decided the declarations of structures and functions.
- File lab2.c, which contains coded functions,
- File main.c source, that ^ contains the basic program.

21 MOBITI MAHENGE April 15, 2013 at 7:02 am

The article or explanations are very good, congratulation for that; my request is i need the knowledge like this with reference to C++ language…by Mobiti Mahenge

22 Hemanth April 16, 2013 at 1:09 am

Awesome Explanation, keep up the good work.

23 Ali April 16, 2013 at 7:07 pm

Thank you!! very handy!!

24 abhishek May 11, 2013 at 11:31 am

Its a better…. ND uses exam time

25 Frank May 26, 2013 at 12:02 am

I used to think that there is no boolean conditions in C ??? Is this correct or wrong?

26 saranya June 23, 2013 at 9:30 am

how to understand a logic in c???

27 LeBoepp June 27, 2013 at 4:56 am

@Pedro Rodrigues
You are right.
In function delete_from_list() you can change
if(del == curr)
{
curr = prev;
}
else if(del == head)
{
head = del->next;
}

to

if(del == curr)
{
curr = prev;
}

if(del == head)
{
head = del->next;
}

Remove the else and it works fine.

28 Rana June 28, 2013 at 2:13 am

Nice ,very effective article.thx so much

29 DHANUNJAYA REDDY July 22, 2013 at 9:05 pm

good example programs

30 pavithra July 25, 2013 at 10:39 am

i am doing my B.E.cse 2nd yr i am a biology student i dont even the basics of c &cannot understand the subject please give me sum suggestion to rectify it

31 BOOPATHI August 13, 2013 at 11:49 pm

i am also biology student please give some tips about pagination using circular linked list.

32 Anonymous October 29, 2013 at 1:46 am

easily understandable thanks a lot

33 shraddha December 3, 2013 at 8:58 pm

liked it very much…….

34 sutha merthi December 15, 2013 at 12:19 am

nice well undestand sir

35 Ishan January 6, 2014 at 3:44 am

i modified main() of this program and its not functioning the way i intended.
int main(void)
{
int i = 0, ret = 0;

print_list();

for(i = 5; i<10; i++)
add_to_list(i,true);

print_list();

for(i = 5; i<10; i++)
{

ret = delete_from_list(i);
if(ret != 0)
{
printf("\n delete [val = %d] failed, no such element found\n",i);
}
else
{
printf("\n delete [val = %d] passed \n",i);
}

}
print_list();
return 0;
}

the output i am getting wrong is that although it every value gets deleted including [9] as it shows
delete [val=9] passed
but last print_list()
it is still printing
[9]

36 Madalina January 21, 2014 at 6:48 am

Awesome explanation! Thank you very much!

37 Dimpal January 22, 2014 at 12:06 pm

Excellent….:)

38 varun February 1, 2014 at 2:44 am

Any one pls write the program to find exact middle node in a linked list with out going to last node????????????

39 Prasad Upganlawar February 24, 2014 at 1:11 am

Can we use link list on stack memory? Why?

40 k4rp March 25, 2014 at 4:44 pm

@Prasad Upganlawar

Of course you can. Its the fundamental method for implementing a stack. To understand the stack memory, imagine you have a stack of dirty dishes. Everytime a man eats the food, he put the dish on the table. Another man that finishes, places the dish right above the previous and so on(action 1). When someone is gonna get and wash the dishes, he takes the first dish from the top of the stack, washes it, then he takes again the first dish from the stack and so on until there are no more dishes to be washed. (action 2).
In programming manner, call action 1 “push” and action 2 “pop”.
The code above can be easilly adapted on a stack. add_to_list() can be modified to act like push() and delete_from_list() as a pop(). push() must always add a node to the “head” and pop() has to return always the “head” node and delete it from the list.

I hope this makes things more clear for you.

Btw i find this article great! Keep up the good work!

41 annu April 2, 2014 at 5:11 am

Very helpful

42 mirzat April 27, 2014 at 8:50 am

Very helpful,
Thanks!

43 ronaldo h May 25, 2014 at 2:37 pm

hey guys what i the difference between *headref=(*headref)->next and headref=&((*headref)->next)

44 antonio August 7, 2014 at 7:55 pm

Great code , simple complete and self explanatory, as in a tutorial like this it should be. Brilliant article, thanks.

45 Ashokkumar August 27, 2014 at 4:59 am

very thanks for easy to understand….
Explain some other few examples & details for Linked List….

46 nginging September 3, 2014 at 4:52 am

Recoded to help me.

#include
#include
#include

typedef struct intnode *linkedlist;
struct intnode
{
int data;
linkedlist next;
};
void main()
{
linkedlist temp, intlist;
int number;
//clrscr();

intlist = NULL;
printf (“Enter integer number and press enter to continue\n”);
scanf (“%d”, &number);
while (number != 0)
{
temp = (linkedlist) malloc (sizeof (intnode));
temp = data = number;
temp = next = intlist;
intlist = temp;
scanf (“%d”, &number);
}

temp = intlist;
while (temp != NULL)
{
printf (“\n%d”, temp =data);
temp = temp next;
}
getch();
}

Leave a Comment

Previous post:

Next post: