Difference between array and linked list
An array is a collection of elements of a similar data type.
Linked List is an ordered collection of elements of the same type in which each element is connected to the next using pointers.
Array elements can be accessed randomly using the array index.Random accessing is not possible in linked lists. The elements will have to be accessed sequentially.Data elements are stored in contiguous locations in memory.New elements can be stored anywhere and a reference is created for the new element using pointers.Insertion and Deletion operations are costlier since the memory locations are consecutive and fixed.Insertion and Deletion operations are fast and easy in a linked list.
Memory is allocated during the compile time (Static memory allocation).
Memory is allocated during the run-time (Dynamic memory allocation).
Size of the array must be specified at the time of array declaration/initialization.Size of a Linked list grows/shrinks as and when new elements are inserted/deleted.
Advantages of Linked Lists
Size of linked lists is not fixed, they can expand and shrink during run time.Insertion and Deletion Operations are fast and easier in Linked Lists.Memory allocation is done during run-time (no need to allocate any fixed memory).Data Structures like Stacks, Queues, and trees can be easily implemented using Linked list. Disadvantages of Linked Lists
Memory consumption is more in Linked Lists when compared to arrays. Because each node contains a pointer in linked list and it requires extra memory.Elements cannot be accessed at random in linked lists.Traversing from reverse is not possible in singly linked lists.
Applications of Linked Lists
Linked Lists can be used to implement Stacks, Queues and Trees.Linked Lists can be also used to implement Graphs. (Adjacency list representation of Graph).Linked Lists can be used to Implement Hash Tables - Each Bucket of the hash table can be a linked list (Open chain hashing).
