# Linked List Data Structure

A

**linked list**is a data structure that is made up of a group of*nodes*that are connected to eachter.A

*node*often contains:- Some
*data*. - A
*pointer*to the next*node*in the linked list.

The

**head**of the linked list is a pointer to the*first node*in the list.While the

**tail**of a linked list is a pointer to the*last node*Here's an example of a

*linked list*of numbers:### Implementation

In Python, the above linked list can be implemented below:

We are left with

`head`

and `tail`

to access data in the linked list.### Linked List Big O Overview

Operation | Time |
---|---|

Insert | O(n) |

Append | O(1) |

Prepend | O(1) |

Delete | O(1) |

Lookup | O(n) |

Note to get to another node, for example the

*third*node, we must iterate through each node's`next`

pointer until we reach the third one.### Linked List Pros

*Append*to the end of the list in constant time

new_node = Node(data)tail.next = new_nodetail = new_node

- Similarly,
*prepend*in constant time

new_node = Node(data)new_node.next = headhead = new_node

- A linked list doesn't need a preset size since new nodes can be added any time.

### Linked List Cons

The main con with a linked list is that accessing any other node costs

`O(n)`

time.Another con is that since nodes in the list aren't necessarily in contiguous location in memory, which makes it not cache-friendly.

## 8 Essential Linked Lists Coding Interview Problems

Master Linked Lists by trying the coding challenges below.

- 1.Insert NodeEasy
- 2.Remove NodeEasy
- 3.Find the MiddleEasy
- 4.Add Linked ListsEasy
- 5.Reverse Linked ListMedium
- 6.Detect CycleMedium
- 7.Merge Linked ListsMedium
- 8.Pivot Linked ListHard