Linked List

Need of linked list -

Array are not good choice when we are not sure about the size of data required for our calculation. At runtime if the size of data structure gets varied then array is not great choice. To overcome this list is used. 

A list is a collection of elements which are linked and grow during runtime . We will use linked list in this case.

Linked List Concept explained 

Lets say we have a running competition, where athletes are allowed to run for an hour. The one who runs fastest will get a gold medal. 

Now for this situation ,

- we can't create array as we are not sure about number of participants

- If we create largest possible size , there might be worst case that no one joins

- If we create smaller array then there can be huge participation.

So in this case array doesn't serve our purpose.

Better solution is to track the no. of participants as they go and keep track . To implement this, we can create a structure for each athletes dynamically as size can grow when declared dynamically.

For each dynamically created structure , we should have separate pointer. To do this is overhead.

Better solution will be to create a structure we will call it node with speed of each player and link that with another player. 

Lets create a node name start which will have the required information and address of next node so that we can link. As the next player has not participated yet we have garbage value. To resolve this we will use the NULL pointer. No the first node is created and it waiting for availability of next node. 

If we wish to add the next node , then we will have to create the next node dynamically and then link with previous node. To do this we will assign the address of next node to previous node pointer. 

Since the pointer can only point to the data of its type , data should be of type node. 

This will look like below, first node will be the start node and the last node will be having NULL to mark end of the list.