7 - Implementing Lists, Stacks and Queues

7.1 - Common features for a list

Storing data in a sequential order.
Can perform the following operations:
- Retrieve element from a list.
- Insert a new element into a list.
- Delete an element from a list.
- Find out how many elements are in the list.
- Determine whether an element is in the list.
- Check whether the list is empty.
An abstract class provides a skeletal implementation of the interface, which minimizes the effort required to implement the interface.

Array is a fixed-size data structure.
- Changing the size of the array by creating a bigger array, and moving the existing array in it.
  - Check the size before adding items.
- If a new element is inserted before an existing one, the whole array needs to be shifted.

A linked list contains of a set of Node object which are linked to eachother.
Head = The first element in the link.
Tail = The last element in the link.
Each element knows the next element.
The next field only needs to be upated when the next item is replaced.
Circular Linked List = When the last element directs the "next" to the first item in the list.
Doubly Linked List = Each item has a "next" and "previous"
Circular Doubly Linked List = Each item has a next and a previous, but the "previous" of the first item in the list directs to the last item in the list. And the "next" of the last item in the list directs to the first item in the list.

Stacks can be implemented using arrayLists.
- A stack only makes changes to the end of the array (top of the stack), so arrayList is most effecient.
Queues can be implemented using linkedLists.
- Adding new items to the tail, access and delete items from the head.