Linked list with Operation and application

Let us start with Linked list with the type of linked list and operation performed in a linked list and application of linked list in the data structure below.

Introduction to Linked List

The linked list is a collection of elements and each element is called a node. Where each node divided into two parts. The first part contains information of the element and the second part called the link field or next pointer field, contains the address of the next node in the list.

The linear linked list(singly linked list) can be represented in memory with the following declaration.

struct Llist
{
int INFO;	//this is information part of node.
struct Node *Next;	//it is address part of node, contains the address of next node
};
typedef struct Node *NODE;

Advantage and Disadvantage of Linked List

A linked list has many advantages and some of them are:

  1. A linked list is a dynamic data structure. That is, they can grow or shrink during the execution of a program.
  2. Efficient memory utilization: In linked list (or dynamic) representation, memory is not pre-allocated. Memory is allocated whenever it is required. And it is deallocated  (or removed) when it is not needed.
  3. Insertion and deletion are easier and efficient. The linked list provides flexibility in inserting a data item at a specified position and deletion of a data item from the given position.
  4. Many complex applications can be easily carried out with a linked list.
  5. A number of nodes need not be known in advance.
  6. Traversal is possible in both the direction in case of doubly and circular doubly linked list.

A linked list has the following disadvantages or limitations

  1. More memory is needed: to store an integer number, a node with integer data and address field is allocated. In doubly link list an extra pointer is also needed to store the address of the previous node. That is more memory space is needed.
  2. Accessing, updating, deletion, insertion is cumbersome: It means accessing nodes and updating nodes requires more logics. Insertion and deletion of nodes also require extra logic.
  3. infinite loop: if proper care is not taken in a circular link list then the loop can go to-infinitive.
  4. Only sequential searching is possible.
  5. The implementation of a link is a little bit cumbersome.
  6. Can not go back in case of a single and circular linked list.

Operations on the linked list

The primitive operations performed on the linked list are as follows

  1. Creation: Creation operation is used to create a linked list. Once a linked list is created, insertion operation can be used to add more elements in a node
  2. Insertion: Insertion operation is used to insert a new node at any specified location in the linked list. A new node may be inserted.
    1. At the beginning of the linked list
    2. At the end of the linked list
    3. At any specified position in between in a linked list
  3. Deletion: Deletion operation is used to delete an item (or node) from the linked list. A node may be deleted from the
    1. Beginning of a linked list
    2. End of a linked list
    3. Specified location of the linked list
  4. Traversing: Traversing is the process of going through all the nodes from one end to another end of a linked list. In a singly linked list, we can visit from left to right, forward traversing, nodes only. But in doubly linked list forward and backward traversing is possible.
  5. Searching
  6. Concatenation: Concatenation is the process of appending the second list to the end of the first list. Consider a list A having n nodes and B with m nodes. Then the operation concatenation will place the 1st node of B in the (n+1)th node in A. After concatenation A will contain (n+m) nodes
  7. Update
  8. Sorting: is possible but requires extra logic.

Types of the linked list

Basically we can divide the linked list into the following three types in the order in which they (or node) are arranged.

  1. Singly-linked list
  2. Doubly linked list
  3. Circular linked list
  4. Circular doubly linked list

Empty List: If a list does not have any node, it is called an empty list. It means in case of a singly or circular list if the HEAD points a NULL value. In case of doubly or circular doubly link list HEAD or TAIL both points a NULL value.

Application of Link list:

  1. A stack can be implemented using the concept of a link list.
  2. A queue can be implemented using the concept of a linked list.
  3. In the dynamic memory management concept of the link, the list is used.
  4. Representation of polynomials is also possible using a link list.
  5. In a browser that allows us to hit the back button.
  6. Undo function of word processors, text editors, Photoshop, etc.

Comment you like or not our article on the Linked list with Operation and application, You can also visit our other article by click here.