Data-Structure Topics:

• Arrays and ArrayLists
• LinkedLists
• Stacks and Queues
• Sets
• Maps
• Tree Data Structure

Arrays and ArrayLists:

Most Basic types of array declaration:

data-type varName[size];

OR

data-type[size] varName;

Initializing an array

int[] arr = new int[size];

OR

int[] arr = {0,1,2,3,4,5,6,7,8,9};

Most common methods to find the size or length of an array

arr.length -> for calculating the length of all types of array (int[], String[], char[])

arr.size() -> for calculating the size of an object array(Ex. List array as it stores only objects)

Point to remember

.length -> It is used for calculating the length of all types of array (int[], String[], char[])

.length() -> It is used for calculating the length of a String

Array and List declarations:

/*---- General ways of creating int and String arrays ----*/


int[] intArray1 = new int[10];                /*-- Array size should be provided --*/                             

int[] intArray2 = {0,1,2,3,4,5,6,7,8,9};      /*-- Also a valid declaration --*/

int intArray3[] = new int[10];                /*-- Another valid declaration --*/

int intArray4[] = {0,1,2,3,4,5,6,7,8,9};      /*-- Another valid declaration --*/

String[] stringArray1 = new String[5];

String[] stringArray2 = {"Hello", "Hello", "Hello", "Hello", "Hello"};




/*---- Creating Lists for Integer objects ----*/


List<Integer> list1 = new ArrayList<Integer>();                 /*-- Empty List, List size not required --*/

List<Integer> list2 = new ArrayList<>();                        /*-- Valid declaration, List size not required --*/

List<Integer> list3 = new ArrayList<Integer>(new Integer(100)); /*-- Integer object 100 as first element --*/

List<Integer> list4 = new ArrayList<>(new Integer(120));        /*-- Integer object 120 as first element --*/

List<Integer> list5 = new ArrayList<Integer>(130);              /*-- Integer object 130 as first element --*/




/*---- Creating Lists for String objects ----*/

/*-- We use Arrays.asList(String[] s) and (listName).toArray(String[] s) for dealing with Lists and String arrays--*/


List<String> list6 = new ArrayList<String>(Arrays.asList(new String("Hello"))); /*-- Valid declaration for String --*/

List<String> list7 = new ArrayList<>(Arrays.asList(new String("Hello")));       /*-- Valid declaration for String --*/

List<String> list8 = new ArrayList<> (Arrays.asList("Hello", "Hi"));            /*-- Adding two elements in the list --*/

List<String> list9 = new ArrayList<> (Arrays.asList(stringArray2));             /*-- Passing a String array in the asList method --*/       


/*---- Referencing ----*/


int[] intArray5 = new int[10];     

int[] intArray6 = intArray5;             

List<String> list10 = new ArrayList<>();

List<String> list11 = list10;            

Converting List<Integer> into int[] (until Java 7):

public class Test {

    public static void main(String[] args) {

        List<Integer> list = new ArrayList<Integer>();
        list.add(1);
        list.add(2);

        int[] intArray = new int[list.size()];

        for(int i=0; i<list.size(); i++){

            intArray[i] = list.get(i); /* Auto-unboxing from Integer -> int */

        }

    }

}

Converting List<Integer> into int[] (Java 8):

public class Test {

    public static void main(String[] args) {

        List<Integer> list = new ArrayList<Integer>();
        list.add(1);
        list.add(2);

        int[] intArray = list.stream().mapToInt(i->i).toArray();

    }

}

Converting int[] into List<Integer>:

public class Test {

    public static void main(String[] args) {

        int[] intArray = {1,2,3,4,5,6,7};

        List<Integer> list = new ArrayList<Integer>();

        for(int i : intArray){

            list.add(i);   /* Auto-boxing from int -> Integer */

        }

    }

}

Converting List<String> into String[]:

public class Test {

    public static void main(String[] args) {

        List<String> list = new ArrayList<String>();
        list.add("Item 1");
        list.add("Item 2");
        list.add("Item 3");
        list.add("Item 4");

        String[] stringArray = new String[list.size()];
        stringArray = list.toArray(stringArray);       

        }

}

Converting String[] into List<String>:

public class Test {

    public static void main(String[] args) {

        String[] stringArray = {"Hello", "Hi", "Whats up"};
        List<String> list = Arrays.asList(stringArray);    

        for(int i=0; i<list.size(); i++){
            System.out.println(list.get(i));
        }

        /* Enhanced for loop can also be used for printing the elements of the list */
        for(String s : list){
            System.out.println(s);
        }

    }

}

Overview of char[] and List<Character> (Optional read):

public class Test {

    public static void main(String[] args){

        String name = "A Character String";
        /*---- Note: char is a data type and Character is the wrapper class ----*/
        char[] nameArray = name.toCharArray(); /*---- Character Array Declaration ----*/


        List<Character> list = new ArrayList<>(); /*---- List of Character objects ----*/
        list.add('a');
        list.add('b');

        StringBuilder sb = new StringBuilder();

        /*-- Now adding elements to String Builder from Character list--*/
        /*--- NOTE: This method for printing elements works for Integers, Strings and Character lists---*/
        for(char ch : list){
            sb.append(ch);
        }

    }

}

