Linked List v/s Arrays

Linked list is a replacement to the arrays. Since arrays take in a block of memory so the flexibility is very less.It has a defined structure which uses a limited memory and uses only when the memory is required. Though adding more elements is a cumbersome task.

Each node in a list consists of at least two parts:

1. Data
2. Pointer to the next node

struct Node{ int data; Node* next; }

A tabular comparison of Arrays v/s Linked List:

S. No	Parameter		Arrays	Linked list
1	Cost		Constant time O(1)	O(n)
2	Memory usage		Fixed Size Contiguous Blocks of memory	No unused memory, Extra memory for pointer variables
3	Cost of inserting and Deleting elements	At the beginning	O(n) Shifting one index at a time to the right	Creating a new node and head pointer O(1)
		At the end	If Array not full O(1) else O(n)	Traversing a new node & End
		At the nth position	O(n)	O(n)
4	Ease of Use		Very Easy	Complicated especially in C/C++

Advantages over arrays

1. Dynamic size
2. Ease of insertion/deletion

Drawbacks:

1. Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do binary search with linked lists.
2. Extra memory space for a pointer is required with each element of the list.