Introduction to Linked List


A linked list is considered as a commonly used linear data structure which consists of a group of nodes that are arranged in a sequence. In a linked list every node has the address of next node which forms a chain. Consider the following figure in which a linked list is illustrated:

linked list

Here, obj is the object or data to be stored and add is the address of the next node. Together object and address makes a node. The first node is also called header or head node.


Advantages of Linked List:

The following are some of the advantages of linked list:

  1. Linked lists are dynamic in nature which means the memory is allocated when needed.
  2. Using linked list we can easily insert and delete elements.
  3. We can easily execute stack and queue when using linked list.
  4. Access time is reduced when we use linked list.


Disadvantages on linked list:

The following are some of the disadvantages of using linked lists:

  1. As we need pointers to store the address of objects, in this way a lot of extra memory is required to save those pointers.
  2. We cannot access the elements randomly in a linked list. To access an element each node is to be sequentially accessed.


Applications of linked list:

The following are the applications of linked list:

  1. Linked lists can be used to implement stack and queue easily.
  2. Elements can be inserted at the beginning or ending of the list.
  3. The size of the linked list is not needed in advance.


Types of linked lists:

The following are the types of linked list data structure:

Singly linked list:

A singly linked list is the one that has nodes. Each node has two parts one contains the object and the other part contains the address of next node and is a pointer. We can insert and delete and traverse through a single linked list. Consider the following figure of singly linked list:

singly linked list

Doubly linked list:

In a doubly linked list every node has two pointers. One pointer stores the address of the previous node and the other pointer stores the address of the next node. Consider the following figure and you will get an idea of doubly linked list:

doubly linked list

Circular linked list:

Circular linked is just like a singly linked list but the last node of the circular linked list contains the address of first node which forms a circular chain. Consider the following figure in which circular linked list is illustrated:

circular linked list