Linear List
Stack >A linear list is a data structure that holds a sequential list of elements.
11, 35, 1, 12, 9
In the above example, element 11 is at position 1, element 35 is at position 2, and so on. (Note that in many programming languages position 1 has index 0, position 2 has index 1, etc.)
Implementations
Array
Being one of the first data structures new programmers learn to work with, it is the most widely known implementation of a linear list. An array is stored in one contiguous block of memory.
In most programming languages, arrays have a fixed size once declared. This means that you can change item values but you can't add or delete new items. Arrays allow for quick random access, meaning that you can get the element at any given position in efficiently (in constant time).
Vector
A vector behaves much like an array, but unlike regular arrays its size can change dynamically. Keep in mind however that when you enlarge a vector, your operating system might have to look for a contiguous block of free memory that can store the enlarged vector.
Vectors are often stored in contiguous memory (e.g. the std::vector type in C++ -- source), but that's not always the case.
Linked list
A linked list holds a chain of elements. Each element knows the location of its successor (if any). This property is used to walk through the list from left to right. The first element is usually called the head, which makes the last element the tail.
Adding and removing elements in a linked list is less costly than in vectors (if the position of the element is known), because the structure of a linked list doesn't require that it is stored in contiguous memory.
On the downside, you can't get random access to any element without first passing through the other elements. If you need to access the element at position 800, you'll need to go to the list tail, ask element 0 where element 1 is, ask element 1 where element 2 is, and so on.
So which implementation is the best?
Each linear list implementation has its own pros and cons. To know which one is the most efficient in your case, just have a look at this nice little flowchart...
Stack >