Single linked list 

A single linked list is a linked list in which all nodes are connected with each other in sequence. Each node of a singly linked list has two fields. The first field is used to store the data, and the second field is used to link or pointer to the next field.

Types of Linked list

Doubly linked list

The doubly linked list is also called a two-way list in which every node is divided into three fields.

  1. The first field of the linked list is called the previous pointer field, which holds the address of the previous element of the list.
  2. The second field of the linked list stores the information.
  3. The third field of the linked list is called next pointer, which points to the next element of the linked list.

Two pointer variables are used in the doubly linked list which contains the address of the first element of the list and the last element of the list. If the previous part of the first element of the linked list remains NULL, that it indicates that there is no other node behind this node. If the next part of the last element of the linked list remains NULL,it indicates that there is no node next to it. The doubly link list can be traversed in both directions.

Suppose user wants to store integer value in linked list. For this, the doubly linked list structure must be in memory, so the structure will define.

Node Structure:

Insert a node at the beginning

This algorithm is for adding a new node at the beginning:

Function:

Traversing the Doubly Linked list

  • In order Traversal: For this, the following step is followed.

Step 1: The Linked list pointer will proceed until the head is NULL.

                                while (head != NULL)

Step 2: It will print every information part of the linked list and keep moving the head.

                                 print head -> Info

                                 head = head -> next

  • Reverse Order Traversal: For this, the following step is followed.

Step 1: The Linked list pointer will proceed until the tail is NULL.

                                while (tail != NULL)

Step 2: It will print every information part of the linked list and keep moving the tail.

                                 print tail -> Info

                                 tail = tail -> next

Delete a node at the beginning

If the doubly linked list is empty, then it will return the linked list; Otherwise, we will delete the node that indicates the head pointer. For this, the following step is followed.

Function:

Delete a node at the end

To delete the last node of the linked list, you will check three conditions.

  • If the doubly linked list is empty, then it will return the linked list.
  • If there is only one node in the linked list, you will delete it, and insert NULL in the head.
  • If there is more than one item in the linked list, it will reach the last node first and then delete the last node. For this, the following step is followed.

Function:

Circular Linked List

Each node in a circular linked list is connected like a circle. There is no NULL value at the end of the circular linked list. In this, the last node stores the address of the first node, i.e., the first and last node are adjacent.

There are two types of circular linked list: 

  1. Single circular linked list
  2. Doubly circular linked list.

 

Pin It on Pinterest

Share This