Programming Practices (CS-406) Unit 2 Notes

How unit 2 is examined

This unit covers data structures, wrapper classes, memory allocation, generics, the Collections Framework, its algorithms, Stack, PriorityQueue and Map; no topic was asked in the supplied papers, so learn each definition and its key points.

Data Structures: Introduction

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. A data structure is a way of organising data in memory so that it can be stored, accessed and modified efficiently.

Key points.

Java offers arrays for fixed-size storage and the java.util Collections Framework for dynamic structures.
Data structures are linear (array, list, stack, queue) or non-linear (tree, graph, map).
Arrays have a fixed size, so growing data needs a dynamic structure such as ArrayList.
Choose a structure by the operations needed: fast indexing, fast insertion, ordering or lookup by key.

Type-Wrapper Classes for Primitive Types

Definition. A wrapper class is an object type that wraps one primitive value, for example Integer for int, so the value can be used where an object is required.

Key points.

The eight wrappers are Byte, Short, Integer, Long, Float, Double, Character and Boolean.
Collections store only objects, so List<Integer> needs wrappers instead of int.
Autoboxing converts a primitive to its wrapper automatically, and unboxing converts it back.
Methods such as Integer.parseInt("25") and Integer.valueOf(25) convert strings and numbers.
Wrapper objects are immutable, and unboxing a null wrapper throws NullPointerException.

Dynamic Memory Allocation

Definition. Dynamic memory allocation is the creation of objects at run time with new, in heap memory, whose size need not be known at compile time.

Key points.

new allocates an object on the heap, and the reference to it is held in a variable.
Java has no free or delete; the garbage collector reclaims objects that no reference can reach.
System.gc() only requests a collection and does not force it.
The finalize() method was called before collection but is deprecated.
Collections such as ArrayList allocate dynamically and grow as elements are added.

Linked List, Stack, Queues, Trees

Definition. These are the basic linked and linear structures: a linked list chains nodes by references, a stack is last-in first-out, a queue is first-in first-out, and a tree is a hierarchy of nodes.

Key points.

A linked list node holds data and a reference to the next node, so insertion and deletion need no shifting.
A stack adds and removes at one end, the top, using push and pop.
A queue adds at the rear and removes from the front, using enqueue and dequeue.
A tree has a root and child nodes; in a binary tree each node has at most two children.
Java gives LinkedList, Stack, Queue and TreeSet or TreeMap ready-made.

Generics: Introduction, Overloading Generic Methods, Generic Classes

Definition. Generics let a class or method work on a type given as a parameter, such as <T>, giving compile-time type safety without casting.

Key points.

A generic class is written class Box<T> { T val; } and used as Box<String>.
A generic method declares its own parameter before the return type, as in static <E> void print(E[] a).
Generic methods can be overloaded with other generic or non-generic methods of the same name but different parameters; the most specific one is chosen.
Type arguments must be reference types, so Box<int> is illegal and Box<Integer> is used.
Type erasure removes the type parameter at run time, and <? extends Number> is a bounded wildcard.

Collections: Interface Collection and Class Collections, Lists, Array List and Iterator, Linked List, Vector

Definition. The Collections Framework is a set of interfaces and classes in java.util for storing groups of objects; Collection is the root interface and Collections is a utility class of static methods.

Key points.

A List is an ordered collection that allows duplicates and access by index.
ArrayList is backed by a resizable array, so it is fast for random access but slow for insertion in the middle.
LinkedList is a doubly linked list, so it is fast for insertion and removal at the ends but slow for index access.
Vector is like ArrayList but synchronized, and it doubles its capacity when full.
An Iterator visits elements with hasNext(), next() and remove(); ListIterator also goes backwards.

Collections Algorithms: Algorithm sorts, Algorithm shuffle, Algorithms reverse, fill, copy, max and min Algorithm binary Search, Algorithms add All

Definition. Collections algorithms are static methods of the Collections class that operate on lists and collections.

Key points.

sort(list) sorts in ascending natural order, or by a Comparator if one is given.
shuffle(list) randomly permutes the elements, and reverse(list) reverses their order.
fill(list, x) overwrites every element with x, and copy(dest, src) needs dest to be at least as long as src.
max(c) and min(c) return the largest and smallest elements.
binarySearch(list, key) needs a sorted list and returns the index, or a negative value if absent.
addAll(c, e1, e2, ...) adds the given elements to a collection.

