Skip to main content

C Program Code for Linked List Manipulations

Radhika has the degree of master in computer applications. She has worked as a faculty with Aptech Computer Education Center for sometime.

Singly linked list

Singly linked list

Linked lists are data structures that are user friendly. They not only save memory space, but also reduce the complexity in the manipulation of list elements such as insertion or deletion. Even if arrays can be used to store the list elements, the underestimation of maximum storage for them and their allocation in contiguous memory locations cause wastage of memory space and make the traversal of list more complicated. But this loophole is closed efficiently by the implementation of pointers in linked lists.

Singly linked lists are a collection of nodes consisting of data items and a link to next node. Suppose a list of customers have to be maintained where insertion or deletion of customers take place frequently. Using a linked list, these operations can be carried out using pointers.

Let’s analyze each step of writing the program:

1. Creation of a linked list of customers

Start by creating a data type structure containing customer code, name and a pointer to next node as structure elements. Let list be a global pointer that points to the beginning of the list accessible by all the functions. Create nodes as per the list of customers using the structure type pointer ‘ptr’ and input all customer codes and names into it.

The recursive function nodecreate(ptr) performs this task. Here, memory for the first node is allocated dynamically. Then the user has to enter the first customer code in the list. The number -999 has been chosen as a checking point to indicate the end of the list. If customer code is not equal to -999, customer name is asked and the first node would contain the values of customer code and name in the list. Then, memory for second node is allocated dynamically and the pointer is made to point to the second node using its link. Function nodecreate(ptr) is called again that performs its routines recursively. When the customer code becomes -999, the link to the next node is assigned NULL value indicating the end of the list.

Creation of linked list plays an important part for manipulating the several operations. Any small error in coding would result in the creation of an abnormal linked list. This linked list is created with customer codes of ascending order. If this order is not maintained, the several manipulations would cause run time errors.

Flowchart for the function nodecreate(node *)

Nodecreate(node *)

Nodecreate(node *)

Output

Data entry for linked list creation

Data entry for linked list creation

linked list created

linked list created

2. Inserting a new customer code into the linked list

Whenever a new customer code has to be entered, its location to insert has to be found out. This is done using the global search function searchnode(custcode)that returns the previous node of inserting node. The function insertnode(new) inserts the new customer node using the pointers ‘prev’ and ‘cur’ that point to the previous and next node of the new inserting node respectively.

Validation for duplicate customer code is required here. As the customer codes are entered in ascending order, the previous node of new inserting node will have customer code value less than that of the new node. But, the next node of the new inserting node pointed to by the pointer ‘cur’ can have customer code value equal to or greater than the new. Equality state alerts for duplicate customer code or customer code already exists.

Codes change relative to the position of the inserting node. If the previous node returned by the search function is NULL, then it is obvious that new node has to be inserted in the first position. Here ‘cur’ gets initialized to ‘list’. ‘New’ node gets linked to ‘cur’ as next and ‘list’ is made to point to ‘new’ as ‘list’ pointer always has to point to the first node of the linked list.

In other cases, pointer ‘cur’ is made to point to the next node of the previous node. Insertion is carried out by linking ‘prev’node to ‘new’ and ‘new’ node to ‘cur’. This way insertion takes place just within two steps. Arrays would require a lot more reordering while inserting a new one as elements are placed in adjacent memory locations.

Flowchart for the function insertnode(node *)

Insertnode(node *)

Insertnode(node *)

Output

Data entry for insert manipulation

Data entry for insert manipulation

Linked list after insertion

Linked list after insertion

Alert for inserting an existing customer code

Alert for inserting an existing customer code

3. Deleting a customer from the list

The manipulation of deletion also can be done fairly well with that of a linked list. Here too, the search function returns the pointer ‘prev’ that point to the previous node of the node that has to be deleted. The function nodedelete(cd) takes customer code as the argument for checking all through the linked list. Pointer ‘cur’ determines whether the given customer code can be deleted or not.

Scroll to Continue

