Introduction to Data Structure & Algorithms in Java - Part 2

Linked Lists

What is a linked list?

graph LR
  head(1) --next node--> node1(2)
	node1 --next node--> node2(3)
	node2 --next node--> null(Null)

Implementing a linked list in Java

public class Node<T> {
	private T data;
	private Node<T> nextNode;
	
	public Node(T data) {
		this.data = data;
	}
	
	public void setData(T data) {
		this.data = data;
	}
	
	public T getData() {
		return data;
	}
	
	public Node<T> getNextNode() {
		return nextNode;
	}
	
	public void setNextNode(Node<T> nextNode) {
		this.nextNode = nextNode;
	}
	
	@Override
	public String toString() {
		return this.data.toString();
	}
	
}

public class LinkedList<T> {

	private Node<T> head;

	public Node<T> getHead() {
		return this.head;
	}

	public void addAtStart(T data) {
		Node<T> newNode = new Node<T>(data);
		newNode.setNextNode(this.head);
		this.head = newNode;
	}
}

Inserting a new node

• addAtStart(data): O(1)

Length of a linked list

public int length() {
		if (head == null)
			return 0;
		int length = 0;
		Node<T> curr = this.head;
		while (curr != null) {
			length += 1;
			curr = curr.getNextNode();
		}
		return length;
	}

Deleting the head node

• Delete head: O(1)

Searching for an item

• Search data: O(n)

Doubly ended lists

• We track the tail

• We can add a new node from head or tail

Inserting data in a sorted linked list

• Insert data: O(n)

Doubly linked list

Stacks and Queues

Stacks

Stacks

• stacks using array

• peek: read the value of topmost element in the stack without removing it

• pop: read the value of the topmost element in the stack and remove it

• push: add new data at the top of the stack

Double Ended Queues (DEQueues)

• DeQueues using arrays

Queues

• queues using arrays

Abstract data types

Implementing stacks using arrays

maxSize = 9;
int[] stackArray = new int[maxSize];
int top = - 1;

• push(7)
• O(1)

• peek(): return 7
• O(1)

• pop(): return 7 and also decrease the value of top
• O(1)

Queues

• enqueue: insert an element in the queue from the tail towards the head

• dequeue: remove an element in the queue from the head of the queue

Queues using arrays

maxSize = 8;
int[] queueArray = new int[maxSize];
int head = -1
int tail = -1

• enqueue(8)

 

 

• enqueue(12)

 

 

enqueue(17); enqueue(73)

enqueue(19);enqueue(12)

enqueue(3); enqueue(98)

 

dequeue()

 

 

 

dequeue()

dequeue()

 

• enqueue(27)

• enqueue(9)

• Math.abs(tail index - head index): number of items

• This is circular queue

 

Double-ended queues

Double-ended queues using an array

• Insert right (7)

• Insert right (12)

 

• Insert left (14)

 

 

 

maxSize = 8;
int[] queueArray = new int[maxSize];
int head = -1
int tail = -1

• Insert right(7)

• Insert right(12)

 

 

 

• Insert left(14)

• Insert left(9)

• Insert left(15)

 

• delete Left(15)

 

Recursion

Introduction

• Implement factorial

• How the recursion call stack works

• Implement Tower of Hanoi

• Implement Merge Sort algorithm

public int gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}

public int factorial(int n) {
	int result = 1;
	for(int i =1; i<=n; i++) {
		result *= i;
	}
}

Understanding recursion

public int factorial(int n) {
	if (n == 0) return 1;
	return n * factorial(n-1);
}

Tail recursion

public int tail_factorial(int n, int result) {
	if (n == 0) return result;
	return tail_factorial(n-1, n*result);
}
public int factorial(int n) {
	return tail_factorial(n, 1);
}

Tower of Hanoi

• move(n, ‘A’, ‘C’, ‘B’)
• move(n-1, ‘A’, ‘B’, ‘C’)
• Print “Moving disc n from A to C”
• move(n-1, ‘B’, ‘C’, ‘A’)

 

Tower of Hanoi: Implementation

/**
 * It takes exponential time.
 * For n discs, number of moves are (2^n)-1
 * Number of moves - [1->1, 2->3, 3->7, 4->15, 5->31...]
 */
public class TowerOfHanoi {
	private static int numOfMoves = 0;
	
