LearnFrenzy
Sign in Take a free test

Java Programming · Topic 28 of 28

Data Structures in Java

  • 4 exercises
  • 60 questions
  • ~60 min
  • Answers explained

Coding Techniques

Data Structures in Java · Study material

Hash table with separate chaining

A hash table turns a key into a bucket index with hashCode(), keeps colliding keys in a short chain, and doubles its bucket array when the load factor passes 0.75 – the same plan HashMap follows (plus tree bins for very long chains).

public class Main {
    // A tiny String → int hash table with separate chaining (the idea behind HashMap)
    static class ChainedHashTable {
        private static class Entry {
            final String key;
            int value;
            Entry next;
            Entry(String key, int value, Entry next) { this.key = key; this.value = value; this.next = next; }
        }

        private Entry[] buckets = new Entry[4];
        private int size;

        private static int index(String key, int length) { return (key.hashCode() & 0x7fffffff) % length; }

        void put(String key, int value) {
            int i = index(key, buckets.length);
            for (Entry e = buckets[i]; e != null; e = e.next)
                if (e.key.equals(key)) { e.value = value; return; }           // existing key: replace
            buckets[i] = new Entry(key, value, buckets[i]);                   // new key: front of the chain
            if (++size > buckets.length * 3 / 4) resize();                    // load factor 0.75
        }

        Integer get(String key) {
            for (Entry e = buckets[index(key, buckets.length)]; e != null; e = e.next)
                if (e.key.equals(key)) return e.value;
            return null;
        }

        private void resize() {                                               // rehash every entry
            Entry[] old = buckets;
            buckets = new Entry[old.length * 2];
            for (Entry head : old)
                for (Entry e = head; e != null; e = e.next) {
                    int i = index(e.key, buckets.length);
                    buckets[i] = new Entry(e.key, e.value, buckets[i]);
                }
            System.out.println("  resized to " + buckets.length + " buckets");
        }
    }

    public static void main(String[] args) {
        ChainedHashTable t = new ChainedHashTable();
        String[] fruits = {"apple", "banana", "cherry", "date", "elder", "fig", "grape"};
        for (int i = 0; i < fruits.length; i++) t.put(fruits[i], i * 2 + 3);
        t.put("apple", 4);
        System.out.println(t.get("apple") + " " + t.get("fig") + " " + t.get("kiwi") + " size=" + t.size);
    }
}

Output

  resized to 8 buckets
  resized to 16 buckets
4 13 null size=7

Trie for prefix search and autocomplete

A trie stores words character by character, so words with a common prefix share nodes. Lookup and prefix search take O(length of the word), independent of how many words are stored.

import java.util.ArrayList;
import java.util.List;

public class Main {
    // A trie (prefix tree) for lowercase words
    static class Trie {
        private static class Node {
            final Node[] next = new Node[26];
            boolean word;                                   // does a word end here?
        }

        private final Node root = new Node();

        void insert(String w) {
            Node n = root;
            for (char c : w.toCharArray()) {
                int i = c - 'a';
                if (n.next[i] == null) n.next[i] = new Node();
                n = n.next[i];
            }
            n.word = true;
        }

        private Node find(String prefix) {
            Node n = root;
            for (char c : prefix.toCharArray()) {
                n = n.next[c - 'a'];
                if (n == null) return null;
            }
            return n;
        }

        boolean contains(String w) { Node n = find(w); return n != null && n.word; }

        List<String> startsWith(String prefix) {            // every word under the prefix, in a-z order
            List<String> out = new ArrayList<>();
            Node n = find(prefix);
            if (n != null) collect(n, new StringBuilder(prefix), out);
            return out;
        }

        private void collect(Node n, StringBuilder sb, List<String> out) {
            if (n.word) out.add(sb.toString());
            for (int i = 0; i < 26; i++)
                if (n.next[i] != null) {
                    sb.append((char) ('a' + i));
                    collect(n.next[i], sb, out);
                    sb.deleteCharAt(sb.length() - 1);       // backtrack
                }
        }
    }

    public static void main(String[] args) {
        Trie t = new Trie();
        for (String w : new String[]{"java", "javac", "javadoc", "jar", "jvm", "lambda", "list"}) t.insert(w);
        System.out.println(t.contains("java") + " " + t.contains("jav") + " " + t.contains("jvm"));
        System.out.println(t.startsWith("jav") + " " + t.startsWith("l") + " " + t.startsWith("x"));
    }
}

Output

true false true
[java, javac, javadoc] [lambda, list] []

Linked-list pointer patterns

// Middle node: fast moves 2, slow moves 1
Node slow = head, fast = head;
while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }

// Cycle detection (Floyd): the two pointers meet only if there is a loop
boolean hasCycle(Node head) {
    for (Node s = head, f = head; f != null && f.next != null; ) {
        s = s.next; f = f.next.next;
        if (s == f) return true;
    }
    return false;
}

// Dummy head: no special case for removing/inserting at the front
Node dummy = new Node(0, head), cur = dummy;
while (cur.next != null) { if (cur.next.val == target) cur.next = cur.next.next; else cur = cur.next; }
head = dummy.next;

Monotonic stack and deque patterns

// Next greater element: keep a stack of indexes whose answer is still unknown
int[] next = new int[a.length];
Arrays.fill(next, -1);
Deque<Integer> st = new ArrayDeque<>();
for (int i = 0; i < a.length; i++) {
    while (!st.isEmpty() && a[st.peek()] < a[i]) next[st.pop()] = a[i];
    st.push(i);
}

// Sliding-window maximum: the deque holds indexes in decreasing value order
Deque<Integer> dq = new ArrayDeque<>();
for (int i = 0; i < a.length; i++) {
    if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();       // left the window
    while (!dq.isEmpty() && a[dq.peekLast()] <= a[i]) dq.pollLast();    // smaller values are useless
    dq.offerLast(i);
    if (i >= k - 1) result.add(a[dq.peekFirst()]);
}

Data structure checklist

  • List the operations you need and how often; pick the structure that makes the frequent ones cheap.
  • Prefer ArrayList, ArrayDeque, HashMap and PriorityQueue from the JDK in production code.
  • Make node classes private static nested classes.
  • Keep a size field instead of counting nodes every time.
  • Use a dummy head node to simplify linked-list edge cases.
  • Always keep a visited set when traversing graphs.
  • Test empty, single-element and duplicate-key cases.

Ready to test your Programming?

Timed online tests with instant scores and explanations.

About this section

About Java Programming

Java is one of the most used languages in the world – for enterprise software, Android apps, banking systems and backend services. This section covers core Java from syntax and data types to OOP, strings, arrays, exceptions, collections and multithreading, with clear explanations and practice questions for every topic.

Why it matters

  • Java is the main language in service-company placement tests and many product companies
  • OOP, String, collections and exception questions appear in nearly every Java interview
  • Strong core Java is the base for Spring Boot, Android and backend development
  • Java questions are common in university exams and certification tests

Who it is for

  • School students (Class 11–12 / ICSE computer applications) learning Java
  • College students (B.Tech, BCA, MCA) preparing for exams, labs and projects
  • Freshers preparing for placements, Java developer roles and technical interviews
  • Developers revising core Java before an interview

What every topic gives you

  • Study material in five tabs: concepts with runnable examples, coding techniques, programs, interview questions and a cheat sheet
  • MCQs that check your understanding of every concept
  • "Predict the output" puzzles – the trickiest part of written tests
  • "Find the error" programs that train you to spot bugs quickly
  • Complete programs with solutions and real output, verified on a compiler

Asked in

  • Campus placements
  • Java developer interviews
  • Service company tests
  • University exams
  • Certification exams
  • Government IT exams

How to use this section

  1. Read the study material of a topic and run the examples yourself.
  2. Practise the four exercises – MCQs, output, errors, programs – and read every explanation.
  3. Test yourself with the timed online test, then revise the topics you got wrong.

Search LearnFrenzy

Esc

Quick links