Linked List in C

Linked lists have their own strengths and weaknesses, but they happen to be strong
where arrays are weak. Generally array’s allocates the memory for all its elements in
one block whereas linked lists use an entirely different strategy. Linked lists allocate
memory for each element separately and only when necessary

• A linked list is represented by a pointer to the first node of the linked list
  • The first node is called head
  • If the linked list is empty, then the value of head is null

• Each node in a list consists of at least two parts
  • Data
  • Pointer to the next node

• In C, we can represent a node using structures

The linked list code will depend on the following functions:

malloc()

malloc() is a system function which allocates a block of memory in the “heap” and returns a pointer to the new block. The prototype of malloc() and other heap functions are in stdlib.h. malloc() returns NULL if it cannot fulfill the request. It is defined by:

free()

free() is the opposite of malloc(), which de-allocates memory. The argument to free() is a pointer to a block of memory in the heap a pointer which was obtained by a malloc() function. The syntax is:

free (ptr);

Linked List Concepts:

A linked list is a non-sequential collection of data items. It is a dynamic data structure. For every data item in a linked list, there is an associated pointer that would give the memory location of the next data item in the linked list

The data items in the linked list are not in consecutive memory locations. They may be anywhere, but the accessing of these data items is easier as each data item contains the address of the next data item.

Advantages of linked lists:

Linked lists have many advantages. Some of the very important advantages are:

• Linked lists are dynamic data structures. i.e., they can grow or shrink during the execution of a program.
• Linked lists have efficient memory utilization. Here, memory is not preallocated. Memory is allocated whenever it is required and it is de-allocated (removed) when it is no longer needed.
• Insertion and Deletions are easier and efficient. Linked lists provide flexibility in inserting a data item at a specified position and deletion of the data item from the given position.
• Many complex applications can be easily carried out with linked lists

Disadvantages of linked lists:

• It consumes more space because every node requires a additional pointer to store address of the next node.
• Searching a particular element in list is difficult and also time consuming.

Types of Linked Lists:

Basically we can put linked lists into the following four items:

• Single Linked List.
• Double Linked List.
• Circular Linked List.
• Circular Double Linked List.

Single Linked List

A single linked list is one in which all nodes are linked together in some sequential manner. Hence, it is also called as linear linked list

Double Linked List

A double linked list is one in which all nodes are linked together by multiple links which helps in accessing both the successor node (next node) and predecessor node (previous node) from any arbitrary node within the list. Therefore each node in a double linked list has two link fields (pointers) to point to the left node (previous) and the right node (next). This helps to traverse in forward direction and backward direction

Circular Linked List

A circular linked list is one, which has no beginning and no end. A single linked list can be made a circular linked list by simply storing address of the very first node in the link field of the last node.

Circular Double Linked List

A circular double linked list is one, which has both the successor pointer and predecessor pointer in the circular manner.

Comparison between array and linked list:

Trade offs between linked lists and arrays:

Applications of linked list:

• Linked lists are used to represent and manipulate polynomial. Polynomials are expression containing terms with non zero coefficient and exponents. For example:
  • P(x) = a₀ Xⁿ + a₁ X^n-1 + ….. + a_n-1 X + an

• Represent very large numbers and operations of the large number such as addition, multiplication and division.
• Linked lists are to implement stack, queue, trees and graphs
• Implement the symbol table in compiler construction

Single Linked List:

A linked list allocates space for each element separately in its own block of memory called a “node”. The list gets an overall structure by using pointers to connect all its nodes together like the links in a chain. Each node contains two fields; a “data” field to store whatever element, and a “next” field which is a pointer used to link to the next node. Each node is allocated in the heap using malloc(), so the node memory continues to exist until it is explicitly de-allocated using free(). The front of the list is a pointer to the “start” node

The beginning of the linked list is stored in a “start” pointer which points to the first node. The first node contains a pointer to the second node. The second node contains a pointer to the third node, … and so on. The last node in the list has its next field set to NULL to mark the end of the list. Code can access any node in the list by starting at the start and following the next pointers

The start pointer is an ordinary local pointer variable, so it is drawn separately on the left top to show that it is in the stack. The list nodes are drawn on the right to show that they are allocated in the heap

Implementation of Single Linked List:

Before writing the code to build the above list, we need to create a start node, used to create and access other nodes in the linked list. The following structure definition will do

• Creating a structure with one data item and a next pointer, which will be pointing to next node of the list. This is called as self-referential structure.
• Initialise the start pointer to be NULL.

struct slinklist
{
int data;
struct slinklist* next;
};
typedef struct slinklist node;
node *start = NULL;

The basic operations in a single linked list are:

• Creation
• Insertion
• Deletion
• Traversing

Creating a node for Single Linked List:

Creating a singly linked list starts with creating a node. Sufficient memory has to be allocated for creating a node. The information is stored in the memory, allocated by using the malloc() function. The function getnode(), is used for creating a node, after allocating memory for the structure of type node, the information for the item (i.e., data) has to be read from the user, set next field to NULL and finally returns the address of the node

