The Need for Flexible Collections

Section 12.2 The Need for Flexible Collections

Think about common tasks in programming. Often, we aren’t just dealing with single pieces of information, but with groups or collections of related items. Consider these scenarios:

🔗

Keeping track of all the usernames currently logged into a system.

🔗
Storing the sequence of steps required to complete a task.

🔗
Managing the items a customer has placed in their online shopping cart.

🔗
Maintaining a list of high scores achieved in a game.

🔗

In each case, we need a way to store and manage a potentially changing number of elements.

🔗

How have we handled multiple items previously? You might initially think of using many separate variables (like item1, item2, item3), but this clearly doesn’t scale well if you don’t know how many items you’ll have. A more structured approach we encountered is using arrays (See Chapter 4). Arrays provide a way to store a sequence of items of the same type under a single variable name, using an index to access specific elements.

🔗

// An array can hold a fixed number of items
String[] shoppingList = new String[5]; // Create space for exactly 5 items

shoppingList[0] = "Apples";
shoppingList[1] = "Milk";
// ... potentially fill up to shoppingList[4] ...

String firstItem = shoppingList[0]; // Access using index

Arrays are powerful and efficient for accessing elements if you know their index. However, they come with a significant limitation that causes problems for scenarios like our shopping cart or high score list: arrays have a fixed size. When you create an array using new String[5], you are allocating memory for exactly 5 String references, no more, no less. This fixed nature presents two major challenges:

🔗

Running out of space: What happens if our shopping list needs a 6th item? The array created with size 5 simply cannot hold it.
🔗
```
String[] shoppingList = new String[5];
// ... fill items 0 through 4 ...
// shoppingList[5] = "Bread"; // ERROR! This causes an ArrayIndexOutOfBoundsException at runtime.
```
Trying to access an index outside the array’s bounds (0 to length-1) results in a program crash.
🔗

🔗
Wasting space (or guessing): If we don’t know the exact number of items needed beforehand, we might try to guess a "large enough" size:
🔗
```
String[] maybeEnoughScores = new String[1000]; // Hope we never get more than 1000 high scores?
maybeEnoughScores[0] = "PlayerA: 5000";
maybeEnoughScores[1] = "PlayerB: 4500";
// ... but maybe only 10 scores are ever added.
```
In this case, we’ve allocated space for 1000 scores, but most of that memory might sit unused, which is inefficient. Furthermore, what if our guess was wrong, and the game becomes wildly popular with 1001 high scores? We’re back to running out of space!
🔗

🔗

Because fixed-size arrays are often impractical when the number of items isn’t known in advance or can change frequently, we need a more flexible solution. We need a dynamic collection – a structure that can automatically grow (and perhaps shrink) its capacity as elements are added or removed, without the programmer having to manually manage fixed-size arrays.

🔗

This chapter focuses on building one common type of dynamic collection: a List. Our specific goal is to create an ArrayList<T> class that provides the functionality of a list but uses an array internally, cleverly handling the resizing process "under the hood" so that the user of the list doesn’t have to worry about the fixed-size limitation of the underlying array. This project will give you valuable insight into how such fundamental data structures are designed and implemented.

🔗

You have attempted of activities on this page.

🔗

Prev Top Next