Linked List

Introduction

A linked list is a linear data structure in which elements are not stored in one contiguous block of memory. Instead, they are stored as separate nodes connected to each other using pointers.

Each node stores:

• data — the value contained in the node;
• next — a pointer to the next node in the list.

To work with a linked list, we usually keep pointers to the beginning and the end of the list. These are called head and tail.

So the list itself can be represented as:

Types of Linked List

Singly Linked List

This is the standard linked list described above. Each node stores a pointer only to the next node.

Doubly Linked List

In a doubly linked list, each node stores one more pointer: prev, which points to the previous node.

Circular Linked List

In a circular linked list, the last node points back to the first node, forming a cycle.

Operations on a Linked List

Searching for a Node

Find the $i$-th node

Indexing starts from zero.

The idea is simple:

• start from head;
• move to the next node exactly $i$ times.

Find a node by value

To find a node with a given value:

• start from head;
• move forward until the needed value is found or the list ends.

Adding a Node

Add a node to the end of the list