node* getnode()
{
node* newnode;
newnode = (node *) malloc(sizeof(node)); 
printf("\n Enter data: "); scanf("%d", 
&newnode -> data);
newnode -> next = NULL;
return newnode;
}

Creating a singly Linked List with ‘n’ numbers of nodes

• The following steps are to be followed to create ‘n’ number of nodes
  • Get the new node using getnode()
    • newnode = getnode();

• If the list is empty, assign new node as start.
  • start = newnode;

• If the list is not empty, follow the steps given below:
  • The next field of the new node is made to point the first node (i.e. start node) in the list by assigning the address of the first node.
  • The start pointer is made to point the new node by assigning the address of the new node.

• repeats the above steps ‘n’ times

The function createlist() is used to create ‘n’ number of nodes

void createlist(int n)
{
int i;
node * new node;
node *temp;
for(i = 0; i < n ; i+ +)
{
new node = getnode();
if(start = = NULL)
{
start = new node;
}
else
{
temp = start;
while(temp - > next != NULL)
temp = temp - > next;
temp - > next = new node;
}
}
}

Insertion of a Node:

One of the most primitive operations that can be done in a singly linked list is the insertion of a node. Memory is to be allocated for the new node (in a similar way that is done while creating a list) before reading the data. The new node will contain empty data field and empty next field. The data field of the new node is then stored with the information read from the user. The next field of the new node is assigned to NULL. The new node can then be inserted at three different places namely:

• Inserting a node at the beginning.
• Inserting a node at the end
• Inserting a node at intermediate position

Inserting a node at the beginning:

The following steps are to be followed to insert a new node at the beginning of the list:

• Get the new node using getnode().
  • newnode = getnode();

• If the list is empty then start = newnode
• If the list is not empty, follow the steps given below:
  • newnode -> next = start;
  • start = newnode;

The function insert_at_beg(), is used for inserting a node at the beginning

void insert_at_beg()
{
node *newnode;
newnode = getnode();
if(start == NULL)
{
start = newnode;
}
else
{
newnode -> next = start;
start = newnode;
}
}

Inserting a node at the end:

void insert_at_end()
{
node *newnode, *temp;
newnode = getnode();
if(start == NULL)
{
start = newnode;
}
else
{
temp = start;
while(temp -> next != NULL)
temp = temp -> next;
temp -> next = newnode;
}
}

Inserting a node at intermediate position:

void insert_at_mid()
{
node *newnode, *temp, *prev;
int pos, nodectr, ctr = 1;
newnode = getnode();
printf("\n Enter the position: ");
scanf("%d", &pos);
nodectr = countnode(start);
if(pos > 1 && pos < nodectr)
{
temp = prev = start;
while(ctr < pos)
{
prev = temp;
temp = temp -> next;
ctr++;
}
prev -> next = newnode;
newnode -> next = temp;
}
else
{
printf("position %d is not a middle position", pos);
}
}

Deletion of a node:

Another primitive operation that can be done in a singly linked list is the deletion of a node. Memory is to be released for the node to be deleted. A node can be deleted from the list from three different places namely

• Deleting a node at the beginning.
• Deleting a node at the end.
• Deleting a node at intermediate position.

Deleting a node at the beginning:

void delete_at_beg()
{
node *temp;
if(start == NULL)
{
printf("\n No nodes are exist..");
return ;
}
else
{
temp = start;
start = temp -> next;
free(temp);
printf("\n Node deleted ");
}
}

Deleting a node at the end:

void delete_at_last()
{
node *temp, *prev;
if(start == NULL)
{
printf("\n Empty List..");
return ;
}
else
{
temp = start;
prev = start;
while(temp -> next != NULL)
{
prev = temp;
temp = temp -> next;
}
prev -> next = NULL;
free(temp);
printf("\n Node deleted ");
}
}

Deleting a node at Intermediate position:

if(pos > 1 && pos < nodectr)
{
temp = prev = start; 
ctr = 1;
while(ctr < pos)
{
prev = temp;
temp = temp -> next; 
ctr++;
}
prev -> next = temp -> next; 
free(temp);
printf("\n node deleted..");
}

Traversal and displaying a list (Left to Right):

To display the information, you have to traverse (move) a linked list, node by node from the first node, until the end of the list is reached. Traversing a list involves the following steps

• Assign the address of start pointer to a temp pointer
• Display the information from the data field of each node

The function traverse() is used for traversing and displaying the information stored in the list from left to right.

