Java and Python Implementation Foundations

Introduction

Data structures and algorithms become useful only when they can be represented accurately in a programming language. Java and Python support the same fundamental abstractions—arrays, lists, stacks, queues, maps, sets, trees, and graphs—but express them differently. Java emphasizes explicit types, class contracts, interfaces, and predictable object-oriented structure. Python emphasizes flexibility, concise syntax, protocols, and dynamic typing.

These differences affect how a programmer designs, implements, tests, and evaluates a data structure. A linked list, for example, requires references in both languages, but Java normally expresses the node type through a class with declared fields, whereas Python uses object attributes and often relies on conventions or type hints. The underlying algorithm may be identical, while memory management, equality, error detection, and API design differ.

This chapter establishes the implementation foundations required for later study of linear and nonlinear data structures. It focuses on classes, interfaces, generics, arrays, collections, sequences, iterators, type hints, references, mutability, equality, memory management, and language-specific trade-offs.

Learning Objectives

By the end of this chapter, you should be able to:

1. Explain how Java and Python represent objects, references, and collections.
2. Implement simple data structures using Java classes, interfaces, generics, arrays, and collection types.
3. Implement equivalent structures in Python using classes, sequences, iterators, and type hints.
4. Distinguish identity, equality, mutability, and assignment in both languages.
5. Describe the role of automatic memory management and garbage collection.
6. Select suitable language features for reliable and maintainable data-structure implementations.
7. Compare Java and Python in terms of safety, performance, flexibility, readability, and development effort.

1. Abstraction and Data-Structure Interfaces

A data structure has both a representation and a set of permitted operations. The representation describes how data is stored; the interface describes what clients may do with it. For example, a stack may support push, pop, peek, and isEmpty, without exposing whether it is implemented with an array or linked nodes.

This separation is an example of abstraction and encapsulation. Encapsulation restricts direct access to internal state so that an implementation can change without forcing changes in client code. A well-designed data structure should preserve its invariants. A stack invariant, for instance, is that removal occurs only from the most recently inserted element.

Java makes interfaces explicit through the interface construct. Python usually expresses interfaces through duck typing, abstract base classes, or protocols. In duck typing, an object is suitable if it provides the operations required by the client, regardless of its declared class.

A Java interface

public interface Stack<E> {
    void push(E item);
    E pop();
    E peek();
    boolean isEmpty();
    int size();
}

The type parameter E means that the stack can store any reference type selected by the client. The interface does not specify the internal representation.

A Python protocol-style interface

from typing import Protocol, TypeVar

T = TypeVar("T")

class Stack(Protocol[T]):
    def push(self, item: T) -> None: ...
    def pop(self) -> T: ...
    def peek(self) -> T: ...
    def is_empty(self) -> bool: ...
    def __len__(self) -> int: ...

Python type hints support documentation and static analysis, but ordinary Python execution does not enforce them automatically. A program can therefore violate the annotation unless a type checker, testing system, or runtime validation is used.

2. Java Foundations for Data Structures

2.1 Classes and object state

A Java class defines fields, constructors, and methods. Fields should normally be private, with public methods controlling valid operations.

public final class ArrayStack<E> implements Stack<E> {
    private Object[] elements;
    private int top;

    public ArrayStack(int capacity) {
        if (capacity < 1) {
            throw new IllegalArgumentException("capacity must be positive");
        }
        elements = new Object[capacity];
        top = 0;
    }

    @Override
    public void push(E item) {
        if (top == elements.length) {
            throw new IllegalStateException("stack is full");
        }
        elements[top++] = item;
    }

    @SuppressWarnings("unchecked")
    @Override
    public E pop() {
        if (isEmpty()) {
            throw new IllegalStateException("stack is empty");
        }
        E result = (E) elements[--top];
        elements[top] = null;
        return result;
    }

    @SuppressWarnings("unchecked")
    @Override
    public E peek() {
        if (isEmpty()) {
            throw new IllegalStateException("stack is empty");
        }
        return (E) elements[top - 1];
    }

    @Override
    public boolean isEmpty() {
        return top == 0;
    }

    @Override
    public int size() {
        return top;
    }
}

The assignment elements[top++] = item stores a reference to an object. It does not copy the object itself. Clearing the removed array position is good practice because it prevents the unused slot from retaining a reference to an object.

