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.
My name is Ramesh Natarajan. I will be posting instruction guides, how-to, troubleshooting tips and tricks on Linux, database, hardware, security and web. My focus is to write articles that will either teach you or help you resolve a problem. Read more about
Comments on this entry are closed.
Very good article. Reminded my college days.:)
The good old days 🙁
Hi,
Very good article. I sent it to my students..
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.
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!
Ok but are there people who still use aloc, maloc i realoc
new and delete do it for me….
You cannot use new and delete in C program. So Malloc and free are required for dynamic memory allocation and release
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
wat would be the op if we just print ptr??
int *ptrInt = new int[100];
How would you comment this one, Yes it is possible to do it in C, with other comanda
@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++.
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 …
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
Have I ever told YA about the realloc, pay per view on that one?
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
really nice n easy to understand… 🙂
Really good, exp also very easy
linked list is very interesting part and easy to understand
explanation very good sir
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.
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
Awesome Explanation, keep up the good work.
Thank you!! very handy!!
Its a better…. ND uses exam time
I used to think that there is no boolean conditions in C ??? Is this correct or wrong?
how to understand a logic in c???
@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.
Nice ,very effective article.thx so much
good example programs
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
i am also biology student please give some tips about pagination using circular linked list.
easily understandable thanks a lot
liked it very much…….
nice well undestand sir
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]
Awesome explanation! Thank you very much!
Excellent….:)
Any one pls write the program to find exact middle node in a linked list with out going to last node????????????
Can we use link list on stack memory? Why?
@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!
Very helpful
Very helpful,
Thanks!
hey guys what i the difference between *headref=(*headref)->next and headref=&((*headref)->next)
Great code , simple complete and self explanatory, as in a tutorial like this it should be. Brilliant article, thanks.
very thanks for easy to understand….
Explain some other few examples & details for Linked List….
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();
}
i have been searching for a basic implimentation of linked list i got many but none of them compiled to give output. i am very glad i got your help.
nice work.
learnt a lot from this program.
very use full
create a program for a teacher to maintain records of his/her students.there should be a menu for asking for following options.
1.add
2.update
3.delete
4.search by id
5.search by name
6.exit
I’m a c student… n it’s a very easy way to learn a data structure without any confusion…I was looking only for this… keep it up…
thanks a lot im a second year student confused of this linked lists but this explanation made easy
Will you explain the program about adding a node in between two nodes?
Thats really helped me alot.
It solved my all confusions
Thanks a lot .I am a student of computer science . this notes is very useful for me.
So thanks again ….
Dear sir,
It’s not working properly ,So please Explain
Is der smone who can help me to write a c program using link list to display employees I’d and name in ascending order?????
Evergreen interview question. Add node in between….
void addNode_in_between(int valToSearch, int valToAdd) { struct test_struct* tempNode = NULL; struct test_struct* findNode = search_in_list(valToSearch,NULL); if(findNode == NULL) { printf("\n Node not found \n"); return NULL; } //Create tempNode tempNode = (struct test_struct*)malloc(sizeof(struct test_struct); if(tempNode == NULL) { printf("\n Node creation failed\n"); return NULL; } tempNode->val = valToAdd; tempNode->Next = findNode->Next; findNode->Next = tempNode; }Is anyone able to with an issue I am having:
When a call add_to_list – the new value I am adding seems to overwrite the existing ones in the list. So as the list grows, I just see a list of the same value.
Thanks,
vry authentic meterial
Thank you for article, it was very useful to me.
What is the role of prev in search_in_list function ?
Here is an even more complete, enhanced version, that actually shows how the “linked list” is implemented and manipulated, with a method to update data without rewriting everything:
///////////////////////////////////////////////////////////////////// #include #include #include #include struct test_struct { int val; char name[24]; char address[32]; double salary; struct test_struct * next; }; struct test_struct *head = NULL; struct test_struct *curr = NULL; struct test_struct **linked_list = NULL; struct test_struct* get_head() { return head; } struct test_struct* get_tail() { return curr; } struct test_struct* create_list_element(int val, char *address, char* name, double salary) { 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; strcpy(ptr->address, address); strcpy(ptr->name, name); ptr->salary = salary; ptr->next = NULL; head = curr = ptr; linked_list = &head; return ptr; } struct test_struct* add_to_list(int val, char *address, char* name, double salary, bool add_to_end) { if (NULL == head) { return (create_list_element(val,address,name,salary)); } 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; memset(ptr->address, 0, sizeof(ptr->address)); strcpy(ptr->address, address); strcpy(ptr->name, name); ptr->salary = salary; ptr->next = NULL; if (add_to_end) { curr->next = ptr; curr = ptr; } else { ptr->next = head; head = ptr; } linked_list = &head; 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 Key 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] [%s] [%s] [%f] \n" , ptr->val, ptr->address, ptr->name, ptr->salary); ptr = ptr->next; } printf("\n -------Printing list End------- \n"); return; } int update_element(int val, char *address=NULL , char* name=NULL, double salary=NULL) { printf(" Updating Element in List \n"); struct test_struct *cur = curr; struct test_struct *ptr = head; struct test_struct *tmp = NULL; while (ptr != NULL) { if ( ((ptr)->val) == val ) { if (address != NULL) strcpy( ((ptr)->address), address); if (name != NULL) strcpy( ((ptr)->name), name); if (salary !=double(NULL)) ((ptr)->salary) = salary; printf(" Updating ->>>> Id [%d] -- Name [%s] -- Address[%s] \n", ((ptr)->val), ((ptr)->name),((ptr)->address)); return 1; } ptr = ptr->next; } printf(" No Valid Update \n"); return 0; } int main(void) { int i = 0, ret = 0; struct test_struct *ptr = NULL; print_list(); for(i = 5; i 0; i--) add_to_list(i, (char*)"12 rue de la Roquette", (char*)"Diana Gontcharova", 666.77, false); print_list(); ptr = search_in_list(5, 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); } ret = delete_from_list(4); struct test_struct * ptr_head = get_head() ; printf("GetHead ...\n"); printf("\n [%d] [%s] [%s] [%f] \n", ptr_head->val, ptr_head->name, ptr_head->address, ptr_head->salary); struct test_struct * ptr_tail = get_tail() ; printf("GetTail ...\n"); printf("\n [%d] [%s] [%s] [%f] \n", ptr_tail->val, ptr_tail->name, ptr_tail->address, ptr_tail->salary); printf ("SizeOf %d", sizeof(linked_list)); // Do Update: update_element(7, "New Address", "New Name", NULL); print_list(); // Final Printout: ((*linked_list)->next) = head->next; while (*linked_list != NULL) { printf(" Id Double Link[%d] -- Name [%s] -- Address [%s] \n", ((*linked_list)->val), ((*linked_list)->name),((*linked_list)->address)); *linked_list = ((*linked_list)->next); } printf(" Final Print via Resequence \n"); print_list(); return 0; }this is very large program i like you to do this large code!!!!!!!!!!
very nicely explained. Good job. Thank you.
The reason I am learning this in mid 2016 itself tells us that C is still the language to master first before writing heavy high level based applications.
Sir
Article is Simply good
good one