UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 4.2 Free with a free account
Turning Data Definitions into Working Java Code
Data Structures and Algorithms · Chapter 4: Abstract Types, Exceptions, and Nested ClassesSection 4.2 · lesson 12 of 8711 min · free with a free account
Free preview
Create a free account to keep watching
It takes a minute and costs nothing. Your free account unlocks all of Chapter 1 and 3 more lessons of Data Structures and Algorithms.
Lesson complete
Earn the 3 college credits for Data Structures and Algorithms
Enrolling adds a quiz after each lesson, the graded work and the official transcript. Recommended for credit by NCCRS.
Next lesson: Anticipating and Recovering from Runtime Errors Gracefully →← Defining Data Behavior Without Implementation DetailsNext lesson: Anticipating and Recovering from Runtime Errors Gracefully →
In this lesson
Turn an ADT into a Java interface, generic implementations and tests.
- Translate each operation of a specification into a Java interface method signature
- Implement an interface with public methods and swap implementations behind it
- Use generic type parameters, wrapper types and bounds such as Comparable
- Write tests from the specification that judge every implementation alike
Free study notes
Get this lesson's notes by email
The key points and 4 practice questions with answers, in your inbox. One email, free.
One email. Unsubscribe in one click.
Transcript
Everything said in the video, section by section (1,566 words). Read along, or search it.
Opening Question
From Written Promise to Compiled Code
An abstract data type says what a structure promises, and nothing about how it's stored. A stack, for example: the item added last is the first one removed. But a promise written in words can't be compiled. So how does it become Java code that the compiler holds you to? And once someone writes an implementation, how do you know it really keeps the promise?
Method Signatures
Five Stack Operations as Signatures
For a stack, five operations are enough. Push puts an item on top. Pop removes the top item and gives it back. Peek gives back the top item and leaves it in place. Is empty and size report on the stack. Each operation becomes exactly one method signature. An operation that produces an answer gets a return type. One that only changes the structure returns void. And whatever it needs from the caller becomes a parameter. The letter T stands for the type of the items, whatever the stack holds. For now, pop and peek on an empty stack simply return null. Handling that properly is the job of exceptions, covered shortly.
Interface
A Contract for a Stack of Strings
An interface is a list of method signatures with no bodies. It's a contract: any type that implements it promises to supply every method. To keep the first version simple, here's the contract for a stack of strings only.
Implementation
A Stack Backed by an Array List
Here's one type that keeps it. List string stack implements string stack, and stores the items in an array list: a ready-made, growable list from Java's library. The field is private, so no code outside can see that storage choice. That hidden choice is exactly what the specification leaves open. The end of the list is the top. Pop removes the last item, and returns null on an empty stack, under the temporary rule. Interface methods are automatically public, so every implementing method must be declared public too. Leave the word out, and the compiler rejects it for weakening the access.
Demo
Pushing and Popping Through the Interface
The variable is declared with the interface type, string stack, while the object is made from the implementing type. Everything after that line talks only to the contract. Push a, b and c. Peek shows c without removing it, and pop removes it. Two items remain, and the next two pops give b, then a. Then the emptied stack reports true for is empty, and one more pop returns null, under the temporary rule.
Compile Error
A Class Missing Its Size Method
If an implementing type forgets a method, the compiler refuses to build it. This one has four of the five, and no size. Broken is not abstract, and does not override the abstract method size in string stack. The contract is enforced before anything runs.
Motivation
Why One Stack per Type Fails
That stack holds only strings. A stack of whole numbers would need an almost identical interface and class, with Integer in place of String, and a stack of decimals would need a third copy. Generics solve that. A generic type takes a type parameter, a placeholder in angle brackets, which is replaced by a real type when the type is used. Write the definition once, as stack of T. Then stack of String treats T as String everywhere, stack of Integer treats it as Integer, and so on.
Generics
Rewriting the Stack With a Type Parameter
Here's the interface rewritten with a type parameter. Every String that meant the item type has become T, and the name gained angle brackets with T. And the implementation changes the same way: list stack of T implements stack of T, with an array list of T inside. Nothing else changes.
Demo
Stacks of Words and Numbers
Now the same two definitions serve a stack of words and a stack of numbers. Run it: fig, thirty. On the left, stack of String states what the variable may hold, so words dot pop is known to be a String. On the right, the empty diamond lets the compiler fill in the type argument from the left. A type argument can't be a primitive like int, so you use its wrapper, Integer. Java converts between them automatically, which is why push ten, and adding two pops, just work. By convention, a type parameter is one capital letter: T for an ordinary type, E for an element, and K and V for a key and a value.
Compile-Time Safety
Three Mistakes Generics Catch
The payoff is that mistakes are caught before the program runs. Here are three of them. A stack of Integer refuses a String. And a primitive type argument is an unexpected type: Java requires a reference type, like Integer. And a stack of String is not a stack of Object, even though a String is an Object. Otherwise, code could push a number into a stack made for strings. Compile it, and javac reports all three, before anything runs. One more thing to know: Java checks type arguments while compiling, then erases them. At run time, every stack is the same kind of object. That's why generic code can't write new T.
Quick Check
Pushing an Int Onto a Double Stack
Quick check. A stack of Double. Line four pushes two point five. Line five pushes three. Line six pops into a double. Which line does javac reject, if any? Pause, and predict. It rejects line five. Three is an int, and Java will box an int into an Integer, not into a Double. Int cannot be converted to Double. Two point five is already a double, so line four boxes it into a Double. And line six unboxes the Double popped from the stack. Write three point zero, and it compiles.
Bounded Types
Generic Methods and Comparable Bounds
A single method can have its own type parameter, written before the return type. The compiler works out the type argument from the values passed in. First non null accepts any type. Larger has a stricter need: it must compare two values, and only some types know how. So its type parameter is bounded. T extends comparable of T means, any type that can compare itself with another T. The word extends is used here, even for an interface like Comparable. Run it: fallback, nine, and pear. One definition handled numbers and words, because both Integer and String compare themselves.
Compile Error
What Happens Without the Bound
The bound is also what makes the body legal. Remove it, and inside larger, Java no longer knows that a has a compare to method. Cannot find symbol: method compare to, in a variable of type T, where T extends Object. The bound protects callers too: asking for the larger of two plain Objects is refused, because plain objects have no natural order.
Second Implementation
A Linked Stack of Nodes
The interface says nothing about storage, so a second implementation can store the items completely differently. Linked stack keeps a chain of small node objects. Each node holds one item, and a reference to the next node. The top of the stack is the first node. Push makes a new node in front of the old top. Pop moves the top to the next node. And a count field keeps size up to date.
Swapping Implementations
One Drain Method, Two Stacks
Drain was written once, against the interface. It pops until the stack is empty, and joins what comes out. One stack is a list stack, the other a linked stack, each with x, y, z pushed. Run it: z y x, both times. Switching implementations means changing one word, list stack to linked stack, on the line that creates the object. Nothing else that uses the stack changes.
Testing From the Spec
One Check per Promise
Two implementations that look right aren't necessarily right. The specification is the judge, so tests are written from it: one check for every promise, and not from one implementation's details. A new stack holds nothing. Peek shows the top and changes nothing. Pop removes and returns the top. Items leave in reverse order. And an emptied stack is empty. Then the same checks run against every implementation, including a deliberately faulty one, whose pop removes the oldest item instead of the newest. That turns a stack into a queue.
Faulty Implementation
A Pop That Removes the Oldest
Here's the faulty one. Everything matches list stack, except one line: pop removes position zero, the oldest item.
Test Harness
Running Nine Checks on Every Stack
The harness takes any stack of Integer. Each check states the rule it tests, prints only failures, and a one-line summary closes each run. Run it. List stack and linked stack pass all nine. Front pop stack fails exactly the two checks about order, and the messages name the broken promise. It still passes the other seven, because a faulty implementation is usually wrong in one place only. That's why every rule needs its own check. And a pass shows only that your checks found no fault, so include the boundaries: the empty stack, one item, the last pop.
Quick Check
A Leaky Count After Pop
Quick check. Leaky is the linked stack, with one line missing: pop never decrements the count. Run through the same nine checks, how many does it pass? Nine, eight, or seven? Pause, and predict. It passes eight. Only, pop removes that item, fails: after one pop, size still says three. Order is right, and is empty is right, because they look at the nodes, not the count. One wrong line, one failed promise, and the message names it.
Key Takeaways
Interfaces, Generics and Spec Tests
To summarize. Each operation in a specification becomes one method signature in a Java interface, and an implementing type must supply every one, as public methods. Generics let one definition serve any item type. Type arguments are reference types, checked at compile time, and a bound like T extends comparable of T allows compare to. Several implementations can sit behind one interface, and swapping them changes one word. And tests written from the specification, one check per promise, judge every implementation alike.
About Data Structures and Algorithms at UPI Study
Data Structures and Algorithms (Computer Science 251) is a self-paced online course of 87 video lessons in 17 chapters, from Java and object-oriented design to arrays, linked lists, recursion, stacks and queues, trees, heaps, hash tables, sorting and graphs. It carries a NCCRS credit recommendation for 3 semester credits.
Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →
Compare: Discrete Math vs Data Structures and Algorithms · Intro to Java vs Data Structures and Algorithms
Why take it here
Why students take Data Structures and Algorithms with UPI Study
Where the credit goes
Universities that work with NCCRS
Data Structures and Algorithms carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Thomas Edison State UniversitySigned partner
University of the PeopleSigned partner
Charter Oak State CollegeSigned partner
Strayer UniversitySigned partner
Columbia Southern UniversitySigned partner
Indiana TechSigned partner
Penn StateWorks with NCCRS
Southern New Hampshire UniversityWorks with NCCRS
SUNYWorks with NCCRS
+many more cooperating universitiesFind my college →Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.
FAQ
Questions students ask us
About Turning Data Definitions into Working Java Code
Why use generics in Java?
Why can't you use int as a generic type argument in Java?
What does T extends Comparable<T> mean in Java?
Is a Stack<String> also a Stack<Object> in Java?
About the Data Structures and Algorithms course
How many college credits is Data Structures and Algorithms?
How much does Data Structures and Algorithms cost and what is included?
Which universities accept UPI Study credits?
How long does Data Structures and Algorithms take?
How are the exams done?
How do my credits reach my college?
Ready for the full course? Earn 3 credits in Data Structures and Algorithms.
87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.
3 credits · NCCRSEnroll →