This implementation uses Object[] because Java does not permit direct creation of a generic array such as new E[capacity]. The cast is safe under the class invariant that only values of type E are inserted through push. An alternative implementation can use a collection such as ArrayList<E> and avoid this low-level issue.

2.2 Interfaces and polymorphism

A variable declared as an interface type can refer to any compatible implementation:

Stack<String> history = new ArrayStack<>(20);
history.push("Home");
history.push("Search");
System.out.println(history.pop());

The client depends on the Stack contract rather than ArrayStack. This is polymorphism: the same interface can be used with different concrete implementations.

2.3 Generics and type safety

Generics allow a class or method to operate over a type parameter while preserving compile-time checking.

public static <T> void swap(T[] values, int i, int j) {
    T temporary = values[i];
    values[i] = values[j];
    values[j] = temporary;
}

The compiler checks that the array elements and temporary variable have compatible types. Java generics primarily apply to reference types, so primitive values use wrapper classes such as Integer, Double, and Boolean. Automatic boxing and unboxing convert between primitives and wrappers, but repeated boxing can create overhead.

Generics are invariant. A List<Integer> is not a subtype of List<Number>, even though Integer is a subtype of Number. This prevents unsafe insertion of a Double into a list intended to contain only integers. Wildcards express controlled flexibility:

List<? extends Number> readings;   // can read Number values
List<? super Integer> targets;     // can safely add Integer values

The practical rule is often summarized as “producer extends, consumer super.” A producer supplies values and is commonly declared with extends; a consumer receives values and is commonly declared with super.

2.4 Arrays and collections

Java arrays have fixed length and indexed access. If an array has length n, valid indexes are from 0 through n − 1. Access outside this range raises ArrayIndexOutOfBoundsException.

The Java Collections Framework provides reusable abstractions:

Programmers should usually declare variables using interfaces and instantiate concrete implementations only where necessary:

List<String> names = new ArrayList<>();
Map<String, Integer> frequencies = new HashMap<>();
Deque<Integer> work = new ArrayDeque<>();

ArrayList provides efficient indexed access and amortized efficient appending. LinkedList supports linked-node operations but is often a poorer choice for general-purpose indexed lists because traversal to an index is linear. HashMap and HashSet rely on hashing and require correctly implemented equals and hashCode methods.

3. Python Foundations for Data Structures

3.1 Classes and attributes

Python classes create objects whose attributes can be changed unless the design prevents or discourages such changes.

from typing import Generic, TypeVar

T = TypeVar("T")

class ArrayStack(Generic[T]):
    def __init__(self, capacity: int) -> None:
        if capacity < 1:
            raise ValueError("capacity must be positive")
        self._items: list[T] = []
        self._capacity = capacity

    def push(self, item: T) -> None:
        if len(self._items) == self._capacity:
            raise OverflowError("stack is full")
        self._items.append(item)

    def pop(self) -> T:
        if not self._items:
            raise IndexError("stack is empty")
        return self._items.pop()

    def peek(self) -> T:
        if not self._items:
            raise IndexError("stack is empty")
        return self._items[-1]

    def is_empty(self) -> bool:
        return len(self._items) == 0

    def __len__(self) -> int:
        return len(self._items)

The leading underscore communicates that _items is an implementation detail, but it is not a strict access restriction. Python relies substantially on programmer discipline and documented conventions.

Python’s built-in list is a dynamic array. Appending is usually efficient because capacity is increased in stages, although an individual resize may require copying references. Inserting or deleting near the beginning generally requires shifting many elements. For queue operations at both ends, collections.deque is preferable to list.

3.2 Sequences, mappings, and sets

Python provides several built-in collection categories:

• list: mutable ordered sequence.
• tuple: immutable ordered sequence.
• str: immutable sequence of Unicode text.
• dict: mutable mapping from keys to values.
• set: mutable collection of unique hashable elements.
• collections.deque: double-ended queue.

Python’s sequence protocol includes operations such as indexing, slicing, iteration, and membership testing. A custom class can participate in these protocols by implementing methods such as __len__, __getitem__, and __iter__.

3.3 Iterators and generators

An iterable can produce an iterator. An iterator maintains traversal state and provides a __next__ method that raises StopIteration when exhausted.

class Countdown:
    def __init__(self, start: int) -> None:
        self.current = start

    def __iter__(self):
        return self

    def __next__(self) -> int:
        if self.current == 0:
            raise StopIteration
        value = self.current
        self.current -= 1
        return value

A generator provides the same idea more concisely:

def countdown(start: int):
    for value in range(start, 0, -1):
        yield value

Generators are lazy: values are produced when requested rather than all being stored immediately. This can reduce memory use when processing large streams. However, a generator is generally single-use and does not provide random access.

3.4 Type hints and generic design

Modern Python supports annotations such as list[int], dict[str, float], and generic classes. Type hints improve editor support, documentation, and static checking with tools such as mypy or pyright. They do not, by themselves, make Python statically typed or prevent all runtime errors.

Python’s type system supports structural ideas through Protocol. This allows a function to accept any object with the required operations, which resembles duck typing while retaining analyzable contracts.

4. References, Identity, Equality, and Assignment

A variable in both languages commonly stores a reference to an object rather than the object’s complete contents. Consider two variables referring to one mutable list:

first = [10, 20]
second = first
second.append(30)

Both names refer to the same list, so first becomes [10, 20, 30]. The assignment copied the reference, not the list.

Java behaves similarly for objects:

List<Integer> first = new ArrayList<>();
first.add(10);
List<Integer> second = first;
second.add(20);

first and second refer to the same ArrayList object. Primitive variables such as int hold values directly, whereas object variables hold references. Python uses objects for all values, although implementation details may optimize some immutable values.

Identity versus equality

Identity asks whether two references designate the same object. Equality asks whether two objects represent equivalent values.

In Python, identity is tested with is, while value equality is tested with ==:

a = [1, 2]
b = [1, 2]
c = a

# a == b is True
# a is b is False
# a is c is True

In Java, == compares primitive values but compares reference identity for objects. The .equals() method is used for logical equality:

String a = new String("data");
String b = new String("data");
// a == b is usually false
// a.equals(b) is true

A Java class that overrides equals should normally also override hashCode. Equal objects must produce equal hash codes; otherwise hash-based collections may behave incorrectly. Python objects used as dictionary keys or set members must be hashable. Mutable objects whose equality-relevant state changes should generally not be used as keys.

5. Mutability and Immutability

A mutable object can change after creation; an immutable object cannot. Java String, Python str, Python tuple, and Java wrapper objects are examples of commonly used immutable types. Java collections such as ArrayList are mutable, as are Python lists, dictionaries, and sets.

Immutability offers several advantages:

• state cannot be changed unexpectedly through an alias;
• objects are easier to share safely;
• hash-based use is safer when hash-relevant state cannot change;
• concurrent reasoning is simpler.

Mutability is useful when algorithms need in-place updates. A sorting algorithm may rearrange an array to avoid allocating another collection, but this creates side effects that should be documented.

A shallow copy duplicates the outer collection while retaining references to contained objects. A deep copy recursively duplicates nested objects where supported. Neither should be used casually: copying can be expensive, and some objects should remain shared.

6. Memory Management and Resource Lifetime

Both languages automatically reclaim memory that is no longer reachable by the program. This removes the need for explicit deallocation of ordinary objects, but it does not eliminate resource-management responsibilities.

Java uses garbage collection based on reachability. An object becomes eligible for collection when no live reference path reaches it. Collection timing is not guaranteed, so programs must not rely on a destructor-like event for closing files, sockets, or database connections.

Python implementations commonly use reference counting together with a cyclic garbage collector. In CPython, an object whose reference count reaches zero is usually reclaimed immediately, but this is an implementation detail rather than a universal language guarantee. Cycles may require cyclic garbage collection.

External resources must be closed explicitly. Java uses try-with-resources:

try (var reader = Files.newBufferedReader(path)) {
    // use reader
}

Python uses a context manager:

with open("records.txt", encoding="utf-8") as file:
    data = file.read()

The key distinction is between memory lifetime, managed automatically, and resource lifetime, which should be managed deterministically.

7. Complexity and Implementation Trade-offs

The choice of representation affects time and space complexity. For a dynamic array with n elements, indexing is typically Θ(1), while inserting at the beginning is Θ(n) because elements may need to shift. A linked list can insert at a known node in Θ(1), but locating that node by position is Θ(n). Hash-table lookup is expected Θ(1) under suitable hashing and load assumptions, but worst-case behavior can be Θ(n).

These are asymptotic descriptions, not guarantees of equal real-world speed. Constant factors, memory locality, allocation costs, interpreter overhead, and workload patterns also matter.