void traverse()
{
node *temp;
temp = start;
printf("\n The contents of List (Left to Right): 
\n"); if(start == NULL )
printf("\n Empty List");
else
{
while (temp != NULL)
{
printf("%d ->", temp -> data);
temp = temp -> next;
}
}
printf("X");
}

Source Code for the Implementation of Single Linked List:

# include <stdio.h>
# include <conio.h>
# include <stdlib.h>
struct slinklist
{
int data;
struct slinklist *next;
};
typedef struct slinklist node;
node *start = NULL;
int menu()
{
int ch;
clrscr();
printf("\n 1.Create a list ");
printf("\n--------------------------");
printf("\n 2.Insert a node at beginning ");
printf("\n 3.Insert a node at end");
printf("\n 4.Insert a node at middle");
printf("\n--------------------------");
printf("\n 5.Delete a node from beginning");
printf("\n 6.Delete a node from Last");
printf("\n 7.Delete a node from Middle");
printf("\n--------------------------");
printf("\n 8.Traverse the list (Left to Right)");
printf("\n 9.Traverse the list (Right to Left)");
printf("\n--------------------------");
printf("\n 10. Count nodes ");
printf("\n 11. Exit ");
printf("\n\n Enter your choice: ");
scanf("%d",&ch);
return ch;
}
node* getnode()
{
node * newnode;
newnode = (node *) malloc(sizeof(node));
printf("\n Enter data: ");
scanf("%d", &newnode -> data);
newnode -> next = NULL;
return newnode;
}
int countnode(node *ptr)
{
int count=0;
while(ptr != NULL)
{
count++;
ptr = ptr -> next;
}
return (count);
}
void createlist(int n)
{
int i;
node *newnode;
node *temp;
for(i = 0; i < n; i++)
{
newnode = getnode();
if(start == NULL)
{
start = newnode;
}
else
{
temp = start;
while(temp -> next != NULL)
temp = temp -> next;
temp -> next = newnode;
}
}
}
void traverse()
{
node *temp;
temp = start;
printf("\n The contents of List (Left to Right): \n");
if(start == NULL)
{
printf("\n Empty List");
return;
}
else
{
while(temp != NULL)
{
printf("%d-->", temp -> data);
temp = temp -> next;
}
}
printf(" X ");
}
void rev_traverse(node *start)
{
if(start == NULL)
{
return;
}
else
{
rev_traverse(start -> next);
printf("%d -->", start -> data);
}
}
void insert_at_beg()
{
node *newnode;
newnode = getnode();
if(start == NULL)
{
start = newnode;
}
else
{
newnode -> next = start;
start = newnode;
}
}
void insert_at_end()
{
node *newnode, *temp;
newnode = getnode();
if(start == NULL)
{
start = newnode;
}
else
{
temp = start;
while(temp -> next != NULL)
temp = temp -> next;
temp -> next = newnode;
}
}
void insert_at_mid()
{
node *newnode, *temp, *prev;
int pos, nodectr, ctr = 1;
newnode = getnode();
printf("\n Enter the position: ");
scanf("%d", &pos);
nodectr = countnode(start);
if(pos > 1 && pos < nodectr)
{
temp = prev = start;
while(ctr < pos)
{
prev = temp;
temp = temp -> next;
ctr++;
}
prev -> next = newnode;
newnode -> next = temp;
}
else
printf("position %d is not a middle position", pos);
}
void delete_at_beg()
{
node *temp;
if(start == NULL)
{
printf("\n No nodes are exist..");
return ;
}
else
{
temp = start;
start = temp -> next;
free(temp);
printf("\n Node deleted ");
}
}
void delete_at_last()
{
node *temp, *prev;
if(start == NULL)
{
printf("\n Empty List..");
return ;
}
else
{
temp = start;
prev = start;
while(temp -> next != NULL)
{
prev = temp;
temp = temp -> next;
}
prev -> next = NULL;
free(temp);
printf("\n Node deleted ");
}
}
void delete_at_mid()
{
int ctr = 1, pos, nodectr;
node *temp, *prev;
if(start == NULL)
{
printf("\n Empty List..");
return ;
}
else
{
printf("\n Enter position of node to delete: ");
scanf("%d", &pos);
nodectr = countnode(start);
if(pos > nodectr)
{
printf("\nThis node doesnot exist");
}
if(pos > 1 && pos < nodectr)
{
temp = prev = start;
while(ctr < pos)
{
prev = temp;
temp = temp -> next;
ctr ++;
}
prev -> next = temp -> next;
free(temp);
printf("\n Node deleted..");
}
else
{
printf("\n Invalid position..");
getch();
}
}
}
void main(void)
{
int ch, n;
clrscr();
while(1)
{
ch = menu();
switch(ch)
{
case 1:
if(start == NULL)
{
printf("\n Number of nodes you want to create: ");
scanf("%d", &n);
createlist(n);
printf("\n List created..");
}
else
printf("\n List is already created..");
break;
case 2:
insert_at_beg();
break;
case 3:
insert_at_end();
break;
case 4:
insert_at_mid();
break;
case 5:
delete_at_beg();
break;
case 6:
delete_at_last();
break;
case 7:
delete_at_mid();
break;
case 8:
traverse();
break;
case 9:
printf("\n The contents of List (Right to Left): \n");
rev_traverse(start);
printf(" X ");
break;
case 10:
printf("\n No of nodes : %d ", countnode(start));
break;
case 11 :
exit(0);
}
getch();
}
}