Design Patterns & Collections

Overview

This lecture introduces design patterns in object-oriented programming, focusing on collections and iterators, and compares ArrayList and LinkedList implementations in Java.

Design Patterns: Purpose and Format

• Design patterns provide proven solutions to recurring design problems in software development.
• They enhance flexibility, adaptability, and maintainability of code.
• Each pattern has a name, a problem context, and a solution prescription.
• Patterns are language-agnostic and apply across programming languages like Java, C++, Python, etc.

Java Collections Overview

• Java offers several container classes: ArrayList, LinkedList, Vector, HashSet, StringBuffer, etc.
• The Collection interface unifies operations like isEmpty, contains, add, remove, and size.
• Collections class is a utility with static algorithms (sort, shuffle, etc.), distinct from the Collection interface.

Collection Hierarchy & Types

• Core interfaces include Collection, Set, List, Queue, and their subtypes like SortedSet and NavigableSet.
• List: Elements are ordered and can have duplicates.
• Set: No duplicates and usually unordered; some (like SortedSet) can be sorted.

ArrayList Implementation Details

• Stores elements in a resizable array, offering fast access (O(1)) but slow insert/delete (O(N)).
• Grows array by copying elements to a new, larger array when needed.
• Java’s standard ArrayList should always be preferred over custom implementations.

MyArrayList Methods Overview

• size(): Returns the number of elements.
• get(index): Retrieves element by index after boundary checking.
• add(element): Appends element, resizing if needed.
• add(index, element): Inserts element at index, shifting elements.
• remove(index): Deletes element by index, shifting elements down.

Iterator & Iterable Interfaces

• Iterator traverses a collection without exposing internal details.
• Methods: hasNext() checks for next element; next() retrieves it; remove() deletes last returned.
• Iterable interface provides factory method iterator(), so collections can be used in enhanced for-loops.

LinkedList Implementation Details

• Stores elements as nodes linked together; each node holds an element and reference to the next.
• Adding/removing at head or tail is fast (O(1)), but accessing or inserting elsewhere is slower (O(i)).
• Maintains head, tail references, and size.

MyLinkedList Methods Overview

• get(index): Traverses nodes from head to find element.
• add(element): Appends to tail; special handling if list is empty.
• add(index, element): Inserts at given position; O(1) for head/tail, O(index) otherwise.
• remove(index): Removes node at index; updates head/tail pointers accordingly.

Improving LinkedList Operations

• Iterator extensions (like ListIterator) allow efficient element handling and bidirectional traversal.

Key Terms & Definitions

• Design Pattern — General, reusable solution to a common software design problem.
• Collection (interface) — Java interface standardizing container operations.
• ArrayList — Dynamic array-backed list; fast access, slow inserts/removes at arbitrary positions.
• LinkedList — List of interconnected nodes; fast adds/removes at ends, slower random access.
• Iterator — Object for sequentially accessing collection elements.
• Iterable — Interface enabling a collection to be iterated with an iterator.

Action Items / Next Steps

• Review ItJPaDS 11 ed., Chapter 13.10 and 24.4 for class design guidelines and LinkedList remove details.
• Prepare for next lecture: Lambda expressions & recursive data structures.