“Amortized Θ(1)” means that the average cost per operation over a sufficiently long sequence is constant, even though occasional resizing costs Θ(n). The statement assumes a standard capacity-growth strategy and does not mean every individual append is constant time.

Java often offers stronger compile-time guarantees and can deliver high throughput after just-in-time compilation. Python generally offers shorter code and rapid experimentation, but interpreted execution and dynamic dispatch can increase runtime cost. Python libraries implemented in optimized native code can nevertheless provide excellent performance for specialized workloads.

8. An Applied Case: Choosing a Log-Processing Structure

Background

A small monitoring service receives application events. Each event contains a timestamp, service name, severity, and message. The service must retain recent events, count events by severity, and process urgent events first.

Problem

An initial implementation stores every event in a Python list and repeatedly scans the list to find urgent events. As the event volume grows, processing becomes slow. A Java version uses a linked list for all tasks, even though most operations are indexed reads and appends.

Analysis

The requirements are different operations, so one structure is unlikely to be ideal for all of them:

• recent chronological events require an ordered sequence;
• severity counts require a mapping from severity to integer count;
• urgent processing requires a priority queue;
• bounded retention requires removal from the oldest end.

Approach

In Python, a deque can maintain recent events, a dict[str, int] can maintain counts, and heapq can implement a priority queue. In Java, ArrayDeque<Event> can maintain the recent window, HashMap<String, Integer> can maintain counts, and PriorityQueue<Event> can process urgent events.

The design should define how priority is compared. For example, a lower numeric priority value may mean greater urgency. Timestamps should use a consistent time zone or an explicitly documented instant representation. Events should be treated as immutable records where possible, preventing their ordering or identity from changing after insertion into a priority queue.

Outcome

The revised design avoids repeated full scans and expresses each requirement through an appropriate abstraction. Memory is bounded by removing events older than the retention window. The Java implementation gains compile-time checking of event fields and collection element types. The Python implementation is shorter and easier to adapt, while type hints and tests provide additional confidence.

Learning points

1. Select structures according to operations, not habit.
2. Separate event storage, counting, and priority processing.
3. Document equality and ordering rules.
4. Bound memory deliberately in long-running services.
5. Use interfaces or protocols so implementations can be replaced during testing.

9. Best Practices and Limitations

Good implementation practice includes the following:

• program to interfaces in Java and protocols or documented protocols in Python;
• keep representation fields private or conventionally internal;
• validate constructor arguments and preserve invariants;
• use generics and type hints to communicate intended element types;
• distinguish equality from identity;
• avoid mutable keys in hash-based collections;
• choose ArrayDeque rather than Stack for ordinary Java stack or queue behavior;
• choose deque rather than repeatedly inserting at the front of a Python list;
• close external resources deterministically;
• measure performance with representative workloads rather than guessing;
• test boundary conditions such as empty structures, duplicate values, capacity limits, and invalid indexes.

Neither language automatically produces a correct data structure. Java’s compiler catches many type errors but cannot prove that an algorithm preserves its invariants. Python’s flexibility supports rapid development but can allow incorrect assumptions to survive until runtime. In both languages, contracts, tests, code review, and complexity analysis remain essential.

Security and governance also matter. Untrusted input should not be deserialized into arbitrary objects, collection sizes should be bounded where denial-of-service risks exist, and sensitive data should not be retained longer than necessary. Logging structures should avoid exposing credentials or personal information.

Chapter Summary

Java and Python provide rich but contrasting foundations for data-structure implementation. Java emphasizes declared classes, interfaces, generics, compile-time type checking, and explicit collection abstractions. Python emphasizes dynamic objects, protocols, built-in sequences, iterators, generators, and optional type hints.

In both languages, variables commonly refer to objects. Identity and equality are distinct concepts, and aliases to mutable objects can create observable side effects. Java uses == for primitive comparison and reference identity, while .equals() expresses object equality. Python uses is for identity and == for equality. Correct equality and hashing are essential for sets, maps, and dictionaries.

Arrays and dynamic arrays provide fast indexed access but may require linear-time shifting for insertion. Linked structures support local insertion efficiently but have weaker positional access. Hash-based structures offer expected constant-time lookup under appropriate assumptions. Memory is automatically reclaimed, but files, sockets, and other external resources require deterministic management.

Effective programmers select representations according to required operations, preserve invariants, document mutability and equality behavior, use type information appropriately, and test both normal and boundary cases. The same algorithm can be implemented in both languages, but language-specific trade-offs influence safety, expressiveness, performance, and maintenance.

