Linked List | Array v/s Linked List | Applications | BitsOfCS

Linked list is a linear data structure like array. In array data structure, elements are stored in contiguous memory location but in linked list data structure, elements are not necessarily stored in contiguous memory location. The elements in the linked list are connected with pointers.

Array v/s Liked List: 

1.  Array is a random access data structure, that means we can randomly access an element in an array. But in the linked list, random access is not allowed. If we want to access an element in the linked list we have to sequentially traverse the linked list from the first element. 
2.  We cannot create an array dynamically, but linked lists are formed using self referential structure and in structure we can create the data dynamically. Hence there is no need to define the size of data structures like arrays, because we can create the new elements dynamically(during the runtime of the program.)
3.  There is no pointer handling in the array, But in the linked list every element takes extra memory space for pointers.

Example–

Application of Linked List:

1.  Different data structures like queue and stack can be implemented using linked lists.
2.  Linked list can be used to implement adjacency list representation of graphs.
3.  In order to implement hash table (Open chain hashing)
4.  A lot of applications provide the undo functionality that can be implemented using a linked list.

Types of Linked List:

1.  Singly Linked List
2.  Doubly Linked List
3.  Circular Linked List
4.  Circular Doubly Linked List