ArtsAutosBooksBusinessEducationEntertainmentFamilyFashionFoodGamesGenderHealthHolidaysHomeHubPagesPersonal FinancePetsPoliticsReligionSportsTechnologyTravel
  • »
  • Technology»
  • Computers & Software»
  • Computer Science & Programming

C Program Code for Linked List Manipulations

Updated on August 19, 2017
radhikasree profile image

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 | Source

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 *) | Source

Output

Data entry for linked list creation
Data entry for linked list creation | Source
linked list created
linked list created | Source

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 *) | Source

Output

Data entry for insert manipulation
Data entry for insert manipulation | Source
Linked list after insertion
Linked list after insertion | Source
Alert for inserting an existing customer code
Alert for inserting an existing customer code | Source

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.

‘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) | Source

Output

Data entry for deletion
Data entry for deletion | Source
Linked list after deletion
Linked list after deletion | Source
Alert for entering a customer code that doesn't exist
Alert for entering a customer code that doesn't exist | Source

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) | Source

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() | Source

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!

Is this code easy to follow?

See results

© 2013 Radhika Sreekanth

Comments

    0 of 8192 characters used
    Post Comment

    • radhikasree profile image
      Author

      Radhika Sreekanth 4 years ago from Mumbai,India

      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.

    • profile image

      sowrav 4 years ago

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

    • radhikasree profile image
      Author

      Radhika Sreekanth 4 years ago from Mumbai,India

      Hi Ruby,

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

    • always exploring profile image

      Ruby Jean Fuller 4 years ago from Southern Illinois

      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...

    • radhikasree profile image
      Author

      Radhika Sreekanth 4 years ago from Mumbai,India

      Hi MarieAlana1,

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

    • MarieAlana1 profile image

      Marie Alana 4 years ago from Ohio

      Wow! I wish I had this knowledge.