Key Terms

Abstraction: Representation of essential behavior while hiding implementation details.

Alias: A second reference or name that designates the same object.

Array: A fixed-length indexed collection of elements.

Class: A definition from which objects are created.

Collection: An object used to group and manage multiple values.

Duck typing: Treating an object as suitable when it provides the required operations.

Encapsulation: Restricting direct access to representation and controlling state changes.

Equality: A relation indicating that two objects have equivalent values.

Garbage collection: Automatic reclamation of unreachable memory.

Generic: A parameterized type or class that operates over specified element types.

Identity: The property of being the same object in memory or object model.

Immutable: Unable to change state after creation.

Interface: A contract describing operations supported by an implementation.

Iterator: An object that produces elements successively and signals completion.

Mutable: Able to change state after creation.

Polymorphism: Use of one interface with objects of different concrete types.

Protocol: A set of operations an object is expected to support.

Reference: A value that designates an object.

Sequence: An ordered collection supporting operations such as indexing or iteration.

Type hint: Annotation communicating intended types, usually for tools and documentation.

Review Questions

Short Answer Questions

1. What is the difference between an interface and a concrete implementation?
2. Why should a Java class that overrides equals normally override hashCode?
3. Distinguish identity from equality in Python.
4. Why is deque commonly preferred to list for queue operations at both ends?
5. What is the difference between memory management and external-resource management?

Long Answer Questions

1. Compare Java generics and Python type hints in terms of safety, enforcement, and practical use.
2. Explain the advantages and disadvantages of mutable and immutable objects in data-structure design.
3. Compare arrays, dynamic arrays, linked structures, and hash tables for representative operations.
4. Describe how aliases can produce unexpected changes in Java and Python programs.
5. Explain how interfaces, protocols, encapsulation, and invariants contribute to maintainable data structures.

Analytical / Application Questions

1. Design suitable Java and Python structures for a browser history that supports visiting pages, moving backward and forward, and discarding forward history after a new visit. Justify each choice.
2. A program repeatedly removes items from the front of a Python list containing one million elements. Explain the performance problem and propose two alternatives.
3. An object used as a key in a hash map changes one of the fields used by its equality and hash calculations. Explain the resulting risk and recommend a safer design.

Multiple Choice Questions with Answers

Question 1

Which Java abstraction allows a client to use a stack without depending on its internal representation?

A. An interface

B. A primitive variable

C. A package declaration

D. A comment

Correct Answer: A. An interface

Question 2

Which Python operator tests object identity?

A. ==

B. is

C. equals

D. same

Correct Answer: B. is

Question 3

What is the typical complexity of indexed access in a Java ArrayList or Python list?

A. Θ(1)

B. Θ(log n)

C. Θ(n)

D. Θ(n²)

Correct Answer: A. Θ(1)

Question 4

Why should mutable objects generally not be used as hash-map keys?

A. They cannot be stored in memory

B. Their equality or hash value may change after insertion

C. They always contain duplicate values

D. They cannot be compared

Correct Answer: B. Their equality or hash value may change after insertion

Question 5

Which Python collection is generally appropriate for efficient insertion and removal at both ends?

A. list

B. tuple

C. deque

D. str

Correct Answer: C. deque

Question 6

What does a Java generic type parameter such as E primarily provide?

A. Compile-time information about the element type

B. Automatic parallel execution

C. Guaranteed constant-time operations

D. Automatic serialization

Correct Answer: A. Compile-time information about the element type

Question 7

What happens when a Python generator uses yield?

A. It immediately creates every result in a list

B. It produces values lazily during iteration

C. It converts values into dictionary keys

D. It prevents iteration

Correct Answer: B. It produces values lazily during iteration

Question 8

If two Java variables refer to the same mutable object, changing the object through one variable will usually:

A. Change the object observed through the other variable

B. Create an automatic deep copy

C. Cause a compile-time error

D. Make both variables null

Correct Answer: A. Change the object observed through the other variable

Question 9

Which Java collection is designed for key–value associations?

A. Map

B. Deque

C. Queue

D. Stack

Correct Answer: A. Map

Question 10

What does amortized Θ(1) append mean for a dynamic array?

A. Every append is guaranteed to take exactly one step

B. The average cost over a long sequence of appends is constant

C. Appending always requires a full scan

D. The array can never resize

Correct Answer: B. The average cost over a long sequence of appends is constant