List

Introduction

A List is a set of nodes that are ordered. From the Graph perspective, it is a set of acyclic, directed nodes that have only one way to go from each node. From the Tree perspective, it is a tree with branches that only have one child node.

Everything is really a list

If you can describe a way to visit all the nodes in a graph, then you've turned the graph into a list.

By the same token, if you've decided to search a tree depth-first (or width-first), then you've also turned it into a list.

Vectors

Vectors are lists that are stored with contiguous bits of memory.

Vectors have a definite size. Expanding them requires copying the old data into a new space.

However, random access (accessing elements with no particular order) is extremely fast.

Linked Lists

Linked Lists are lists where each item knows where to find the next item, or knows that it is the last item.

Operations

• insert
• delete
• find
• next item