## Arrays

Arrays are the most common data structure and are very versatile

• A sequenced collection of variables of the same type (homogenous)
• Each cell in the array has an index
• Arrays are of fixed length and so have a max capacity
• Can store primitives, or references to objects
• When inserting an element into the array, all to the right must be shifted up by one
• The same applies in reverse for removal to prevent null/0 gaps being left

## Sorting Arrays

• The sorting problem:
• Consider an array of unordered elements
• We want to put them in a defined order
• For example [3, 6, 2, 7, 8, 10, 22, 9] needs to become [2, 3, 6, 7, 8, 9, 10, 22]
• One possible solution: insertion sort:
• Go over the entire array, inserting each element at it's proper location by shifting elements along
public static void insertionSort(int[] data){
int n = data.length;
for(int k = 1; k < n; k++){             //start with second element
int cur = data[k];                  //insert data[k]
int j = k;                          //get correct index j for cur
while(j < 0 && data[j-1] > cur){    //data[j-1] must go after cur
data[j] = data[j-1];            // slide data[j-1] to the right
j--;                            //consider previous j for cur
}
data[j] = cur; //cur is in the right place
}
}

• Insertion sort sucks
• Has worst case quadratic complexity, as k comparisons are required for k iterations.
• When the list is in reverse order (worst case), comparisons are made
• Can do much better with alternative algorithms

• Linked lists is a concrete data structure consisting of a chain of nodes which point to each other
• Each node stores the element, and the location of the next node
• The data structure stores the head element and traverses the list by following the chain
• Operations on the head of the list (ie, prepending) are efficient, as the head node can be accessed via its pointer
• Operations on the tail require first traversing the entire list, so are slow
• Useful when data needs to always be accessed sequentially
• Generally, linked lists suck for literally every other reason