Queues, BST, and lists

In object-oriented programming, we often deal with objects (hence the name). Because of this, programmers have come up with several unique ways to store and access data. First, we learn about the most primitive form, variables, which let us name the objects we create using the new keyword. The next step is arrays, a collection of variables of the same type. These two methods don't offer any kind of flexibility, however, we are not limited to them: we also have access to different data structures.

ArrayList, LinkedList, Stack are some of the examples of the built-in classes Java offers us. Each of these is a container that holds variables, or sometimes other containers. They each have unique ways of accessing and modifying the data stored in them. It is important to know how they work because it enables us to maximize our coding efficiency and create more streamlined and effective solutions.

Array list

By now you should have some idea of how arrays work. They have a predetermined size which can't be changed, which causes a few limitations. ArrayList is a simple structure that works similarly to an array, however, its limitations are removed after initialization and its size can be modified.

public static void main(String[] args) {
    ArrayList<T> arrayList = new ArrayList<T>();
    T element = new T();
    //T can be replaced by any type which is not primitive.

    arrayList.add(element); 
    //Adds an element to the ArrayList and returns true if successful.

    arrayList.get(0); 
    //Returns the element on the specified index
        
    arrayList.indexOf(element); 
    //Returns the index of the specified object, or -1 if the ArrayList doesn't contain the object

    arrayList.remove(element); 
    //Removes an element and returns true if successful
}

The methods above are used to manipulate and access the ArrayList, so let's discuss how exactly they work and what their time complexities look like. If you don't remember what time complexities are you can click here to refresh your memory.

• add(E element): this method adds an element to the end of the ArrayList. The time complexity is O(1) on average. However, if the ArrayList needs to resize its internal array to accommodate the new element, the time complexity becomes O(n), where n is the current size of the ArrayList. This is because resizing involves creating a new array and copying the existing elements.

• get(int index): this method retrieves the element at the specified index from the ArrayList. The time complexity is O(1) because accessing an element by its index in an ArrayList is a constant-time operation.

• indexOf(Object o): this method returns the index of the first occurrence of the specified element in the ArrayList. The time complexity is O(n) because it may need to iterate through the ArrayList to find the element. In the worst case, it needs to search through all elements.

• remove(int index): this method removes the element at the specified index from the ArrayList. The time complexity is O(n - index) because it may require shifting the subsequent elements to fill the gap left by the removed element. If the element to remove is at the end of the ArrayList, the time complexity is O(1).

It's important to note that these time complexities assume that the ArrayList is not sorted. If it is sorted, some operations like searching (using indexOf or contains) can be optimized by using binary search, resulting in a time complexity of O(log n).

Stack

The stack behaves in a very simple manner. It is as if you were stacking books on a bookshelf. First, to start stacking, we should build a bookshelf... duh.

Stack<Book> bookshelf = new Stack<Book>();

In this code, a new stack is created with the new keyword. The angle brackets surrounding the word "Book" let us define what type of objects will be stored in our container, which in this case are books.

After building the bookshelf, we can push some books into it.

bookshelf.push(book1)
bookshelf.push(book2)
bookshelf.push(book3)

Here we use the Stack's built-in method .push(T object) to append an object, which must have the same type as declared while creating the stack.

Unfortunately, since our bookshelf is vertical we can only pop out the book that was pushed in last.

Book lastBook = bookshelf.pop();

Here we use another built-in Stack method .pop() which removes the element which was inserted last and returns it. This kind of removal is called LIFO or FILO, which stands for Last In First Out or First In Last Out respectively.

Of course, we can interact with our bookshelf in other ways:

• We can take a peek at the book which is placed last without taking it out with the .peek() method.

  Book lastBook = bookshelf.peek();
  

  The .peek() method returns the last element of the Stack without changing the Stack.

• We can check if it's empty with the .IsEmpty() method.

  boolean isItEmpty = bookshelf.isEmpty();
  

  This method returns a boolean value, which is true if the Stack is empty, and false otherwise.

The time complexities of all the aforementioned methods are O(1) , meaning that each operation requires the same amount of time. That pretty much covers the Stack class.

Stacking challenge

Now that you've armed yourself with knowledge, let's tackle some coding problems. You may have heard of the valid parentheses problem. Here's how it goes:

"Given a string s containing just the characters '(', ')', '{', '}', '[' and ']'. Determine if the input string is valid".

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.

2. Open brackets must be closed in the correct order.

