## Introduction

A linked list is a linear collection of data items where each item points to a next item. Unlike an array, the items in the linked list do not need to be in a continuous memory location. They can be anywhere in the memory as long as they are connected by a link. Figure 1 shows an example of a linked list having 4 items.

Each item in a linked list is called a Node. A node has two parts: the first part is called data and it holds the actual value of the item and the second part is called next and it holds the address of the next node in the sequence. Using the next part of the node, we can get to the next item in the linked list. The first item in the list is pointed by a pointer called head. We can get to the second item by simply using the next part of the head. We can get to the third item using the next part of the second node and so on. The last item points to nowhere. In this way, if we know the pointer to the first item in the list, we can get to any item in the list in linear time.

Depending upon how one item is linked with another item in the list, a linked list can be divided into many types. Some of the types of the linked list are given below.

• Singly Linked List: This type of linked list has only one pointer that points to the next item in the list. That means we can only go in the forward direction. The list given in Figure 1 is an example of a singly linked list.
• Doubly Linked List: It has a pointer to the next node in the list as well as a pointer to the previous node in the list. That means we can go in both forward and backward direction. Figure 2 shows an example of a doubly linked list.

• Circular Linked List: In a linear linked list, the last item points to nowhere. That means we can not go further in the forward direction from the last node. In a circular linked list, however, the last node points to the first node of the list making it a circular structure. Figure 3 is an example of a circular singly linked list.