G4G0-2/Data Structures/Focused Exam Revision.md

Interfaces, Linked Lists, Array Lists

Definitions

Interface

A contract that defines methods, field variables, return types, a class must implement. An example of this is the List interface in Java.

Linked List

A data structure where nodes are linked using pointers. Each node contains data - storing a value, and pointer - referencing the next node (and previous in doubly linked).

Types

• Singly Linked (Unidirectional)
• Doubly Linked (Bidirectional)
• Circular Linked (Last node points to first node)

Array List

A resizable array-based data structure where elements are stored in contiguous memory locations. Arrays allow for random access through an index corresponding to a location in the array. When capacity is exceeded, the list can resize dynamically.

Difference between Linked and Array Lists

• Memory Allocation
  • LL -> Dynamic; Array -> Contiguous
• Performance
  • LL -> Good for Insert/Delete; Array -> Good for searching

Use Case

Linked List

Stacks / Queues

Linked lists can efficiently add or remove from either end.

• Stack: Singly Linked List, insert/remove at head. O(1)
• Queue: Doubly Linked List, efficient tail and head operations (enqueue dequeue)

Task Scheduling

• Dynamic data, removing / adding tasks easier with linked list

Undo Function

• Doubly Linked List, track user actions. move back or forward allows for easy undo / redo

Array List

Database Caching

• Frequent random access, ideal for storing cached records.

Dropdown Menus

• Store and dynamically resize when elements need to be added to UI drop-downs that change based on input.

Inventory Systems

• Elements added or accessed without many deletions, Array List would allow for predictable resizing.

Implementation

Interface

interface Interface {
	void method();
	int method2(int param)
}

Linked List

class Node {
	int data;
	Node next;
	Node(int data) {
		this.data = data
		this.next = null
	}
}

class LinkedList {
	Node head;

	void insert(int data) {
		Node newNode = new Node(data)
		if (head == null) {
			head = newNode;
		} else {
			Node temp = head;
			while (temp.next != null) {
				temp = temp.next;
			}
			temp.next = newNode;
		}
	}
	void display() {
		Node temp = head;
		while (temp != null) {
			System.out.print(temp.data + " => ");
			temp = temp.next;
		}
		System.out.println("null");
	}
}

Array List

import java.util.ArrayList;
class ArrayList {
	public static void main(String[] args) {
		ArrayList<Integer> list = new ArrayList<>();
		list.add(10);
		list.add(20);
		list.add(30);
		System.out.println(list);
	}
}

Stacks

class Stack {
	private int[] stack;
	private int top;
	private int size;

	public Stack(int size) {
		this.size = size;
		stack = new int[size];
		top = -1; //Empty Stack
	}

	// Push: Add Element to Stack
	/**
	 * Take Parameter, check if top = size -1 (overflow),
	 * stack[++top] = value
	 **/
	public void push(int value) {
		if (top == size - 1) { // Check for overflow
			throw new RuntimeException('Stack Overflow');
			return;
		}
		stack[++top] = value; // Increment then add value
	}

	// Pop: Remove top Element from Stack
	/**
	 * No parameter, check if empty (underflow), return -1
	 * return stack[top--]
	**/
	public int pop() {
		if (isEmpty()) { // Check for underflow
			throw new RuntimeException('Stack Underflow');
			return -1; // Error
		}
		return stack[top--]; // Return top value then decrement
	}

	// Peek: Return top element
	/**
	 * Check if empty, return -1, return stack[top]
	**/
	public int peek() {
		if (isEmpty()) {
			throw new RuntimeException('Stack Empty');
			return -1;
		}
		return stack[top];
	}

	// isEmpty: Checks if stack empty
	/**
	 * return bool of expr: top == -1, empty value
	**/
	public boolean isEmpty() {
		return top == -1;
	}

	// Main Method for Testing
	public static void main(String[] args) {
		Stack stack = new Stack(5);
		stack.push(10);
		stack.push(20);
		stack.push(30);
		System.out.println('Top: ' + stack.peek()); // Output 30
		System.out.println('Popped: ' + stack.pop()) // Output 30
		System.out.println('Is Empty?: ' + stack.isEmpty()) // Output false
	}
}

Parenthesis Matching

• Push opening brackets, closing brackets pop correspondingly, if no match, false.

Dijkstra's Two-Stack Algorithm

• Eval parenthesized arithmetic expressions
  • One stack operands
  • One stack operators
• Processes expression by push/pop elements on stacks, eval subexpression when closing parenthesis encountered.
• Assumed expression is fully parenthesised