What is Linked List?


Linked list is a collection of Nodes. Each node having two parts. First part represents value of the node and second part represents an address of the next node. If Next node is not present then it contains NULL value.

Linked List Node

Consider Following Presentation of Linked List:

Linked List

In above presentation FIRST is a pointer which always contains an address of first node in the linked list. If linked list is empty then value of FIRST pointer is NULL.
In Linked List nodes are logically adjacent but physically not adjacent to each other. Because address of first node is 2000, address of second node is 2010 and address of third node is 2002.
Thus in Linked List memory is not allocated sequentially to each node.
There are four types of Linked list:
(1) Singly Linked List
(2) Doubly Linked List
(3) Singly Circular Linked List
(4) Doubly Circular Linked List

     

Types of Linked List


There are four types of linked list:

(1) Singly Linked List

Singly Linked List is a collection of variable number of nodes in which each node consists of two parts. First part contains a value of the node and second part contains an address of the next node.
Following figure represents a structure of the node.

Linked List

Consider Following example in which Singly Linked List consist of three nodes. Each node having INFO part and LINK part.
INFO part contains value of the node.
LINK part contains address of the next node in the linked list. If next node is not present then LINK part contains NULL value. Thus LINK part of the last node always contains NULL value to indicate end of the list.

SIngly Linked List

In Singly Linked List we can traverse only in forward direction because LINK part contains address of the next node in the list. It is not possible to traverse in backward direction in Singly Linked List.

(2) Doubly Linked List

Doubly Linked List is a collection of variable number of nodes in which each node consists of three parts. First part contains an address of previous node, second part contains a value of the node and third part contains an address of the next node.
Following figure represents a structure of the node.

Doubly Linked List Node


Consider Following example in which Doubly Linked List consist of three nodes. Each node having LPTR part, INFO part and RPTR part.
INFO part contains value of the node.
LPTR part contains an address of the previous node in the linked list. If previous node is not present then LPTR part contains NULL value. Thus LPTR part of the first node always contains NULL value.
RPTR part contains an address of the next node in the linked list. If next node is not present then RPTR part contains NULL value. Thus RPTR part of the last node always contains NULL value to indicate end of the list.

Doubly Linked List Node

In Doubly Linked List we can traverse in both direction forward direction as well as backward direction because LPTR part contains an address of the previous node in and RPTR part contains an address of the next node the list.
However Doubly Linked List having two pointers it occupies more memory as compared to Singly Linked List.

(3) Singly Circular Linked List

Circular Singly Linked List is a collection of variable number of nodes in which each node consists of two parts. First part contains a value of the node and second part contains an address of the next node such that LINK part of the last node contains an address of the first node.
Consider Following example in which Circular Singly Linked List consist of three nodes. Each node having INFO part and LINK part.
INFO part contains value of the node.
LINK part contains address of the next node in the linked list. If next node is not present then LINK part contains an address of the first node. Thus LINK part of the last node always contains an address of the first node in the list.

Circular Linked List

In Circular Singly Linked List each node is accessible from every node in the list. But we have to take necessary care to detect end of the list otherwise processing of Circular Singly Linked List may goes into infinite loop.

(4) Doubly Circular Linked List

Circular Doubly Linked List is a collection of variable number of nodes in which each node consists of three parts. First part contains an address of previous node, second part contains a value of the node and third part contains an address of the next node such that RPTR part of the last node contains an address of the first node and LPTR part of the first node contains an address of the last node in the list.
Consider Following example in which Circular Doubly Linked List consist of three nodes. Each node having LPTR part, INFO part and RPTR part.
INFO part contains value of the node.
LPTR part contains an address of the previous node in the linked list. If previous node is not present then LPTR part contains an address of the last node. Thus LPTR part of the first node always contains an address of the last node in the list.
RPTR part contains an address of the next node in the linked list. If next node is not present then RPTR part contains an address of the first node. Thus RPTR part of the last node always contains an address of the first node in the list.

Doubly Circular Linked List

In Circular Doubly Linked List each node is accessible from every node in the list. But we have to take necessary care to detect end of the list otherwise processing of Circular Doubly Linked List may goes into infinite loop.

Download Projects


Download Programs