A linked list is a collection of nodes or elements that we can traverse within the list. A node or an element is a basic structure to create a list. A node contains a data part and the address to the next node, in order to form a list.
Lets’ go through the steps needed to create a singly linked list in C.
Create a node or an element to form a list
The first thing we need to do is, create a node or an element to form a list. Each node contains data & a pointer to the next node to form a singly linked list. The node looks like the below;
Node
{
Data part
A link to next Node
}Note that, we just defined a node with a single link to point to the next node. For a singly linked list, the node contains a single link only.
The first node of the list, we call a Root node or Head node. A list contains 1 or mode nodes. A list without any nodes is an empty list.
We can use structures in C to define a node.
Add a node or an element to the list
Adding a node to the list is nothing but creating a new node and attaching it to the list. We can add a node in any position in the list.
Usually, nodes can be added to the list from the Root node or append to the list. When we append the new node to the list, it is the last node in the list; whereas when we add the new node from the root node, it will be the first node after the root node. But in the code we walkthrough through this article, we will be adding a node at end of the list (appending to the list).
AddNode
{
Traverse to the end of the list
Create a new node and attach it to the end of the list
}It will be easy if we save the location of the last node, to add a new node to the list. In C, we can use malloc() function to allocate memory to the node.
Display the list’s data
In order to display the data from the list, traverse within the list, fetch each node or an element and display the data of each node. Start from the root node to traverse within the list. As this is a singly linked list, we must have to store the location of the root node and traverse within the list to reach the end of the list. If we lose the location of the root node, we can not traverse back as in a singly linked list we can traverse only in the forward direction.
Display
{
Print data of each node
Move to next node
}Remove a node or an element from the list
We can remove the nodes from any place in the list. For this article’s example code, let’s stick to removing the node from the end of the list.
Removing the node means detaching it from the list, and deallocating its’ allocated memory. To remove the last node, traverse within the list from the root node and detach it from the list. Ensure to deallocate memory for the last node if allocated. The previous node to the last node will become the last node.
By using free() function in C, we can deallocate the memory which is already allocated using malloc() function.
RemoveNode
{
Traverse to end of the list
Remove the last node
Set last node's previous node as last node
}
Observe that in our example, the root node will still remain and this can be deleted only when deleting the list.
Delete the list
Delete list means deleting all its’ nodes or elements within the list. Traverse within the list and delete all its nodes. It will be easy to delete the list from its’ root node; instead of deleting the list from the last node.
DeleteList
{
While root node is not empty
{
Save the location of root node's next node
Remove the root node
Set first node as the root node
}
}
Get the length of the list
To get the length of the list we can traverse the list from the root node to the last node. An empty list does not have any nodes.
Simply Linked List – working example in C
Lets’ put together the code and here is the complete working example.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node
{
char data[255];
struct node *pnext;
}*proot = 0, *pcurrent = 0;
int create_list()
{
if ( proot != 0 )
return -1;
proot = (struct node *) malloc(sizeof(struct node));
if ( proot == 0 )
return -1;
proot->data[0] = '\0';
proot->pnext = 0;
pcurrent = 0;
return 0;
}
void delete_list()
{
struct node *pnode = 0;
while(proot != 0)
{
pnode = proot->pnext;
free(proot);
proot = pnode;
}
}
int list_add(char *pdata)
{
if ( pdata == 0 )
return -1;
if ( pcurrent == 0 )
{
if ( strcpy(proot->data, pdata) == 0 )
return -1;
pcurrent = proot;
}
else
{
pcurrent->pnext = (struct node *) malloc(sizeof(struct node));
if ( pcurrent->pnext == 0 )
return -1;
pcurrent->pnext->data[0] = '\0';
pcurrent->pnext->pnext = 0;
if ( strcpy(pcurrent->pnext->data, pdata) == 0 )
{
free(pcurrent->pnext);
pcurrent->pnext = 0;
return -1;
}
pcurrent = pcurrent->pnext;
}
return 0;
}
void list_remove()
{
if ( proot == 0 )
return;
struct node *pnode = proot;
while(pnode->pnext != 0)
{
if ( pnode->pnext->pnext == 0 )
{
free(pnode->pnext);
pnode->pnext = 0;
break;
}
pnode = pnode->pnext;
}
}
void list_display()
{
struct node *pnode = proot;
printf("[");
while (pnode != 0)
{
printf("%s", pnode->data);
pnode = pnode->pnext;
if (pnode != 0)
printf(", ");
}
printf("]");
}
int list_length()
{
int count = 0;
struct node *pnode = proot;
while (pnode != 0)
{
count++;
pnode = pnode->pnext;
}
return count;
}
int main()
{
if ( create_list() == 0 )
{
list_add("Amsterdam");
list_add("Barcelona");
list_add("Chicago");
list_add("Dubai");
list_add("Hong Kong");
list_display();
printf("\nnodes count: %d\n", list_length());
list_remove();
list_remove();
list_display();
printf("\nnodes count: %d\n", list_length());
delete_list();
}
return 0;
}
// Malin