A Tour of Java's Pre-Built Collection Tools, Explained

UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 11.4 Free with a free account

A Tour of Java's Pre-Built Collection Tools

Data Structures and Algorithms · Chapter 11: Dynamic Lists, Iterators, and the Collections FrameworkSection 11.4 · lesson 47 of 8714 min · free with a free account

← Visiting Every Element of a Collection One at a TimeNext lesson: Rearranging Positional Collections into Order →

Earn 3 college credits for Data Structures and AlgorithmsRecommended for credit by NCCRS · Computer Science 251 · self-paced · one payment, lifetime access
Enroll in Data Structures and Algorithms · $250 →Download the syllabus (PDF)

In this lesson

Choosing among Java's lists, sets, queues, deques and maps.

  • Describe how Collection, List, Set, Queue, Deque and Map relate in the Collections Framework
  • Compare the ordering and cost of hash, linked hash and tree implementations
  • Choose a container by asking about keys, uniqueness, priority and ends
  • Use the Arrays and Collections helper classes while avoiding fixed-size and read-only traps

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 (2,133 words). Read along, or search it.

Opening Question

One Family of Ready-Made Containers

Imagine every container in Java had its own method names: push for one, insert for another, append for a third. Every change of container would mean rewriting your code. Instead, Java ships one well-tested family of ready-made containers: lists that grow, sets that reject duplicates, queues, double-ended queues, and maps from keys to values. Together, they're called the Collections Framework. Knowing which one to reach for, and why, matters as much as knowing how to build one.

Interface Hierarchy

Collection Above List, Set and Queue

The framework is organized by interfaces. An interface is a list of promises: add an item, test for an item, report the size. An implementation is a concrete container that keeps those promises, in its own way. At the top sits Iterable, and below it, Collection: the common ancestor of List, Set and Queue. Anything that's a Collection can add, remove, test with contains, report its size, check is empty, and be looped over. Deque extends Queue: a double-ended queue is a queue that can also be used from the other end. Map is a separate family. It stores key-value pairs, which don't fit the single-item shape of a Collection. And LinkedList appears twice in the family, because it implements both List and Deque.

Worked Example

Five Implementations, One Describe Method

Because the interfaces carry the promises, your code should name the interface, and mention the implementation only where an object is created. Then switching to a different container is a one-word edit. This describe method accepts any Collection of strings. It relies only on size, contains, and the collection's text form. Main gives the same six words, with apple twice, to five different implementations, and describes each one. Same method, same data, five different results. The two list-like containers keep all six words, including the repeated apple. The three sets keep five, because a set never holds duplicates. And the order is where they separate. The linked hash set follows arrival order, the tree set sorts alphabetically, and the hash set has an arrangement of its own. That last order isn't specified by Java, and it can differ between versions. A correct program never relies on it.

Interface Promises

What Each Interface Guarantees

Choosing a container starts with choosing the interface, and that's a question about what your program needs to do. A List keeps items at numbered positions, and allows duplicates. Its signature methods are get, set, add and remove, by index. A Set holds each item at most once. Its add method returns false for a repeat. A Queue hands items out in waiting order, with offer, poll and peek. A Deque is a queue that works at both ends. And a Map leads each key to one value. Keys never repeat, though values may. Its methods are put, get, contains key, and get or default. Here's one short example of each promise, in a single program. The list keeps the repeated a, so its size is three, and get of one returns b, the item at position one. The set's add reports whether anything changed: true the first time, false for the repeat. The size stays one. The queue hands items back in arrival order. Peek looks at the front, without removing it. The deque grows at both ends: front, middle, back. And poll last takes from the far end. The map's put returns the value it replaced, one. And get on a missing key returns null, not an error.

Map Views

Keys, Values and Entries as Collections

A Map is not a Collection, but it can produce collections. Key set gives its keys as a Set. Values gives its values. And entry set gives its key-value pairs, which is how a map is looped over.

Implementations

Lists, Deques and Priority Queues

Once the interface is chosen, the implementation decides two things: the order you get back, and the speed. For lists, ArrayList is the default: indexed access, and fast at the end. LinkedList is a List and a Deque in one object, but reaching position i means walking from an end. It's rarely the best choice. For stacks and queues, ArrayDeque is fast at both ends. It has no access by position, and it doesn't accept null. And PriorityQueue always hands out the smallest item next, though only the head is in order.

Three Flavors

Hash, Linked Hash and Tree Order

Sets and maps come in the same three flavors. Hash set and hash map are the fast defaults, and their order isn't specified. Linked hash set and linked hash map keep insertion order, for a little more memory. Tree set and tree map keep sorted order, so the items or keys must be comparable. A tree set is also good for nearest-value searches.

Cost Table

Costs for Lists and Deques

Speed matters as much as order. Here are the usual costs, where n is the number of items. An ArrayList reaches any position in one step. But searching for a value means walking, so it's order n. Adding at its end is constant time, amortized: that is, averaged over many adds. At the front, every item shifts, so it's order n. A LinkedList is constant time at its ends, but order n to reach a position. ArrayDeque is constant time at both ends, with no positions at all.

Cost Table

Costs for Hashing, Trees and Heaps

Hash sets and hash maps find a value in about one step, on average. Tree sets and tree maps take order log n. And a priority queue adds or removes its best item in order log n, and shows it in constant time. Searching it for any other value is order n. Two lessons follow. A list searches by walking, so calling contains on a list thousands of times is expensive. A hash set answers in about one step. And LinkedList isn't the shortcut it looks like. ArrayList is usually the better list, and ArrayDeque the usual stack or queue.

Common Surprise

Printed Order Versus Removal Order

The priority queue deserves a closer look, because printing it is misleading. Five numbers are offered in a scrambled order: five, three, four, one, two. The queue is printed, and then emptied with poll. The printed text is one, two, four, five, three. It's not sorted. But the removal order is one, two, three, four, five. A priority queue promises only that the next item out is the best one. Its printed form shows its internal arrangement, which isn't part of the promise.

Worked Example

Counting Words With Three Maps

Maps show the same thing. This program counts the words of one sentence, with three different kinds of map. The count method works on any Map. Get or default gives zero for a word not seen yet, and put stores the new count. All three maps hold the same counts: to appears three times, and be twice. The linked hash map lists the words as they first appeared. The tree map lists them alphabetically. And the hash map uses an order you can't predict. Which one is right depends on what the output is for. A report for a reader probably wants the sorted version.

Quick Check

Adding a Repeat to a Tree Set

Quick check. This program adds kiwi, fig, kiwi and apple to a tree set. Then it adds fig once more, and prints what that add returned, followed by the set. What's printed? Pause and predict. It prints false, then apple, fig, kiwi. The set already held fig, so that add changed nothing, and reported false. The second kiwi was refused the same way. And a tree set always lists its items in sorted order. True with two figs is what a list would give. And kiwi, fig, apple is arrival order, which a linked hash set would keep.

Older Code

Vector, Stack and Hashtable

One warning about older code. Java also contains Vector, Stack and Hashtable, which date from before the framework. They still work, but their modern replacements are ArrayList, ArrayDeque and HashMap. If a tutorial uses the old ones, treat that as a sign of its age.

Helper Class

Static Methods for Plain Arrays

Plain arrays have no methods of their own, so Java provides a helper type named Arrays, whose static methods work on them. Arrays.toString gives an array's text form. Printing the array variable itself shows only a type code and a hash, not the numbers. Here, sort works on a copy, so the original stays untouched. Binary search finds nineteen at index two, because the copy is sorted. On an unsorted array, its answer would be meaningless. Copy of range takes a slice, and fill sets every element to one value. Equals compares contents. The scores and the sorted copy hold the same numbers in a different order, so the first comparison is false. The double equals operator would only check whether they're the same array. And deep to string prints an array of arrays.

Common Trap

A Fixed-Size View of an Array

Arrays.asList is convenient, but it returns a view of the array, not a free-standing list. A view shows another object's data without copying it. Changing an item through the view changes the array too. But the view can't grow or shrink, so add throws an unsupported operation exception. The fix is a real copy. A new ArrayList built from the view is independent, and it can grow. List.of goes further than a view: it's completely read-only, so its add fails as well.

Naming Confusion

Collection, Collections and Arrays

Be careful with three names that are easy to confuse. Collection, singular, is the interface: the parent of List, Set and Queue. Use it to declare a variable that accepts any of them. Collections, plural, is a helper type with static methods, for sorting, reversing, searching and wrapping lists. And Arrays does the same jobs for plain arrays. Mix up the first two, and you get a compile error for a method that isn't there.

Helper Class

Collections Helpers at Work

Here are the Collections helpers at work, on a list holding eight, three, nine, three, five. Sort and reverse rearrange the list in place. Max and min give nine and three, and frequency counts the two threes. Swap of zero and four exchanged the first and last items of the reversed list. Shuffle used a Random seeded with one, so the same order comes out on every run. Unmodifiable list gives a read-only view: it refuses changes, though the list underneath can still change through its own variable. N copies makes an immutable list of repeated items. List of, set of and map of are read-only too, and set of and map of promise no iteration order.

Decision Guide

Questions for Picking a Container

So which container should you reach for? Ask these questions from the top, and stop at the first yes. Do you look items up by a key? Then it's a Map: hash map for speed, linked hash map for insertion order, tree map for sorted keys. Must every item be unique? Then it's a Set, with the same three choices. Always need the smallest item next? A priority queue. Working mostly at the two ends? An array deque, as a stack or a queue. Otherwise, ArrayList is the default choice: ordered by position, indexed, and fast at the end. Declare the variable with the interface, and the choice stays reversible. If testing shows a better fit, only the word after new changes.

Quick Check

Urgent Tickets Jump the Line

Quick check. A help desk handles tickets in order of arrival. But urgent tickets must jump the line, ahead of everything already waiting. Which container fits? Pause, and decide. A priority queue, declared as a Queue. Order the tickets by urgency, and by arrival time to break ties, so poll always returns the most urgent. An array deque is strictly first in, first out, so an urgent ticket could never jump ahead. A linked hash set also keeps arrival order, so it has the same problem. And a set is for unique items, not for a waiting line.

Common Mistake

Remove by Index or by Object

One common mistake is worth seeing run. A list of integers has two methods named remove: one takes an index, and one takes an object. With a plain int argument, Java chooses the index version. So remove of one took out the item at position one, the twenty, not the value one. Only the second call, with the number wrapped as an Integer object, removed the value one.

More Mistakes

Five More Traps to Avoid

A few more mistakes to avoid. Calling get of i in a loop over a LinkedList walks from an end every time, so iterate instead. Binary search on unsorted data gives a meaningless index. Sort first, or use contains on a set. Set items or map keys without suitable equals and hash code methods: equal-looking objects are treated as different. Putting items that can't be compared into a tree set fails at run time. Make the type comparable, or supply a comparator. And declaring an ArrayList variable, instead of a List, ties your code to one implementation.

Key Takeaways

Interfaces Promise, Implementations Deliver

To sum up. Collection is the parent of List, Set and Queue. Deque extends Queue, and Map is a separate family. The interface sets the promises about duplicates, order and operations. The implementation sets the order you actually get, and the cost. Arrays and Collections hold the static helpers, and watch for the read-only and fixed-size traps. And declare with the interface, so changing the implementation is a one-word edit.

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

How programs store and search dataData Structures and Algorithms teaches how to organize data and measure how fast code runs: arrays, linked lists, stacks, queues, trees, heaps, hash tables, sorting and graphs, all written in Java. It is a core course in computer science and software degrees.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

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 UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks 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 A Tour of Java's Pre-Built Collection Tools

What is the difference between Collection and Collections in Java?
Collection, singular, is the interface that List, Set and Queue extend, so a Collection<String> variable can hold any of them. Collections, plural, is a utility class of static methods such as sort, reverse, max, min, frequency, shuffle and unmodifiableList. Arrays plays the same helper role for plain arrays. Mixing up the two names causes a compile error, because the Collection interface has no static sort method.
Should I use ArrayList, LinkedList or ArrayDeque in Java?
ArrayList is the usual default list: it reaches any index in O(1) and adds at the end in amortized O(1). For a stack or a queue, ArrayDeque is usually the better choice, with constant-time work at both ends, though it has no index access and rejects null. LinkedList implements both List and Deque, but reaching a position takes O(n), so it is rarely the best option.
Why does Arrays.asList throw UnsupportedOperationException on add?
Arrays.asList returns a fixed-size view backed by the array, not an independent list. Calling set works and writes through to the array, but add and remove would change the size, so they throw UnsupportedOperationException. List.of is stricter: it is fully unmodifiable, so even set throws. When a list must grow, copy it, as in new ArrayList<>(Arrays.asList("a", "b")), which creates an independent, resizable list.
How do you choose the right Java collection for a task?
Ask a few questions in order and stop at the first yes. Looking items up by key calls for a Map: HashMap for speed, LinkedHashMap for insertion order, TreeMap for sorted keys. Requiring unique items calls for a Set with the same three choices. Needing the smallest item next calls for a PriorityQueue, and working mostly at both ends calls for ArrayDeque. Otherwise, use ArrayList, declared as a List.

About the Data Structures and Algorithms course

How many college credits is Data Structures and Algorithms?
Data Structures and Algorithms (Computer Science 251) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Data Structures and Algorithms cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Data Structures and Algorithms take?
It is self-paced with no deadlines. The 87 lessons total about 15 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

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.

Enroll in Data Structures and Algorithms →Download the syllabusEvery course with PRO →
Data Structures and Algorithms
3 credits · NCCRSEnroll →