Stack Class of Package java. Util

Definition. java.util.Stack is a last-in first-out class that extends Vector.

Key points.

push(x) places x on top, and pop() removes and returns the top element.
peek() returns the top element without removing it.
empty() tests for an empty stack, and search(x) gives the 1-based position from the top.
pop() and peek() on an empty stack throw EmptyStackException.
Because it extends Vector it is synchronized; ArrayDeque is the modern alternative.

Class Priority Queue and Interface Queue

Definition. Queue is a first-in first-out interface, and PriorityQueue is a Queue class that orders elements by priority instead of arrival.

Key points.

Queue offers offer() to add, poll() to remove and peek() to read the head, returning null when empty.
add(), remove() and element() do the same jobs but throw an exception when the queue is empty or full.
PriorityQueue is a heap, so the head is the smallest element by natural order or by a given Comparator.
It does not allow null and its iteration order is not sorted.
It is not thread-safe.

Maps, Properties Class, Un-modifiable Collections

Definition. A Map stores key-value pairs with unique keys; Properties is a Hashtable of String keys and values, and unmodifiable collections are read-only views.

Key points.

HashMap is unordered and allows one null key, TreeMap keeps keys sorted, and LinkedHashMap keeps insertion order.
Main methods are put, get, remove, containsKey, keySet and entrySet.
Properties uses getProperty(key), setProperty(key, value), load() and store() to read and write configuration files.
Collections.unmodifiableList(list), and the matching Set and Map versions, return a read-only view.
Any change to an unmodifiable collection throws UnsupportedOperationException.

Last-minute revision

A wrapper class wraps a primitive as an object; autoboxing and unboxing convert automatically.
Java frees memory through the garbage collector; there is no free.
Stack is LIFO and Queue is FIFO.
Generics give compile-time type safety and use reference types only.
ArrayList is array-backed, LinkedList is doubly linked, and Vector is synchronized.
Collection is the root interface and Collections is the utility class.
binarySearch needs a sorted list.
Stack methods are push, pop, peek, empty and search.
PriorityQueue is a min-heap by default.
HashMap allows one null key; Properties holds String pairs.
Unmodifiable collections throw UnsupportedOperationException on change.

Memory hooks

SPFR: Sort, Permute (shuffle), Fill, Reverse.
Stack is a plate pile: the last plate on is the first off.
Queue is a ticket line; PriorityQueue is an emergency room where the most urgent goes first.
Vector is ArrayList wearing a lock (synchronized).

Coverage checklist

Data Structures: Introduction: definition, linear and non-linear kinds. No past questions.
Type-Wrapper Classes for Primitive Types: wrappers, autoboxing. No past questions.
Dynamic Memory Allocation: new, heap, garbage collection. No past questions.
Linked List, Stack, Queues, Trees: node, LIFO, FIFO, hierarchy. No past questions.
Generics: Introduction, Overloading Generic Methods, Generic Classes: type parameter, generic method, generic class. No past questions.
Collections: Interface Collection and Class Collections, Lists, Array List and Iterator, Linked List, Vector: List classes, Iterator. No past questions.
Collections Algorithms: Algorithm sorts, Algorithm shuffle, Algorithms reverse, fill, copy, max and min Algorithm binary Search, Algorithms add All: all nine methods. No past questions.
Stack Class of Package java. Util: push, pop, peek. No past questions.
Class Priority Queue and Interface Queue: offer, poll, heap order. No past questions.
Maps, Properties Class, Un-modifiable Collections: Map types, Properties, read-only views. No past questions.

Account

Programming Practices (CS-406) - Unit 2 Short Notes

How unit 2 is examined

Data Structures: Introduction

Type-Wrapper Classes for Primitive Types

Dynamic Memory Allocation

Linked List, Stack, Queues, Trees

Generics: Introduction, Overloading Generic Methods, Generic Classes

Collections: Interface Collection and Class Collections, Lists, Array List and Iterator, Linked List, Vector

Collections Algorithms: Algorithm sorts, Algorithm shuffle, Algorithms reverse, fill, copy, max and min Algorithm binary Search, Algorithms add All

Stack Class of Package java. Util

Class Priority Queue and Interface Queue

Maps, Properties Class, Un-modifiable Collections

Last-minute revision

Memory hooks

Coverage checklist