Two Dimensional (2D) Array declaration:

public class Test {

    public static void main(String[] args){

            ArrayList<ArrayList<Integer>> rows = new ArrayList<>();

            for(int i=0; i<5; i++){
                ArrayList<Integer> row = new ArrayList<>();
                for(int j=0; j<5; j++){
                    row.add(j*j);
                }
                rows.add(row);
            }

            for(int i=0; i<5; i++){
                for(int j=0; j<5; j++){
                    System.out.print(rows.get(i).get(j)+" ");
                }
                System.out.println("");
            }

    }

}

Common ArrayList Operations:

Array and ArrayList Programs:

LinkedLists:

LinkedList is a class in Java and also a Data Structure. It contains nodes.

LinkedList class:

/*-- Node class Implementation --*/

class Node{

    int data;
    Node next;

    public Node(int data){
    this.data = data;
    }
}

LinkedList method addNodeToTail:

/*-- Method to add a Node to the tail of a LinkedList --*/

public void addNodeToTail(int addData){

    Node current = this;

    while(current!=null){

        if(current.next==null){
            current.next = new Node(addData);
            break;
        }

        current = current.next;
    }

}

Common LinkedList Operations:

LinkedList Programs:

Stacks and Queues:

Stack is a class in Java while Queue is an Interface, so both will have different kinds of declaration. Stack will have a regular declaration of Java class initialization while Queue Interface can be implemented with a LinkedList.

Stack<T> stack = new Stack<T>();
Queue<T> queue = new LinkedList<T>();

Time Complexity: Stack based operation such as pop(), push(), peek() takes O(1) time. Queue based operations such as add(), poll(), peek() also takes O(1) time. It means that the time taken for Stack operations and Queue operations is constant.

Stack Operations:

Queue Operations:

Sets:

HashSet, TreeSet and LinkedHashSet also uses concept of Hashing like Maps for storing the data and also It does not contains duplicate values!!

• HashSet - Stores the added values in the random order without duplicates.
• TreeSet - Stores the added values in the naturally ordered way without duplicates.
• LinkedHashSet - Stores the added values in the order of insertion without duplicates.

Let us see the working of a HashSet, TreeSet and a LinkedHashSet:

Implementation of a HashSet:

int intValue = 87611122;
String input = Integer.toString(intValue);

Set<Character> hashSet = new HashSet<Character>();

for(int i=0; i<input.length(); i++){

    hashSet.add(input.charAt(i));

}

Iterator<Character> it = hashSet.iterator();

while(it.hasNext()){
    System.out.print(it.next()+" ");
}

Output:

1 2 6 7 8

Implementation of a TreeSet:

int intValue = 87611122;
String input = Integer.toString(intValue);

Set<Character> treeSet = new TreeSet<Character>();

for(int i=0; i<input.length(); i++){

    treeSet.add(input.charAt(i));

}

Iterator<Character> it = treeSet.iterator();

while(it.hasNext()){
        System.out.print(it.next()+" ");
}

Output:

1 2 6 7 8

Implementation of a LinkedHashSet:

int intValue = 87611122;
String input = Integer.toString(intValue);

Set<Character> treeSet = new LinkedHashSet<Character>();

for(int i=0; i<input.length(); i++){

    treeSet.add(input.charAt(i));

}

Iterator<Character> it = treeSet.iterator();

while(it.hasNext()){
        System.out.print(it.next()+" ");
}

Output:

8 7 6 1 2

Set Operations:

Maps:

HashMap, TreeMap and LinkedHashMap:

Map is an Interface in Java while HashMap, TreeMap and LinkedHashMap are classes.

HashMap, TreeMap and LinkedHashMap:

• HashMap - Stores keys and values in an unordered way and contains only unique keys.
• TreeMap - Stores keys and values in a naturally ordered way and contains only unique keys.
• LinkedHashMap - Stores keys and values in the order of keys insertions and contains only unique keys.

HashMap, TreeMap and LinkedHashMap can be used for the following kind of problems:

• Find whether a substring is part of a String or not!
• How many times a letter is occurring in a String?
• Arrange the words of a String in ASC order of their length!

Map<T, E> hm1 = new HashMap<T, E>();
Map<E, E> hm2 = new HashMap<E, E>();

Let us see the output of the code for a HashMap, TreeMap and a LinkedHashMap:

Implementation of a HashMap:

//Counting the occurrence of digits in a number!
int intValue = 87611122;
String stringValue = Integer.toString(intValue);
int[] input = new int[stringValue.length()];
int inputLength = input.length;

for(int i=0; i<inputLength; i++){
    input[i] = Character.getNumericValue(stringValue.charAt(i));
}

HashMap<Integer, Integer> hm = new HashMap<>();

for(int i=0; i<inputLength; i++){

    Integer j = hm.get(input[i]);

    if(j==null)
        hm.put(input[i],1);

    else
        hm.put(input[i],j+1); /*-- Here it is overwriting the value of the same keys --*/

}

for(Integer i : hm.keySet()){
    System.out.print(i + "="+ hm.get(i)+" ");
}

