Arrays and Collection Framework

Arrays and Collection Framework

1. Arrays:

Declaration:

type arrName[];
OR
type[] arrName;

Instantiation:

arrName = new type[size];

Can be combined in one statement:

type[] myArray = new type[size];

If elements are already known, declaration/instantiation can be done in the following way:

int[] nums = {1, 2, 1, 1, 3};

Accessing and Editing Elements:

String[] cities = {"Eskisehir", "Istanbul", "Izmir"};
System.out.println(cities[0]);

cities[0] = "Ankara";

2. Multidimensional Arrays:

Declaration and Instantiation:

Similar to a 1D array but adding more dimensions:

Syntax:

data_type[1st dimension][2nd dimension][]..[Nth dimension] 
array_name = new data_type[size1][size2]….[sizeN];

As an example:

int[][] intArray = new int[10][20]; //a 2D array or matrix
int[][][] intArray = new int[10][20][10]; //a 3D array

Same as 1D arrays, if the elements are known declaration can be done in the following manner: (R1C1 corresponds to row 1 column 1)

data_type[][] arrName = {
                        {valueR1C1, valueR1C2, ....}, 
                        {valueR2C1, valueR2C2, ....}
                        };

Accessing and Editing Elements:

We can use nested loops to add elements to a multi-dimensional array, as an example:

for (int i = 1; i <= 9; i++) {
       for (int j = 1; j <= 9; j++) {
            intArray[i][j] = i*j;
       }
}

3. ArrayList:

ArrayLists are dynamic, unlike arrays. This makes them easier to use when there will be lots of manipulations to the array (adding and deleting many elements)

ArrayList<Type> arrName = new ArrayList<Type>();

Accessing and Editing Elements:

Methods like add() and remove() are implemented in a similar way in most of the other collections data structures and can be used in the same way. Example usage are given below:

// Creating an Arraylist object of string type
ArrayList<String> myList = new ArrayList<>();

// Adding elements
myList.add("First");

// Adding to specific index
myList.add(1, "Second");

// Setting element at specific index
myList.set(1, "Element two");

// Removing element at specific index
myList.remove(1);

// Removing specific element
myList.remove("First");

// Get element at index
String new = myList.get(0);

4. LinkedList:

Linked list in collections framework is implemented as doubly linked list, this means that nodes contain pointers (data fields as references) to both next and previous node in the list. (Normally, linked list nodes only have references to next node as one of their data field.)

LinkedList<Type> linkedListName = new LinkedList<Type>();

Accessing and Editing Elements:

add() and remove() functions can be used in the same way as ArrayList. However, it is important to understand how a linked list works internally.

An example usage of most common functions is given below:

LinkedList<String> linkedList = new LinkedList<>();

linkedList.add("Dog");
linkedList.add("Cat");
linkedList.add("Cow");
System.out.println("LinkedList: " + linkedList);

linkedList.add(1, "Horse");

linkedList.set(2, "Van Cat");
System.out.println("Updated LinkedList: " + linkedList);

 linkedList.remove(3);
 linkedList.remove("Horse");
 System.out.println("Updated LinkedList: " + linkedList);

Output:

LinkedList: [Dog, Cat, Cow]
Updated LinkedList: [Dog, Horse, Van Cat, Cow]
Updated LinkedList: [Dog, Van Cat]

Iterating through a LinkedList and other collections can be done easily using a foreach loop:

for(String animal: animals) {
    System.out.print(animal);
}

5. Stack:

Stack class can easily be implemented using a different data structure like an array, or ArrayList.

Collections framework has a stack class that has the classical functionality of a stack data structure. It is based on last-in-first-out (LIFO) principle.

Stack<String> stack = new Stack<String>();

Stack class has functions like push(), pop() and peek(), add() or remove() can also be used however with algorithms that use stack, we use generally use push and pop.

Stack is useful to solve some classical programming problems like checking matching paranthesis or checking regular expressions.

6. Queue:

Similar to stack, a queue can be easily implemented using a different data structure like an array, or ArrayList.

Unlike stack, queue in collections is an interface, an interface is different than a class, details are explained in the classes section.

Queue structure is based on first-in-first-out (FIFO) principle, like a regular queue that we form in real life.

We can use PriorityQueue class to test out its functions, it has functions add(), and remove() that can be used similarly to LinkedList or ArrayList. It also has poll() method which returns the head of the queue (dequeue).

Queue<String> pq = new PriorityQueue<>();

7. Set (HashSet):

HashSet is different than the previous data structures.

It contains a Hash Table, and stores its elements using a mechanism called hashing, so unlike other structures, the order of the elements in HashSet is not concrete.

It only contains unique elements. Remember that a list can contain duplicate elements.

Search operations are generally faster if we use a hash table, therefore if we need to do lots of searching and will have unique elements, it can be better to use a HashSet over an ArrayList.

Usage and functions are very similar to other structures however it is important to understand how they work internally.

HashSet<String> set = new HashSet<String>();

8. Map (HashMap):

HashMap is similar to a HashTable, which generally has a table that maps keys to values.

It stores the data in pairs; Key and Value, unlike other structures.

It helps us to access the values using an index of a different type, generally an integer. Imagine you will have a list of long string values, it would be easier to assign keys to them and access those elements via those keys.

One thing to keep in mind: When inserting an element if you use a key that is already used, the element of that key will be replaced.

HashMap<String, Integer> map = new HashMap<String, Integer>();
map.put("A", 10);

Get the corresponding value of a key using get() method:

map.get(10);