What is a linked list? Explain the different types of linked lists with a neat diagram.

A linked list, or one-way list, is a linear collection of data elements, called nodes, where the linear order is given by means of pointers. That is, each node is divided into two parts:

• The first part contains the information of the element.
• The second part, called the link field or nextpointer field, contains the address of the next node in the list.

In the above figure each node is pictured with two parts.

• The left part represents the information part of the node, which may contain an entire record of data items.
• The right part represents the nextpointer field of the node, An arrow drawn from a node to the next node in the list.
• The pointer of the last node contains a special value, called the null pointer, which is any invalid address.

Single Linked List

A singly linked list is a unidirectional linked list. So, you can only traverse it in one direction, i.e., from head node to tail node.

Doubly Linked List

A doubly linked list is a bi-directional linked list. So, you can traverse it in both directions. Unlike singly linked lists, its nodes contain one extra pointer called the previous pointer. This pointer points to the previous node.

Circular Linked

A circular Linked list is a unidirectional linked list. So, you can traverse it in only one direction. But this type of linked list has its last node pointing to the head node. So while traversing, you need to be careful and stop traversing when you revisit the head node.

Circular Doubly linked list

A circular doubly linked list is a mixture of a doubly linked list and a circular linked list. Like the doubly linked list, it has an extra pointer called the previous pointer, and similar to the circular linked list, its last node points at the head node. This type of linked list is the bi-directional list. So, you can traverse it in both directions