3. Every close bracket has a corresponding open bracket of the same type.

An example of a valid input string would be "{ { [ ( ) ] } }", where each opening bracket is accompanied by a closing one of its type.

We could use the string's built-in methods and iterate over the characters one by one, using some sort of double pointers, or we could use one of the books from our bookshelf.

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        } else {
            if (stack.empty()) {
                return false;
            }
            if (c == ')' && stack.peek() == '(') {
                stack.pop();
            } else if (c == '}' && stack.peek() == '{') {
                stack.pop();
            } else if (c == ']' && stack.peek() == '[') {
                stack.pop();
            } else {
                return false;
            }         
        }     
    }
    return stack.empty();
}

The Stack data structure is perfect for this problem because of how easy it is to add and remove elements from it. The code works like this:

1. The code goes through each character in the string.

2. If the character is an opening bracket, such as (, {, or [, it is added to the stack.

3. If the character is a closing bracket, such as ), }, or ], the code checks if the stack is empty. If it is, there is no matching opening bracket, so the string is invalid.

4. If the stack is not empty, the code compares the closing bracket with the top element of the stack. If they match, for example, ) matches with (, } matches with {, or ] matches with [, – the top element is removed from the stack.

5. If the closing bracket doesn't match the top element of the stack, the string is invalid.

6. After checking all the characters in the string, if the stack is empty, it means that all opening brackets had matching closing brackets, so the string is valid.

7. If there are remaining opening brackets in the stack, the string is invalid.

To sum up, this code uses a stack to ensure that opening and closing brackets in a string are properly balanced. If all brackets are matched correctly, it returns true; otherwise, it returns false.

The time complexity of the code is O(n) because it iterates through each character in the string once. The space complexity is also O(n) because the stack can store up to n opening parentheses in the worst-case scenario.

Linked list

Now let's move on from our vertical bookshelf and tackle another type of container. A linked list can be looked at as a chain of information. Each element of a linked list stores information just like the other data structures, but additionally, it stores a reference to the element in front of it. We call the elements of a linked list nodes. Here's a quick look at how nodes function.

class Node<T> { //T can be replaced with any type, which is not primitive
    public T value; //The information stored within a node
    public Node<T> next; //The next element in the list
    
    public Node(T value) {
        this.value = value;
    }
    
    public Node(T value, Node<T> next) {
        this.value = value;
        this.next = next;
    }
    public Node(){
        
    }
}

You may have noticed that we have three separate constructors. This is because the first allows us to create a Node without specifying its successor. In the second, both the value and the next nodes are necessary. And the third constructor doesn't require any additional input.

With that, let's implement this diagram:

public static void main(String[] args) {
    T value = new T();

    Node<T> head = new Node<>(); // Head has no value
    Node<T> node = new Node<>(value); // The value of node is value     
    Node<T> tail = new Node<>(null,head); // The value of tail is null and its next element is head
        
    head.next = node; // We set the next node of head to node
    node.next = tail; // We set the next node of node to tail
}

The code and the diagram above showcase what's called a circular linked list, since the tail node points to the head node. Of course, there are other types of linked lists, both circular and linear.

It's also important to remember that the removal and addition of elements from the beginning and the end of a linked List require no iterations, which means they are done in constant time or, in terms of time complexity, O(1).

Linking knowledge with programming

A linked list is one of the more challenging tools to use because it requires quite a bit of recursion to iterate over it. And it is because of that challenging nature it's worth mastering it.

Let's look at one of the most common problems regarding linked lists: Reverse Linked List.

The title describes the problem very well, we simply have to reverse the list and return the reversed list, given its head:

public ListNode reverseList(ListNode head) {
    if (head == null) {
        return null;
    }

    ListNode prev = null;
    ListNode current = head;

    while (current != null) {
        ListNode next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }

    return prev;
}

1. This function starts by initializing two variables, prev and current, as null and head, respectively. These variables are used to keep track of the previous node and the current node during the iteration process.

2. The while loop continues as long as the current node is not null, meaning there are still nodes to process in the original list.

3. Inside the loop, the code performs the following steps:
   a. Create a temporary variable next and assign it the value of current.next. This step stores the reference to the next node in the original list before modifying it.
   b. Assign prev to current.next, effectively reversing the connection of the current node. By doing this, the current node is now pointing to the previous node instead of the next node.
   c. Move the prev pointer one step forward by assigning it the value of current. This step allows the prev pointer to progress to the next node in the reversed list.
   d. Move the current pointer one step forward by assigning it the value of next. This step moves the current pointer to the next node in the original list so that the process can continue.

4. After the loop finishes, the prev variable points to the last node in the original list, which is now the first node in the reversed list. This is because the prev pointer keeps getting updated to the previous node as we iterate through the list.

5. The function returns the prev node, which becomes the new head node of the reversed list.

In a nutshell, the function works by iteratively reversing the connections between nodes. It uses the prev and current pointers to keep track of the reversed list as it progresses through the original list. By updating the next pointers of each node, the function effectively reverses the order of the nodes in the linked list.

The time complexity of the code is O(n) because it visits and modifies each node once, and the space complexity is O(1) because it uses a constant amount of extra space.

This problem demonstrates the difficulty of iterating over a linked list quite well, but now that we know how to do it, let's look at another problem.

Merging two sorted lists

You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list.

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

    if (list1 != null && list2 != null) {
        if (list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
    if (list1 == null)
        return list2;
    return list1;
}

1. This function takes two linked lists, list1 and list2, as input and returns a new linked list that contains all the nodes from both lists in sorted order.

2. If both list1 and list2 are not null, which means nodes are remaining in both lists to be merged. In this case, the code compares the values of the first nodes in both lists.

3. If the value of the first node in list1 is less than the value of the first node in list2, the code:
   a. Sets the next pointer of list1 to the result of recursively calling mergeTwoLists with the remaining nodes of list1 (excluding the first node) and list2. This step essentially appends the merged list of the remaining nodes to the first node of list1.
   b. Returns list1 as the merged list, ensuring that the nodes are sorted in ascending order.

4. If the value of the first node in list2 is less than or equal to the value of the first node in list1, the code:
   a. Sets the next pointer of list2 to the result of recursively calling mergeTwoLists with list1 and the remaining nodes of list2 (excluding the first node). This step appends the merged list of the remaining nodes to the first node of list2.
   b. Returns list2 as the merged list, ensuring that the nodes are sorted in ascending order.

5. If one of the lists becomes null, indicating that all nodes from that list have been merged, the code returns the other non-null list as the merged list. This step is necessary to include any remaining nodes from the non-null list in the merged result.

6. If both list1 and list2 are null, indicating that both lists are empty, the code returns null to represent an empty list.

In summary, this code recursively merges two sorted linked lists by comparing the values of their nodes and building a new sorted list accordingly. It uses the next pointers to connect the nodes in the merged list.

The time complexity of the code is O(n + m) because it processes each node in both lists once. The space complexity is also O(n + m) due to the recursion depth and the stack space used by the recursive calls.

As we have seen with these two examples, traversing and operating on linked lists and their elements is quite troublesome because each element holds a reference to its successor. But what's more troublesome than one reference? Two of them.

Binary trees

A binary tree is structurally quite similar to a linked list. However, instead of connecting an object to an object, a binary tree can link an element to two others.

We call this diagram a binary tree, or mostly, just a tree. The beginning point of the tree is called a root. In this diagram, the nodes numbered 2 and 3 are called sibling nodes, and the node numbered 1 (aka the root) is their parent node. Similarly, 4 and 5 are the child nodes of 2, and they are also called leaf nodes since they don't have child nodes of their own. This is what their code would look like:

class Node {

    T key;
    Node left, right;

    public Node(T value){
        this.value = value;
        left = right = null;
    }
    public Node(T value, Node left){
        this.value = value;
        this.left = left;
        this.right = null;
    }
    public Node(T value, Node left, Node right){
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

The left and right fields of the Node class refer to its children. For example, the left field of node 2 on our diagram would be node 4.

Again, we use three constructors. The first constructor initializes the node with only its value letting us set its children after initialization. The second constructor allows us to set the left child during initialization, and the third allows us to set both. Of course, both values can be changed after initialization, but it is better to do it ahead of time whenever possible.

Tree traversal

Due to the access to two other elements, the binary tree gives us a lot of variety in traversal. Some of these methods include:

• Depth First Search (or DFS)
  a. Inorder Traversal
  b. Preorder Traversal
  c. Postorder Traversal

• Level Order Traversal, or Breadth First Search (BFS)

• Boundary Traversal

• Diagonal Traversal

For the purposes of this topic, we will only go over the DFS.

Here's how the DFS traversal works:

1. Start from the given node (usually the root) of the tree.

2. Visit the current node and perform any desired operations on it. This could include printing the node's value, collecting data, or performing some computations.

3. Recursively traverse the children of the current node in a depth-first manner. This means selecting one child node at a time and repeating the process from step 2.

4. If a child node has no further children (leaf node), or all its children have been visited, backtrack to the parent node and explore the remaining unvisited children.

5. Repeat steps 2 to 4 until all nodes in the tree have been visited.

DFS can be implemented using either a recursive approach or an iterative approach using a stack.

public void dfsRecursive(TreeNode node) {
    if (node == null) {
        return;
    }
    System.out.println(node.value);
    
    dfsRecursive(node.left);
    dfsRecursive(node.right);
}

Recursive approach:

1. Implement a recursive function (let's call it dfsRecursive) that takes a node as input.

2. Base case: if the input node is null, return.

3. Visit the current node and perform any desired operations (in this case, we simply print its value).

4. Recursively call dfsRecursive for each child of the current node.

public void dfsIterative(TreeNode root) {
    if (root == null) {
        return;
    }

    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        
        System.out.println(node.val);

        if (node.right != null) {
            stack.push(node.right);
        }

        if (node.left != null) {
            stack.push(node.left);
        }
    }
}

Iterative approach using Stack:

1. Create an empty stack and push the root node onto the stack.

2. While the stack is not empty:

   • Pop the top node from the stack.

   • Visit the popped node and perform any desired operations (in this case, we just print its value).

   • Push all the children of the popped node onto the stack (in reverse order if applicable).

3. Repeat step 2 until the stack is empty.

DFS traversal explores the tree in a depth-first manner, prioritizing the exploration of one branch before moving on to the next branch. This approach is useful for tasks such as searching, pathfinding, and tree analysis.

Binary problems

Now that you can easily traverse a binary tree let's put our knowledge to the test and have a look at the Merge Two Binary Trees problem.

"You are given two binary trees root1 and root2.

Suppose that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, you sum node values up as the new value of the merged node. Otherwise, the non-null node will be used as the node of the new tree".

public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
    if (root1 == null) return root2;
    if (root2 == null) return root1;
    root1.val += root2.val;
    root1.left = mergeTrees(root1.left, root2.left);
    root1.right = mergeTrees(root1.right, root2.right);
    return root1;
}

1. The first two if statements check if either root1 or root2 is null. If one of them is null, it means there are no more nodes in that tree to merge, so the code returns the non-null tree. This handles the base case for recursion.

2. If neither root1 nor root2 is null, the code proceeds to merge the nodes. It adds the values of root1 and root2 together and assigns the sum to root1.val. This step combines the values of the corresponding nodes from both trees.

3. The code then recursively calls mergeTrees for the left child of root1 and root2 by passing root1.left and root2.left as arguments. This step merges the left subtrees.

4. Similarly, the code recursively calls mergeTrees for the right child of root1 and root2 by passing root1.right and root2.right as arguments. This step merges the right subtrees.

5. Finally, the function returns root1 as the merged binary tree.

To recap, the code merges two binary trees by summing up the corresponding nodes. It uses recursion to traverse the trees and combines the values of the nodes. The merging process starts from the roots and propagates down to the leaves of the trees.

The time complexity of the code is O(min(n, m)), where n and m are the number of nodes in root1 and root2, respectively. The code visits each node once, taking into account the smaller tree. The space complexity is also O(min(n, m)), considering the recursion depth and the stack space used by the recursive calls.

Conclusion

In this topic, you have explored the vast diversity of data structures in Java. This is, however, only the tip of the iceberg since there are quite a bit more. Let's summarize what we have just covered.

• ArrayList is a flexible data structure that can store elements of any nonprimitive type. It behaves similarly to an array, the main difference being the ability to resize.

• Stack is a data structure that follows the Last-In-First-Out (LIFO) principle. The addition and removal of elements are efficient and simple and both have O(1) time complexity.

• LinkedList is a data structure consisting of nodes that store values and references to the next node. It's very versatile but at the same time difficult to master. The time complexity of reversing a linked list is O(n).

• Binary tree works similarly to a linked list but, instead of elements storing a reference to a single successor, they hold a reference to two. The first node of a tree is called the root. Each node may only have two child nodes. If it has two children, they are called sibling nodes.

• There are a lot of traversal methods. In this topic, you learned about the DFS (depth-first search), which works by exploring as far as possible along each branch before backtracking.

If you want to know a little more information, you can find it here, here, and here.