Site icon Study Algorithms

Basic Operations on a Linked List

nikoo28

Here are some of the basic operations on a singly Linked List.

Basic functions to perform the above techniques have been defined in the code below.

Creating a new list

A new Linked List creation means that we do not have any elements in the list and we want to start fresh. This means allocating space in the memory for a node and then inserting the data into it.

Since only a single node is created, the NEXT of this node will always be NULL.

/*
Defining a function to create a new list.
The return type of the function is struct node, because we will return the head node
The parameters will be the node, passed from the main function.
The second parameter will be the data element.
*/
struct node * createList(struct node *head,int number)
{
    // creating a temporary node for our initialization purpose
    // the below line allocates a space in memory that can hold the data in a node.
    struct node *temp = (struct node *)malloc(sizeof(struct node));

    // assigning the number to data
    temp -> data = number;

    // assigning the next of this node to NULL, as a new list is formed.
    temp -> next = NULL;

    // now since we have passed head as the parameter, we need to return it.
    head = temp;
    return head;
}
Code language: C++ (cpp)

Adding new elements

One of the operations you can perform on a linked list is to add new elements. Adding new elements to the list has a default case:- Adding elements to the end of a Linked List. We will discuss other cases to insert in between and at the beginning at a later stage.

Now to add a element, 2 cases can arise:-

Fig: Inserting a node in a linked list

Traversing a list

A Linked List traversal is very easy. The HEAD of the List always points to the first element of the Linked List. If we do a statement like

HEAD = HEAD -> next;
Code language: C++ (cpp)

We can move to the next node.

A Linked List, ends when we encounter a NULL. So basically, if we keep on performing the NEXT operation until we encounter a NULL, that means we have successfully traversed the Linked List.

/*
Defining a case when we need to element in the Linked List.
Here 2 cases can arise:-
    - The Linked List can be empty, then we need to create a new list
    - The Linked List exists, we need to add the element
*/
struct node * addElement(struct node *head, int number)
{
	if (head == NULL)
		head = createList(head, number);   // we can directly call the above function
	else
	{
		// now this is a case when we need to add an element to an existing list.

		// Creating a new node and assigning values
		struct node * temp = (struct node*)malloc(sizeof(struct node));
		temp -> data = number;
		temp -> next = NULL;

		// Now we have created the node but, we need to insert it at the right place.
		// A Linked List terminates when we encounter a NULL
		// Let us traverse the List using another temporary variable.
		// We will point it to the start
		struct node * temp2 = head;

		// The limiting condition of the while loop "until temp2's NEXT is not equal to NULL
		// This will happen only in case of the last node of the list.
		while(temp2 -> next != NULL)
		{
			// We need to go to the next node
			temp2 = temp2 -> next;
		}

		// Now temp2 points at the last node of the list.
		// We can add the node at this position now.

		temp2 -> next = temp;  // the number is added to the end of the List.
	}

	return head; // because we only need the HEAD pointer for a Linked List.
}
Code language: C++ (cpp)

Printing the list

Printing the list is same as List Traversal, the only difference is that, we need to print the elements as we move on.

/*
A function to print the Linked List.
The return type of this function will be void, as we do not need to return anything.
We just need the HEAD as the parameter, to traverse the Linked List.
*/
void printList(struct node * head)
{
	// The terminating point of a Linked List is defined when we encounter a NULL
	while(head != NULL)
	{
		printf("%d ",head -> data);

		//now we need to move to the next element
		head = head -> next;
	}
}
Code language: C++ (cpp)

A working demo of all the functions and the main function can be downloaded here.

Exit mobile version