Linked Lists: Definition

A linked list is a linear data structure made of nodes, where each node contains data and a pointer to the next node.

In a singly linked list, the pointers include:

• A head pointer that points to the first node.

• $n$ next pointers, one in each of the $n$ nodes, where the last pointer points to NULL.

• A tail pointer that points to the last node.

Therefore, a singly linked list contains (at most) a total of $n + 2$ pointers.

Unlike arrays, linked lists do not store elements in contiguous blocks of memory.