# C++ Notes: Linked Lists

## Terminology - Head/Tail vs Front/Back

Traditional list terminology calls the first list element the head and the last element the tail, sometimes or the second to the end as the tail.

Most recent terminology is to call the first element the front and the element at the end the back. We'll use the front/back teminology most of the time.

## Singly-Linked Lists

## Doubly-linked Lists

## Problems with Lists as Pointers to Nodes

Several problems come up when using the combination of nodes and pointers to represent lists: ambiguity about single elements and lists, keeping both front and back for lists, and representing empty lists.

### Ambiguity - Head of list or individual node

If you have a pointer to a node, it can interpreted as either a single element, or as the pointer to the head (or tail) of a list. This apparent flexibility often turns in to a handicap, especially in the handling of singly-linked lists where it's impossible to know if there is a preceding element.

## Keeping both front and back pointers

For a doubly-linked list to be useful for operations on either the front or the back, it's necessary to represent it with two pointers, one to the front, and one to the back.

## Empty lists.

Perhaps the most difficult problem, both for singly- and doubly-linked lists is how to handle empty lists. Altho a NULL pointer can represent an empty list when reading it, it isn't adequate for passing a list from function to function that will have elements added to it.

## Changing Nodes and Pointers into Lists, Nodes and Iterators

A solution to the previous issues typically uses the following approach.

- List object. The whole list is represented by a list object that has pointers to the front and back elements.
- Node structure hidden. The actual node structure is hidden as an inner class in the list class.
- Iterators. Pointers to individual elements are represented by iterator objects with overloaded operators to give them the appearance of pointers.