Linked List

Introduction

We have discussed about array in the previous article .The main drawback of array is that one size is declared , it can't be changed during the execution of program.It is static data structure .

There is need of data structure in which we can add as many elements as we want and should be able to allocate the memory at run time(dynamic allocation). 
Introduction to linked list
Analogy of Linked list

So there is a new concept called Linked List .

In this article we are going to make ourself familiar with linked list and in next articles we are going to actually implement linked list using C++.

What is Linked List ?

Linked list  consist of dynamically allocated blocks of memory called ' node '. Linked list is a set of such nodes. 
Linked list data strucutre
dia 1.0
A  node has two parts , a data and an address part. Data part stores the data element while address part stores the memory address of next node.
The extended view of a node can be represented by following diagram ,
Linked list node
dia 1.1
Linked list uses pointer for its implementation.
The whole linked list is retrieved with the help of a pointer called 'head' . It always points to the starting node of list (as shown in dia 1.0).

Nodes are created in memory at random locations. They are connected via a link in between two nodes. A node has the memory address of immediate next node by which we get next node and so on.

 Linked list can grow as much as we want if  sufficient memory is available. 
The node whose address part is null is the end of linked list.




Types of linked list

There are three types of linked list :
  1. Singly Linked List  (SLL)
  2. Doubly Linked List  (DLL)
  3. Circular Linked List  (CLL)

 Advantages of linked list

  1. No need to know the size of list in advance.
  2. Insertion and deletion of data element is very possible and easy.
  3. Memory is  efficiently utilised.

Disadvantaged of linked list

  1. They require more memory than array . In addition to the data part they  store address of next node also which require extra space.
  2. Nodes are stored randomly in memory ,so the time required to access them is more.
  3. As linked list is linear data structure , elements are processed sequentially only.