‘cur’ is initialized depending upon the value returned by ‘prev’. If ‘prev’ is NULL, then pointer ‘cur’ should point to first node else ‘cur’ points to next node of pointer ‘prev’. Validation check for the existence of customer code is made then. If the customer code value of the ‘cur’ pointer is less than or greater than the given customer code, then a message that ‘given customer code doesn’t exist’ pop ups.

The process of deletion takes place depending upon the location of the given customer code. If the value of prev is ‘NULL”, then first node has the customer code same as the given. In this case, ‘cur’ points to ’list’. Deleting it is carried out by the following steps.

prev=cur;

cur=cur->next;

list=cur;

free(prev);

To delete first node, ‘prev’ is made to point to ‘cur’ and ‘cur’ in turn to its successor. Pointer ‘list’ now should point to ‘cur’ as first node would get deleted. Freeing the memory of ‘prev’ pointer deletes the first node. Deleting any other node in the linked list has just two lines of code;

prev->next=cur->next;

free(cur);

As ‘cur’ pointer has to be deleted, the next node of ‘prev’ is made to point to the next node of ‘cur’ to release the memory block of ‘cur’.

Allocation and de-allocation of memory block can be easily handled by using pointers rather than arrays.

Flowchart for the function nodedelete(int)

Nodedelete(int)

Nodedelete(int)

Output

Data entry for deletion

Data entry for deletion

Linked list after deletion

Linked list after deletion

Alert for entering a customer code that doesn't exist

Alert for entering a customer code that doesn't exist

4. Searching a node

Searching a node that satisfies a specific condition is performed by the global function node * nodesearch(int). Customer code is being passed as a parameter that is used for testing each node of the linked list. The search returns the previous node of the current one when the condition becomes false.

The function starts by initializing pointers ‘cur’ to ‘list’ and ‘prev’ to ‘null’. As long as the condition that given customer code is greater than that of the current node in the list is true, the statements

prev=cur;

cur=cur->next;

are made to iterate. If the next node of ‘cur’ becomes NULL or the test condition of the loop becomes false, control exits from the loop and returns the previous node.

The search function stands as a mediator while doing the manipulations ‘insertion’ or ‘deletion’ in a linked list.

Flowchart for the function node * nodesearch(int)

node * nodesearch(int cd)

node * nodesearch(int cd)

5. Displaying a linked list

The data in a linked list can be displayed by using the ‘cur’ pointer starting from ‘list’. While ‘cur’ pointer is not NULL, cur->custcode and cur->custname of each node can be displayed from within a loop. ‘cur’ is incremented to point to its next node and when it reaches the value -999, loop is exited showing the end of the linked list.


Flowchart for the function display()

display()

display()

These entire subroutines constitute the design of a linked list. Moving the data in a list is made easier when referred to their addresses. Pointers with a link can traverse a linked list to access any element and do the required manipulations cost-effectively.

C program code

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>


struct linklist

{
int custcode;
char custname[30];
struct linklist *next;
};
typedef struct linklist node;

node *list;
node * nodesearch(int);

void main()
{
int n, cd;
node *new, *temp;
void nodecreate(node *);
void insertnode(node *);
void nodedelete(int);
void display();

clrscr();
temp=(node *)malloc(sizeof(node));
list=temp;

printf("\n\t\t\tLinked list creation");
printf("\n\t\t\t====================");

printf("\n\n\t\tEnter customer codes in ascending order\n\t\t(-999 to end):\n\n");
nodecreate(temp);
display();

n=1;
while(n!=3)
{
printf("\n\n\n\n\t\tLinked list manipulations\n");
printf("\t\t-------------------------\n");

printf("\n\n\t\t1. Insertion\n");
printf("\t\t2. Deletion\n");
printf("\t\t3. Exit\n");
printf("\n\t\tEnter your choice:");
scanf("%d", &n);

switch(n)
{
case 1: new=(node *)malloc(sizeof(node));

insertnode(new);
display();

break;

case 2:printf("\n\t\tEnter the customercode to delete:");
scanf("%d", &cd);
nodedelete(cd);
display();

break;

case 3: exit(1);


}
}
getch();
}