Output:

1=3 2=2 6=1 7=1 8=1

Alternate Implementation of a HashMap:

/*----NOTE: Method containsKey can also be used to match the keys----*/

int intValue = 87611122;
String stringValue = Integer.toString(intValue);
int[] input = new int[stringValue.length()];
int inputLength = input.length;

for(int i=0; i<inputLength; i++){
    input[i] = Character.getNumericValue(stringValue.charAt(i));
}

HashMap<Integer, Integer> charCounts = new HashMap<>();

for (int i = 0; i < inputLength; ++i){

        int digit = input[i];

    if (!charCounts.containsKey(digit))
        charCounts.put(digit, 1);

    else
        charCounts.put(digit, charCounts.get(digit) + 1);

}

System.out.println(charCounts);

Output:

{1=3, 2=2, 6=1, 7=1, 8=1}

Implementation of a TreeMap:

//Counting the occurrence of digits in a number!
int intValue = 87611122;
String stringValue = Integer.toString(intValue);
int[] input = new int[stringValue.length()];
int inputLength = input.length;

for(int i=0; i<inputLength; i++){
    input[i] = Character.getNumericValue(stringValue.charAt(i));
}

TreeMap<Integer, Integer> tm = new TreeMap<>();

for(int i=0; i<inputLength; i++){

    Integer j = tm.get(input[i]);

    if(j==null)
        tm.put(input[i],1);

    else
        tm.put(input[i],j+1);

}

for(Integer i : tm.keySet()){
    System.out.print(i + "="+ tm.get(i)+" ");
}

Output:

1=3 2=2 6=1 7=1 8=1

Implementation of a LinkedHashMap:

//Counting the occurrence of digits in a number!
int intValue = 87611122;
String stringValue = Integer.toString(intValue);
int[] input = new int[stringValue.length()];
int inputLength = input.length;

for(int i=0; i<inputLength; i++){
    input[i] = Character.getNumericValue(stringValue.charAt(i));
}

LinkedHashMap<Integer, Integer> lm = new LinkedHashMap<>();

for(int i=0; i<inputLength; i++){

    Integer j = lm.get(input[i]);

    if(j==null)
        lm.put(input[i],1);

    else
        lm.put(input[i],j+1);

}

for(Integer i : lm.keySet()){
    System.out.print(i + "="+ lm.get(i)+" ");
}

Output:

8=1 7=1 6=1 1=3 2=2

Printing all the Keys and the Values from a HashMap:

public class Test {

    public static void main(String[] args) {

        String sentence = "I have some work for all of you guys.";

        String input = sentence.substring(0, sentence.length()-1);

        HashMap<String, Integer> hm = new HashMap<>();

        for(String word : input.split(" ")){

            hm.put(word, word.length());

        }

        /*--- Printing the keys and values of a HashMap using Lambdas: ---*/

        hm.entrySet().forEach(e->{
        System.out.println(e.getKey() + " " + e.getValue());  
        });

        /*--- Printing the values of a HashMap using conventional for loop: ---*/

        for(Entry<String, Integer> e : hm.entrySet()){
            System.out.println(e.getKey() + " "+ e.getValue());
        }

    }

}

Printing the Keys of a Map in the ASC order of its Values:

Input String: I have some work for all of you guys.

Output String: I of for all you have some work guys

public class Test {

    public static void main(String[] args) {

        String sentence = "I have some work for all of you guys.";

        String input = sentence.substring(0, sentence.length()-1);

        LinkedHashMap<String, Integer> lhm = new LinkedHashMap<>();

        for(String word : input.split(" ")){

            lhm.put(word, word.length());

        }

        /*--- Printing the keys and values in the order of ASC order of the values: ---*/

        lhm.entrySet().stream()
        .sorted(Map.Entry.<String, Integer>comparingByValue())
        .forEach(e->{
         System.out.print(e.getKey() + " ");  
         });

    }

}

Common Map Operations:

Map/Set Programs:

Trees:

Tree:

• Binary Tree
• Binary Search Tree(BST)

Tree-Algorithms:

• Level-Order Traversal (Breadth First Search)
• Pre-Order Traversal (Depth First Search)
• Post-Order Traversal (Depth First Search)
• In-Order Traversal (Depth First Search)

Binary Tree:

A Tree data structure where each node can at-most have 2 children i.e. a left child and a right child!

Tree Node class for Binary Tree and Binary Search Tree(BST):

class TreeNode{
    TreeNode left,right;
    int dValue;

    TreeNode(int v){
        dValue = v;
        left = null;
        right = null;
    }
}

PreOrderTraversal in a Binary Tree:

Binary Search Tree(BST):

A Binary Tree where the left child is less than the root and the right child is greater than the root and each node can have at-most have 2 children! All the nodes in the left subtree are less than the root node and all the nodes in the right subtree are greater than the root node. All the subtrees in a BST are BST.

Tree Node class for Binary Tree and Binary Search Tree(BST):

class TreeNode{
    TreeNode left,right;
    int dValue;

    TreeNode(int v){
        dValue = v;
        left = null;
        right = null;
    }
}

Tree Programs: