Collections That Grow as Elements Are Added, Explained

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

Collections That Grow as Elements Are Added

Data Structures and Algorithms · Chapter 11: Dynamic Lists, Iterators, and the Collections FrameworkSection 11.1 · lesson 44 of 8711 min · free with a free account

← Queue Applications: Scheduling, Buffering, TraversalNext lesson: Positional List Operations →

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

Dynamic arrays, geometric growth, amortized appends, and Java's ArrayList.

  • Distinguish a dynamic array's size from its capacity
  • Explain why geometric growth gives amortized constant-time appends
  • Apply a shrinking rule that avoids thrashing
  • Use ArrayList, an initial capacity, and trimToSize appropriately

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

Opening Question

Moving Books to a Bigger Shelf

Picture a bookshelf with room for eight books. You buy books one at a time, and line them up. When the ninth arrives, there's no room. You buy a bigger shelf, and carry every book over to it. If each new shelf holds just one more book, you'll spend your life carrying books. If each holds twice as many, the moves become rare, and cheap per book. A Java array is that first shelf: its length is fixed. A dynamic array does the moving for you. The question is how much bigger the new shelf should be.

Definition

Size Versus Capacity

A dynamic array wraps an ordinary array, and tracks two numbers. The size is how many elements it holds. The capacity is the length of the array underneath. The size never exceeds the capacity, and the elements always fill the first size slots. The difference is spare room. So an array of capacity eight holding five elements has three spare slots. The size changes on every add and remove. The capacity changes only when the array grows or shrinks.

Implementation

Append and Resize

Here's the simplest version, holding ints. It starts with capacity four, and doubles whenever it's full. Append asks one question first: is the array full? If so, it makes room. Otherwise, it's just two steps: store the value, and add one to size. A Java array can never change length, so growing really means replacing it. Resize allocates a new array, copies every element across, and points the field at the new one. The old array is no longer referenced, and the system cleans it up. The copies counter isn't part of the design. It just counts the work.

Worked Example

Seventeen Appends, Three Resizes

This main appends ten, twenty, thirty, and so on up to one hundred seventy: seventeen values. Resize prints a line whenever the capacity changes. When the fifth value arrives, four are stored, so four are copied, and the capacity goes to eight. Then again at the ninth value, copying eight, and at the seventeenth, copying sixteen. The array ends with size seventeen, and capacity thirty-two. Seventeen appends caused only three resizes. Everything in between was a plain two-step append.

Comparison

Adding One Versus Doubling

Doubling is a choice. When the array is full, the new capacity could be one more, ten more, one and a half times, or twice as much. This program compares them, starting from capacity ten. It doesn't copy anything. It just adds up how many copies each rule would make. For ten thousand appends, adding one makes almost fifty million copies: about five thousand per append. Doubling makes about ten thousand: one per append. Now ten times as many appends. Adding one needs a hundred times the copies, about five billion. Doubling still needs under two copies per append.

Key Idea

Geometric Growth Makes Resizes Rare

Why the gap? A fixed block of room is used up after a fixed number of appends. So the number of resizes grows with n, and each one copies a bigger array. Multiplying behaves differently. Each new array is a fixed fraction bigger than the last, so resizes get rarer as the array grows: only fourteen for a hundred thousand appends with doubling. Growing the capacity by a fixed factor above one is called geometric growth. It's the right choice for a dynamic array. Java's ArrayList grows by about one and a half.

Analysis

Amortized Constant-Time Append

With doubling, most appends are cheap and a few are costly. Count one step for each write, plus every element copied. The first four appends cost one each. The fifth costs five: the write and four copies. Then nine, seventeen, and thirty-three, further and further apart. Thirty-four appends cost ninety-four steps in all, an average of about two point seven six. The copies add up to four plus eight plus sixteen and so on, which is less than the final capacity. And that's less than twice the number of elements, so n appends cost under three n steps. That's amortized cost: the total for a sequence, divided by the number of operations. Here it's constant, so append runs in amortized order one.

Caveat

One Append Can Still Be Slow

Notice what that claim doesn't say. A single append can still be slow, as slow as copying the whole array, so the worst case for one append is order n. The promise is about the average over a sequence of appends, and it holds for any sequence, not just lucky ones. In general, a growth factor g gives between one over the quantity g minus one, and g over that same quantity, copies per append. That's one to two for doubling, and two to three for one and a half, just as measured.

Quick Check

Copies for Forty Appends

Quick check. The same dynamic array starts at capacity four, and doubles. This main appends forty values, one by one. Then it prints the total number of elements copied. What does it print? Pause and predict. It prints sixty. The array resizes when the fifth, ninth, seventeenth and thirty-third values arrive, copying four, eight, sixteen, and thirty-two. Four plus eight plus sixteen plus thirty-two is sixty, and the capacity ends at sixty-four. Twenty-eight misses the last resize, at the thirty-third value. A hundred twenty-four adds a resize to sixty-four that never happens: forty values fit.

Trade-Offs

Spare Capacity Costs Memory

Spare capacity isn't free. It's memory that's reserved, but holds nothing. Right after a doubling, about half the array is spare. With growth by one and a half, about a third. So a growth factor trades time, fewer copies, against space, more spare room. Adding a constant keeps only a few spare slots, but its copying grows with n, which is far too costly.

Common Mistake

Shrink at a Quarter, Not at Half

Spare room matters most when a collection shrinks. A list that once held a million elements, and now holds ten, still keeps its million-slot array, unless something gives the memory back. The obvious rule, shrink to half as soon as the array is half empty, is a trap. At sixteen in sixteen, one append doubles to thirty-two. One removal leaves it half empty, so it shrinks back to sixteen. The next append doubles again, and every operation pays for a full copy. The safe rule leaves a wide gap: grow when full, but shrink only when the size drops to a quarter of the capacity, and then shrink to half. Over a thousand rounds of one append and one removal, shrinking at half copied thirty-two thousand elements. Shrinking at a quarter copied sixteen, once.

Quick Check

When the Array Shrinks

Quick check. This main appends twenty values, so the capacity reaches thirty-two. Then it calls remove last twelve times. Resize prints a line for every capacity change. Which line does the shrinking print? Pause and predict. It prints size eight, thirty-two to sixteen. Twelve removals take the size from twenty down to eight, and eight is a quarter of thirty-two. So the array shrinks to half, sixteen, and is left half full. Size sixteen would be the half-empty rule, the one that thrashes. And thirty-two to eight would leave the array full, so the next append would grow it right back.

Java Library

How ArrayList Grows

Java doesn't make you write your own. Java util provides ArrayList, a ready-made dynamic array for any object type, written in angle brackets. This program adds three names, then asks for the size, whether it's empty, and whether it contains Ben. Clear removes everything. The second list is created with an initial capacity of a thousand, so its first thousand adds need no resize at all. The element type must be an object type. Integer works, but ask for a list of plain int, and javac refuses: unexpected type, required, reference, found, int. Java converts between int and Integer automatically, but each Integer is a separate object, so a list of them uses more memory than an int array. The capacity of an ArrayList isn't visible through its methods. But inspecting its internal array, on OpenJDK twenty-one, shows how it grows. A new list reserves nothing until the first element arrives. Then it allocates ten, and each resize after that multiplies by about one and a half: fifteen, twenty-two, thirty-three, forty-nine. Clear empties the list, but keeps the capacity for reuse. Trim to size is how a program gives the room back. Those exact numbers are details of one Java version. The documentation promises only amortized constant-time add, so rely on that, not on the factor.

Decision Guide

ArrayList, Initial Capacity, or Array

So, which to use? When the number of elements is unknown, and items are mostly added at the end, use an ArrayList: add is amortized order one. If you know the approximate final size, say a million records about to load, give it that initial capacity, or call ensure capacity first, to skip every resize. For a fixed number of int values, a plain array avoids both the growth logic and an object per element. And when a list grew huge and is now small for good, trim it.

Key Takeaways

Dynamic Array Essentials

To sum up. A dynamic array keeps a size and a capacity. When it's full, it allocates a bigger array, copies, and switches over. Growing by a constant makes copying explode. Growing by a factor, like two or one and a half, keeps copies per append constant: amortized order one. Shrink only at a quarter, and then to half, so growing and shrinking can't thrash. And ArrayList is Java's dynamic array. Clear keeps the capacity, and trim to size gives it back.

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 Collections That Grow as Elements Are Added

What is the difference between size and capacity in an ArrayList?
Size is the number of elements a dynamic array holds, while capacity is the length of the array underneath it. Size is never larger than capacity, and the difference is spare room. Size changes on every add and remove, but capacity changes only when the array grows or shrinks. In ArrayList, size() reports the size, while the capacity is not visible through its methods.
Why do dynamic arrays double instead of growing by a fixed amount?
Growing by a factor such as 2 keeps copying constant per append, while growing by a fixed amount makes copying grow with n. Starting from capacity 10, ten thousand appends with plus-one growth make almost 50 million copies, about 5,000 per append, while doubling makes about 10,000, roughly one per append. Multiplying makes resizes rarer as the array grows, which is called geometric growth.
Why is ArrayList add amortized O(1)?
ArrayList add is amortized O(1) because the capacity grows by a constant factor, so expensive copies get rarer as the list grows. OpenJDK's ArrayList grows by about 1.5 times; for a doubling array starting at capacity 4, copies total 4 + 8 + 16 and so on, less than the final capacity, so n appends cost fewer than 3n steps. A single add can still be O(n) when it triggers a resize; the guarantee covers the average over a sequence.
When should a dynamic array shrink?
A common rule is to shrink a dynamic array to half its capacity once its size drops to a quarter of it. Shrinking as soon as it is half empty causes thrashing: at size 16 and capacity 16, one append doubles to 32, one removal shrinks back to 16, and every operation pays for a full copy. In Java's ArrayList, clear keeps the capacity, and trimToSize gives spare room back.

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 →