What is a linked list and why linked list?

What is a linked list?

     A linked list is a linear data structure used to organize the data in the memory. As its name indicates linked list is a list of items called the 'NODE' linked using  pointers. A 'NODE' is a structure of List containing  two or more fields called the 'data /Info' field and 'Link/address' field. A linked list can be of any of the following type. Linked list used for collecting a sequence of objects, which allows efficient addition, removal and retrieval of elements from any position in the sequence. It is implemented as nodes, each of which contains a reference (i.e., a link) to the next and/or previous node in the sequence.

Singly-Linked ListsDoubly-Linked Lists or Two way Linked ListCircularly-Linked ListsCircularly-Doubly Linked Lists

Fig: Simple Linked List.

Why Linked lists?

            Let us consider an example of implementation of a STACK or a QUEUE using a linear array then it is necessary to declare the SIZE of the STACK or QUEUE array (at Compile time) this may leads to either memory wastage or insufficient memory. This is the main disadvantage of a linear array. So if we use a linked list, we can allocate the  memory "Dynamically"   ( ie. during Run time). So there will not be any problem of memory wastage or insufficient memory.

           Whenever we want to insert or delete an element from a linear array either we must overwrite the value or we should shift the elements to new location. Where as in a linked list we can directly insert or delete the elements without effecting the other elements. So we need Linked List.