void nodecreate(node * ptr)
{

printf("\n\t\tEnter code and press enter:");
scanf("%d", &ptr->custcode);

if((ptr->custcode)!=-999)
{
printf("\n\t\tEnter customer name:");

scanf("%s", ptr->custname);


ptr->next=(node *)malloc(sizeof(node));
nodecreate(ptr->next);
}
else

ptr->next=NULL;

}

void insertnode(node * new)
{
int cd;
char *cn;
node *prev, *cur;

printf("\n\t\tEnter the customercode to insert:");
scanf("%d", &cd);

prev=nodesearch(cd);

if(prev==NULL)
cur=list;
else
cur=prev->next;

if((cur->custcode)==cd)
{
printf("\n\n\n\t\tCustomer code already exists!!");
getch();
}

else
{
printf("\n\t\tEnter customername:");
scanf("%s", cn);
new->custcode=cd;
strcpy(new->custname,cn);

if(cur==list)
{
new->next=cur;
list=new;
}
else
{
prev->next=new;
new->next=cur;
}
}
}
void nodedelete(int cd)
{
node *prev, *cur;

prev=nodesearch(cd);

if(prev==NULL)
cur=list;
else
cur=prev->next;

if((cur->custcode)!=cd)
{
printf("\n\n\n\t\tSuch a code doesn't exist!!");
getch();
}

else if(prev==NULL)
{
list=cur->next;
free(cur);
}

else

{
prev->next=cur->next;
free(cur);
}
}

node * nodesearch(int cd)
{
node *prev, *cur;

cur=list;
prev=NULL;

while(cd>cur->custcode)
{
if(cur->next==NULL)
break;

else
{
prev=cur;
cur=cur->next;
}

}
return(prev);
}


void display()
{

node *cur;
cur=list;

clrscr();
printf("\n\t\t\tLinked list is:");
printf("\n\t\t\t============== ");
printf("\n\n\t\tCustomer code\t\tCustomer name\n");


while(cur)
{
printf("\n\n\t\t%d\t\t\t%s", cur->custcode,cur->custname);

cur=cur->next;
if((cur->custcode)==-999)
break;

}
getch();
}

Please vote!

  • C program code for queue data structure
    Elements in a queue are served in the form of First-In-First-Out manner always. A queue data structure adds data to the rear end called enqueue and removes data from the front end called dequeue. In Computer Science, a queue performs the functions of
  • About C Programming; An Overview
    Why C has gained this much popularity? It is its portability that differentiates it from other programming languages. A program written in C in one computer system can be transferred to another with minimal changes. This is why the name ‘C’ is most h
  • C program code for addition of two polynomials using...
    A polynomial is an expression of finite length constructed from variables, constants and non-negative integer exponents. C program code for polynomial addition is explained in detail here.

© 2013 Radhika Sreekanth

Comments

Radhika Sreekanth (author) from Mumbai,India on November 24, 2013:

Hi sowrav,

Do you think that this is done using arrays? Then, how come the code got simplified like this? Please read the very first introduction and then find out the answer for this question.

sowrav on November 24, 2013:

you did this with the help of array. what will be the code for linked list?

Radhika Sreekanth (author) from Mumbai,India on March 11, 2013:

Hi Ruby,

Thank you for such a pleasing comment. Hope these codes may help those who're in need.

Ruby Jean Richert from Southern Illinois on March 11, 2013:

This is way over my head but i am sure it will help someone who needs this knowledge. It prompts me to wonder what will they think of next? lol..Thank you for sharing...

Radhika Sreekanth (author) from Mumbai,India on March 10, 2013:

Hi MarieAlana1,

Thanks for reading each one of my hubs and for commenting. This program I had developed during my studies.

Marie Alana from Ohio on March 09, 2013:

Wow! I wish I had this knowledge.

Related Articles