Site icon Study Algorithms

Important operations on a Linked List

nikoo28

We covered some of the basic operations on a Linked List in this post.

However, in order to create a functional Linked List, we need even more operations before we can proceed further. Some of these operations are:-

Inserting a node in the beginning of the List.

To insert a node in the beginning of the Linked List, we need to perform a very basic task. Create a temporary node, assign it the data value and then point the NEXT of this node to the initial HEAD of the present Linked List.

/*
Defining a function to add an element at the beginning of the Linked List
*/
struct node * addAtBeg(struct node * head, int number)
{
	//making a temporary node
	struct node * temp = (struct node*)malloc(sizeof(struct node));

	//assigning the necessary values
	temp -> data = number;
	temp -> next = head;

	//we make the new node as the head node and return
	return temp;
}

Inserting a node at a specific position

To insert a node at a specific position, we first need to create a temporary node and assign it with the values. Now we need to go to the desired position. After reaching the desired position, we need to point the next of that location to our temporary variable and the next of the temporary node to the next of the location.

/*Defining a function to add at a particular position in a Linked List*/
struct node * addAtPos(struct node *head, int number, int pos)
{
	//this is our initial position
	int initial_pos = 0;

	//This is a very important statement in all Linked List traversals
	//Always create some temporary variable to traverse the list.
	//This is done so that we do not loose the starting point of the
	//Linked List, that is the HEAD
	struct node * mover = head;

	while(initial_pos != pos)
	{
		//we need to traverse the Linked List, until
		//we reached the userdefined position
		mover = mover -> next;

		//incrementing initial position
		initial_pos++;
	}

	//Now mover points to the user defined position

	//Create a temporary node
	struct node * temp = (struct node*)malloc(sizeof(struct node));
	temp -> data = number;

	//Inserting the node.
	temp -> next = mover -> next;
	mover -> next = temp;

	return head;
}

Inserting after a specific node

To insert a node after a specific node, the entire procedure remains the same, the only difference is that we need to traverse the Linked List, until we reach the desired node. Then we apply the same process.

/*
Defining a function to insert after a specified node
*/
struct node * addAfterNode(struct node * head, int number, int after_num)
{
	//creating a temporary node to iterate
	struct node * mover = head;

	while(mover -> data != after_num)
	{
		// We need to iterate until we reach the desired node
		mover = mover -> next;
	}

	//Now mover points at the node that we want to insert

	struct node *temp = (struct node*)malloc(sizeof(struct node));
	temp -> data = number;
	temp -> next = mover -> next;
	mover -> next = temp;

	return head;
}

Deleting a node

To delete a node, we need to traverse the Linked List to the desired position, that is the node which we want to delete. To delete a node, we do not need to do any advanced operations, just point the next of the previous pointer to the next of the node to be deleted.

/*
Defining a function to delete a node in the Linked List
*/
struct node * deleteANode(struct node * head, int node_data)
{
	//In this function we will try to delete a node that
	//has the particular node data given by the user

	struct node * mover = head;

	//Creating a variable to store the previous node
	struct node * prev;

	while(mover -> data != node_data)
	{
		prev = mover;
		mover = mover -> next;
	}

	//Now mover point to the node that we need to delete
	//prev points to the node just before mover.

	//Deleting the node mover
	prev -> next = mover -> next;

	return head;
}

Deleting the entire Linked List

Simply pointing the HEAD of the Linked List, will surely result in deleting the Linked List, but the memory still remains occupied. To remove this we use the free() function at each of the node.

/*
Defining a function to delete the entire List
*/
struct node * deleteList(struct node * head)
{
	struct node * temp;

	while(head != NULL)
	{
		temp = head;
		head = head -> next;
		free(temp);
	}

	return NULL;
}

You can download the working demo here. It can be opened in any text editor like Notepad, gedit etc…

Exit mobile version