Linked List Data Structure

Linked List Data Structure

Linked List Data Structure

Linked List Data Structure is a part of Learning Data Structure Series. In the last articles of Array Data Structure, we learnt Types of Array, Inserting & Deleting Elements from Array, Searching elements in Array, Sorting the Array. In this we will learn Linked List Data Structure.

Linked List

Let us start with the word List. List refers to the linear collection of elements. Such collection of elements may require data processing like storing, inserting, deleting, searching, sorting. So we can use array for this. But array has certain disadvantages like

1)     Inserting and deleting operation on array is comparatively expensive.

2)    Array usually occupies block of memory space. So increase in memory whenever required is not possible.

Another way of storing such linear data efficiently is using Linked list. Linked list is a linear collection of data elements in which link is maintained by using pointer. So we can say linked list is collection of nodes. Each node is divided into two fields.

1)     Information Field

2)    Link or Pointer Field

Information field contains the element and link field contain the address of next element in the list. So next element need not to have adjacent space in memory. This makes insert and delete operation easier and efficient than array. Also we can increase number of nodes as and when required.

Linked List

Linked List

 

Types of Linked List

There are three types of linked list

1)     Single Linked List

2)    Circular Linked List

3)    Two- Way Linked List

Single Linked List

Single linked list is a basic type of linked list. In this node is divided into two parts to hold value as well as pointer to next element. The address of first node is hold by special pointer called START. And the last node of linked list contains null address. This null address indicates that last node does not point to any other node. The linked list looks like

Simple Linked List

Simple Linked List

Circular Linked List

Circular linked list is modified version of single linked list. In single linked list, last node contains null pointer in the address field but in case of circular linked list last node hold the address of first node. So all the pointers contains valid addresses

Circular Linked List

Circular Linked List

Two-Way Linked List

In single linked list and circular linked, we can traverse in forward direction. In Two way linked list we can traverse the list in both direction forward as well as backward. The two way linked list needs two pointer to do so.

Two Way Linked List

Two Way Linked List

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *