Linked List

Linked lists can be viewed as a collection of nodes which do not necessarily occupy continuous locations in memory.

• Each node typically contains the element and a link to the next node in the list which is referred to as next.  The last node's next link refers to null.
• We store the starting node of the list to allow for easy traversal.
• A singly linked list only has one pointer to the next element in the list.
• A doubly linked list has two pointers for each node, one pointing to the next element and one pointing to the previous element in the list.

Linked List Node

Advantages of Linked Lists over arrays:

1. Easy insertion and deletion - can be achieved in constant time O(1).

2. No need to know how much memory to allocate beforehand.  The list grows dynamically.

3. No need to pre allocate memory beforehand and potentially have wasted spaces or the need to increase the size later like arrays.

Disadvantages over arrays:

1. Traversal takes linear time O(N) because access by position/index isn't possible

2. Need extra memory to store pointer to next element in the list.