Data Structures - Linked List | Insertion in the beginning

Why do we use Linked List instead of Arrays ? 

Arrays have the following limitations :

• Size of the array is fixed. We have to define the upper limit of the elements.
• The memory allocation of the array is done according to the maximum size of the array irrespective of the usage of the memory.
• Insertion of the new element is difficult because we have to create new room for the element and the already present elements must be shifted.

What is a Linked List?

A linked list is a linear data structure, in which the elements are not stored  at contiguous memory locations.

The elements in the linked list are linked using pointers as shown in the below image:

Let's take a closer look.

1. Linked Lists basically consists of Nodes which are connected to each other and are stored in non-contiguous memory.
2. If we look at a single node we would find that it contains two blocks. The first block contains the data and the second block contains a pointer to the next node (or it is a pointer that keeps the address of the next node).
3. In the case of the last node, since there is no other element after that, the pointer is assigned NULL.
4. A linked list is represented by a pointer (which is of type Node)  to the first node. This pointer is known as head. Initially its has NULL value.

The Code:

1. For creating a node we use structures. It will have a variable of int type which will be our data and another variable which is a pointer of type Node (same as the name of the structure).
2. We will create two functions Insert() and print(). 
3. The Insert() function will be created a node and then insert it in our linked list. We are going to use dynamic memory allocation for creating the nodes
4. The print() function will traverse all the elements in the linked list
5. For inserting in the beginning, we create a temporary node. The 'next' pointer in the node is assigned the value in head i.e. the address of the first node. Then the head pointer in assigned the address of the temporary node. Thus breaking the link between the head pointer and the first node.