## Introduction

Linked list is a linear data structure like arrays. But arrays are stored at contiguous location in the memory where linked list use pointer to point to the next element.

## Why Linked List?

Array is the most popular linear data structure but it has some limitations as follows:

1. Array size is fixed. So, we must have to know the limit of the array in advance.

2. Inserting an element in an array is expensive which is O(n).

3. Deleting is also expensive in array which is O(n).

Nevertheless, array is most popular data structure for having the ability of random access and binary search.

But Linked list over comes these disadvantages like as follows:

1. Dynamic memory allocation.

2. Insertion and deletion takes constant time O(1).

Linked list has some drawbacks like random access is not allowed. And we have to access elements sequentially. So, binary search will not fit.

Linked list data structure:

**C/C++:**

struct node
{
int data;
struct node *next;
};

**Java:**

public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}

**C#:**

public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}