A linked list is a linear data structure, in which the elements are **not** stored at contiguous memory locations.

The elements in a linked list are linked using pointers as shown in the below image:

Credit to *GeeksforGeeks*

## Types of linked list

### Singly Linked List

The linked list we talked above is singly linked list.

### Doubly linked list

A **D**oubly **L**inked **L**ist (DLL) contains an extra pointer, typically called *previous pointer*, together with next pointer and data which are there in singly linked list.

Credit to *GeeksforGeeks*

### Circular linked list

**Circular linked list** is a linked list where all nodes are connected to form a circle. There is no NULL at the end. A circular linked list can be a singly circular linked list or doubly circular linked list.

Credit to *GeeksforGeeks*

## Linked list applications

### Delete a node

Credit to *programmercarl*

If we need to delete `node d`

, what we need to do is to delete the pointer that points to `node d`

### Add a node

Credit to *programmercarl*

Add and delete both have time complexity O(1).

**Note**: If we need to delete the last node, we need to start from `head`

node to the fourth node, time complexity is O(n).

### Compare with list

Add/Delete(Time Complexity) | Search(Time Complexity) | When to use | |
---|---|---|---|

List | O(n) | O(1) | Fixed number of data, frequently search, rarely add/delete |

Linked List | O(1) | O(n) | Number of data various, frequently add/delete, rarely search |