Data structure tutorial 3: Singly Linked List

In this chapter we shall learn about below topics:

Singly Linked list is a special data structure, which is a collection of zero or more nodes. The node is a combination of data + link.

Data: It is used to store some value. It can be an Integer variable or a structure.

Link: It is used to hold the information of the next node.

Together with “Data + Link” is called as a node.

1. Singly Linked List

2. Doubly Linked List

3. Circular Singly Linked List

4. Circular Doubly Lined List.

A Singly Linked List is a collection of zero or more nodes where each node has 2 or more elements. One contains data and other contains the link to the next node.

Below is the example of SLL:

From the above image we can infer following below points:

1. The list has 5 elements.

2. In the data section it holds the value 10, 20, 30, 40, 50.

3. In the link field, it holds the address of the next node.

4. The variable “head” holds the address of the first node.

5. The “link field” of the last element has “NULL”, to suggest that it is the end of the list.

1. Insert element in front.

2. Delete element from front end.

3. Search an element.

4. Display all the data.

To insert an element in the front we follow below steps:

1. Take a temp node by allocating the memory.

2. Assign the value

3. Assign the next pointer of the temp node to the head pointer

4. Make the head pointer point to temp node making it as head pointer.

Below image shows the process

Deleting the element from the front end is simple.

1. First take a temp node.

2. Move the temp node to the next of first node.

3. Delete the first node.

4. Now make the temp node as the head, thus deleting the element from first.

Below image shows the process

To display all the node data, take a temp node, and iterate through all the elements present in the list. We take temp node because we don’t want to miss the head pointer.

Below is the code for SLL where the element is inserted at front end and deleted from front end.

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

// declare a structure for linked list

 struct node 
{
	int data;
	struct node *next;
} ;

typedef struct node* node;


// Insert the element at first
node insert_front (int value, node first_node)
{
	//take a temp node and allocate memory
	node temp_node = (node) malloc(sizeof(node));

	// assign the given value in the data section
	temp_node->data = value;

	//since we are inserting the value at first, the temp_node should point to the first_node now.
	temp_node->next = first_node;

	//since temp_node is first now, we shall return the value.
	return temp_node;
}

node delete_front(node first_node)
{
	node temp_node;

	// check if the first_node is null or not
	if(first_node == NULL)
	{
		printf("List is empty\n");
		return first_node;
	}

	// take a temp_node pointer and assign it to the first_node
	temp_node = first_node;

	// now transffer the temp_node to the next node.
	temp_node = temp_node->next;

	printf("The deleted value is %d\n", first_node->data);

	//free first_node
	free(first_node);

	//return temp_node
	return temp_node;

}


void display(node first_node)
{

	node temp_node;

	if(first_node == NULL)
	{
		printf("The list is empty\n");
		return;
	}

	printf("The contents of the list are:\n");

	// point temp_node to first_node
	temp_node = first_node;

	// display the data till temp_node is null
	while (temp_node != NULL)
	{
		printf("%d\n",temp_node->data);
		temp_node = temp_node->next;
	}

}


int main()
{
	node first_node = NULL;

	int choice = 0;
	int value = 0;

	for( ; ; )
	{
		printf("1. Insert front \n2. Delete Front \n3. Display \n4. Exit\n");
		scanf("%d", &choice);

		switch(choice)
		{
			case 1:
				printf("Enter the value to be inserted\n");
				scanf("%d", &value);
				first_node = insert_front(value, first_node);

				break;

			case 2:
				first_node = delete_front(first_node);
				break;

			case 3:
				display(first_node);
				break;

			case 4: 
				exit(0);

		}
	}

}

1. Insert front
2. Delete Front
3. Display
4. Exit
1

Enter the value to be inserted
10

1. Insert front
2. Delete Front
3. Display
4. Exit
1

Enter the value to be inserted
20

1. Insert front
2. Delete Front
3. Display
4. Exit
1

Enter the value to be inserted
30
1. Insert front
2. Delete Front
3. Display
4. Exit
3
The contents of the list are:
30
20
10

1. Insert front
2. Delete Front
3. Display
4. Exit
2
The deleted value is 30
1. Insert front
2. Delete Front
3. Display
4. Exit
3

The contents of the list are:
20
10

1. Insert front
2. Delete Front
3. Display
4. Exit
4