# Unit 1: Data structures in Java (CS609) ## Linked List - A **linked list** is a linear collection of nodes, each holding data and a reference to the next node; non-contiguous memory, dynamic size. - Types: **singly**, **doubly** (prev and next), **circular**. - Java class `java.util.LinkedList` implements `List` and `Deque`; methods `add()`, `addFirst()`, `addLast()`, `remove()`, `get()`, `size()`. - Insertion/deletion at ends O(1); random access O(n). ``` LinkedList l = new LinkedList<>(); l.add("A"); l.addFirst("B"); ``` - vs `ArrayList`: ArrayList has O(1) random access but costly middle insertion. ## Stacks - **LIFO** structure: `push`, `pop`, `peek`, `isEmpty`. - Java: `Stack` class (legacy, synchronized) or preferably `Deque` via `ArrayDeque`. - Uses: expression evaluation, recursion, undo, parenthesis matching. ## Queues - **FIFO** structure: `offer/add`, `poll/remove`, `peek`. - `Queue` interface implemented by `LinkedList`, `ArrayDeque`, **`PriorityQueue`** (heap-ordered by priority). - `Deque` allows insertion and removal at both ends. - Uses: scheduling, buffering, BFS. ## Sets - Collection of **unique** elements; `Set` interface. | Implementation | Order | Notes | |---|---|---| | `HashSet` | Unordered | Hash table, O(1) average | | `LinkedHashSet` | Insertion order | Hash table plus linked list | | `TreeSet` | Sorted | Red-black tree, O(log n) | - Uses `equals()` and `hashCode()` to detect duplicates. ## Maps - Key-value pairs with unique keys; `Map` interface (not part of `Collection`). - `HashMap` (unordered, allows one null key), `LinkedHashMap` (insertion order), `TreeMap` (sorted by key), `Hashtable` (legacy, synchronized). - Methods: `put()`, `get()`, `containsKey()`, `remove()`, `keySet()`, `values()`, `entrySet()`. ``` Map m = new HashMap<>(); m.put("A", 1); ``` - Iterating with `for (Map.Entry e : m.entrySet())`. **[Figure: Java Collections hierarchy]** `Iterable` -> `Collection` -> `List`, `Set`, `Queue`, with `Map` as a separate hierarchy. ## Generics - Allow classes and methods to operate on **type parameters**, giving compile-time type safety and removing casts. - **Generic class**: ``` class Box { T val; void set(T v){val=v;} T get(){return val;} } Box b = new Box<>(); ``` - **Type parameters** conventions: `T` (type), `E` (element), `K` (key), `V` (value), `N` (number). - **Implementing generic types**: interfaces such as `Comparable`, bounded types ``, wildcards ``, ``, ``. - **Generic methods**: `public static void print(T x)`. - **Type erasure**: generic type information is removed at runtime; primitives cannot be type arguments. ## Wrapper Classes - Object versions of primitives: `Integer`, `Double`, `Character`, `Boolean`, `Long`, `Float`, `Short`, `Byte`. - Required because collections hold objects only. - **Autoboxing** (int -> Integer) and **unboxing** automatic; methods `parseInt()`, `valueOf()`, `intValue()`. ## Concept of Serialization - **Serialization** converts an object's state into a byte stream for storage or transmission; **deserialization** rebuilds the object. - Class implements marker interface `java.io.Serializable`; use `ObjectOutputStream.writeObject()` and `ObjectInputStream.readObject()`. - `transient` fields are skipped; `static` fields are not serialized; `serialVersionUID` checks version compatibility. - Hadoop uses its own `Writable` instead because Java serialization is heavy. ## Likely Exam Questions 1. Differentiate ArrayList and LinkedList. (2 marks) 2. Compare HashSet, LinkedHashSet and TreeSet. 3. Explain Map implementations in Java with a code example. 4. What are generics? Write a generic class and a generic method. 5. What are wrapper classes? Explain autoboxing and unboxing. (2 marks) 6. Explain serialization in Java and the role of `transient`.