	public void move(int numberOfDiscs, char from, char to, char inter) {
		if (numberOfDiscs == 1) {
			System.out.println("Moving disc 1 from " + from + " to " + to);
			numOfMoves++;
		} else {
			move(numberOfDiscs - 1, from, inter, to);
			System.out.println("Moving disc " + numberOfDiscs + " from " + from + " to " + to);
			numOfMoves++;
			move(numberOfDiscs - 1, inter, to, from);
		}
	}
	
	public static void main(String[] args) {
		TowerOfHanoi toh = new TowerOfHanoi();
		toh.move(5, 'A', 'C', 'B');
		System.out.println("Number of moves: " + numOfMoves);
	}
}

Merge sort

Merge sort: Pseudocode

MergSort(A, start, end)
	if start < end
		middle = Floor[(start + end)/2]
		MergeSort(A, start, middle)
		MergeSort(A, middle+1, end)
		Merge(A, start, middle, end)

Merge step: Pseudocode

Time complexity of merge sort

• O()

Binary Search Trees

The tree data structure

ㅤ	Sorted Arrays	Linked List
Search	Fast O(log(n))	Slow O(n)
Insert	Slow O(n)	Fast O(1)
Delete	Slow O(n)	Fast O(1)

flowchart TD
  n1((root)) --- n2((2))
	n1 --- n3((3))
	n1 --- n4((4))
	n2 --- n5((5))
	n3 --edge--- n6((6))
	n3 --- n7((node))
	

Binary trees

flowchart TD
  n1((data)) --left--> n2((data))
	n1 --right--> n3[null]
	n2 --> n5[null]
	n2 --> n8[null]

	

flowchart TD
  n1((1)) --- n2((2))
	n1 --- n3((3))
	n2 --- n5((5))
	n2 --- n8(8)
	n3 --- n6((6))
	n3 --- n7((7))
	

Binary search trees

public class TreeNode {
	private Integer data;
	private TreeNode leftChild;
	private TreeNode rightChild;

	public TreeNode(Integer data) {
		this.data = data;
	}
	public void insert(Integer data) {
		if (data >= this.data) { // insert in right subtree
			if (this.rightChild == null)
				this.rightChild = new TreeNode(data);
			else
				this.rightChild.insert(data);
		} else { // insert in left subtree
			if (this.leftChild == null)
				this.leftChild = new TreeNode(data);
			else
				this.leftChild.insert(data);
		}
	}
public TreeNode find(Integer data) {
		if (this.data == data)
			return this;
		if (data < this.data && leftChild != null)
			return leftChild.find(data);
		if (rightChild != null)
			return rightChild.find(data);
		return null;
	}
}

public class BinarySearchTree {

	private TreeNode root;
	public void insert(Integer data) {
			if (root == null)
				this.root = new TreeNode(data);
			else
				root.insert(data);
	}
}

Finding an item in a binary search tree

public TreeNode find(Integer data) {
		if (root != null)
			return root.find(data);
		return null;
	}

Inserting an item in a binary search tree

public void insert(Integer data) {
			if (root == null)
				this.root = new TreeNode(data);
			else
				root.insert(data);
	}

Deleting an item: Case 1 - delete a leaf node

Deleting an item: Case 2 - delete node has one child

Delete an item: Case 3 - delete node has two children

Delete an item: Soft delete

public class TreeNode {
	private Integer data;
	private TreeNode leftChild;
	private TreeNode rightChild;
	private boolean deleted = false;

	public TreeNode(Integer data) {
		this.data = data;
	}
	public void delete(){
        this.deleted = true;
    }
}

Finding smallest and largest values

public Integer largest() {
		if (this.root != null)
			return root.largest();
		return null;
	}
public Integer smallest() {
		if (this.root != null)
			return root.smallest();
		return null;
	}

Tree traversal: In order

flowchart TD
	classDef blue fill:#055C9D,stroke:#000,color:#000
  n1((52)) --- n2((33))
	n1 --- n3((65))

Tree traversal: Pre order

flowchart TD
	classDef blue fill:#055C9D,stroke:#000,color:#000
  n1((52)) --- n2((33))
	n1 --- n3((65))

Tree traversal: Post order

flowchart TD
	classDef blue fill:#055C9D,stroke:#000,color:#000
  n1((52)) --- n2((33))
	n1 --- n3((65))

Unbalanced tree vs. balanced trees

Height of a binary tree

 

Time complexity of operations on binary search trees

• Search item = O()

• delete item = O()

References

• https://www.linkedin.com/learning/introduction-to-data-structures-algorithms-in-java/introduction-7?autoplay=true