32 Operations on Lists
In the prior lecture, we journeyed through the concept of collections of data and their manifestations in computer memory. Such collections were referred to as lists, a data structure central to understanding the organization and manipulation of data in programming. Our objective is to delve into the practical implementation of these lists in Java. However, before we embark on that, we must consider the types of operations we desire our lists to perform. These operations guide our implementation strategy and ensure that our list behaves in the ways we want it to. In this chapter, we’ll be investigating operations performed on a List Abstract Data Type (ADT).
32.1 Adding Data to a List
As you may recall, a list is a collection of data elements. A key operation, therefore, is the ability to add data to this collection. Let’s visualize a simple list:
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|
There are multiple ways to insert new data into this list. For instance, you might want to add a new element, say “X”, at the end:
| 1 | 2 | 3 | 4 | 5 | 6 | X |
|---|
Alternatively, you could place “X” at the beginning:
| X | 1 | 2 | 3 | 4 | 5 | 6 |
|---|
Or perhaps insert “X” somewhere in the middle:
| 1 | 2 | 3 | X | 4 | 5 | 6 |
|---|
There are three distinct methods to add data to our list, and each method may serve different needs in your program. Let’s discuss how these operations are implemented in the List ADT provided by the Java standard library, java.util.List.
32.1.1 Appending an Element
Appending an element to the end of a list is perhaps the most straightforward method of adding data. The add method provided by java.util.List is used for this operation. Here is how you might use it:
listObject.add(itemToAdd);32.1.2 Prepending an Element
Inserting an element at the beginning of a list is also a common operation, often called “prepending”. Though the java.util.List interface doesn’t provide a prepend method, we can use the overloaded add method, which accepts an index and an element. To prepend, we simply pass 0 as the index:
listObject.add(0, itemToAdd);32.1.3 Inserting an Element at a Specific Index
As hinted in the prepend operation, the add method in java.util.List allows for adding an element at any index in the list:
listObject.add(index, itemToAdd);32.1.4 Adding All Elements from Another List
Sometimes, you may want to merge one list into another. The addAll method allows you to add all the elements from another list to the end of the current list:
listObject.addAll(anotherList);32.2 The Role of Abstract Data Types (ADTs)
We’ve mentioned the term “Abstract Data Type” (ADT) several times so far, but what does it really mean? An ADT is a high-level description of a collection of data and the operations that can be performed on that data. It is “abstract” in that it describes what operations are to be done but not how these operations will be implemented.
In the context of lists,
the List ADT defines a list’s behavior. For instance, we can append, prepend, or insert an element at a specific index, but we don’t care about how these operations are performed.
Why do we need ADTs? ADTs allow us to abstract away the details of the data structure’s implementation. They encapsulate the data and provide a well-defined interface to interact with it, ensuring that data remains consistent and operations on the data are predictable. Moreover, by using ADTs, different implementations of the same type of data structure can be swapped seamlessly, without changing the code that uses the data structure.
In your journey with Java so far, you’ve only used one kind of list – the ArrayList. As you progress, you’ll encounter other types of lists, like LinkedLists and Stacks, each with its own strengths, weaknesses, and suitable use cases. All these list types adhere to the same List ADT, allowing us to switch from one type to another depending on our requirements, while our code remains largely the same.
In the next sections of this course, we will dive deeper into different types of lists and their unique characteristics. For now, the important takeaway is that ADTs allow us to focus on what operations we want to perform without worrying about how they are implemented.
32.2.1 Summary of Addition Operations
Here is a summary of the adding operations available in the java.util.List ADT:
| Modifier and Type | Method and Description |
|---|---|
| boolean | add(E e) Appends the specified element to the end of this list (optional operation). |
| void | add(int index, E element) Inserts the specified element at the specified position in this list (optional operation). |
| boolean | addAll(Collection<? extends E> c) Appends all of the elements in the specified collection to the end of this list, in the order that they are returned by the specified collection’s iterator (optional operation). |
| boolean | addAll(int index, Collection<? extends E> c) Inserts all of the elements in the specified collection into this list at the specified position (optional operation). |
32.3 Removing data from our List
32.4 Removing Data from a List
Having explored the addition of data to a list, let’s now shift our attention to its counterpart: removing data from the list. Remember our list from the previous section?
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|
Let’s consider different ways to remove data from this list.
32.4.1 Removing an Element at a Specific Index
Sometimes, you might need to remove an item from a specific position within the list. Java’s List ADT provides the remove(int index) method for this purpose. This method removes the element at the specified position:
listObject.remove(index);32.4.2 Removing the First Occurrence of an Element
At times, you might not know (or care about) the index of the element you want to remove, but you know the value of the element. In such cases, you can use the remove(Object o) method, which removes the first occurrence of the specified element from the list:
listObject.remove(objectToRemove);32.4.3 Removing All Elements from Another List
Consider that you have two lists, and you want to remove all elements in the second list from the first one. You can use the removeAll(Collection<?> c) method, which removes from the current list all of its elements that are contained in the specified collection:
listObject.removeAll(anotherList);32.4.4 Removing All Elements from the List
In some scenarios, you might want to clear your list entirely. The clear() method comes in handy for this, as it removes all elements from the list:
listObject.clear();Like the addition operations, these removal operations offer different ways to manage the data in our list, providing flexibility based on the specific needs of our program.
32.4.5 Summary of Removal Operations
Here is a summary of the removal operations available in the java.util.List ADT:
| Modifier and Type | Method and Description |
|---|---|
| E | remove(int index) Removes the element at the specified position in this list (optional operation). |
| boolean | remove(Object o) Removes the first occurrence of the specified element from this list, if it is present (optional operation). |
| boolean | removeAll(Collection<?> c) Removes from this list all of its elements that are contained in the specified collection (optional operation). |
| void | clear() Removes all of the elements from this list (optional operation). |
32.5 Searching for data in our List
32.6 Searching in a List
Beyond just adding and removing data from our list, we often need to find or check for the existence of certain elements in our list. Java’s List ADT provides several methods for such search operations. Let’s dive into these operations using our familiar list:
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|
32.6.1 Checking If an Element Exists in the List
Sometimes, all we need to know is whether a certain element exists in our list. The contains(Object o) method serves this purpose, returning true if this list contains the specified element, and false otherwise:
boolean contains = listObject.contains(objectToCheck);32.6.2 Checking If All Elements of Another Collection Exist in the List
If you have a collection of elements and you want to check whether all these elements exist in your list, you can use the containsAll(Collection<?> c) method. It returns true if the list contains all of the elements of the specified collection:
boolean containsAll = listObject.containsAll(anotherCollection);32.6.3 Finding the Index of an Element
If you want to find the position of a certain element in your list, Java provides the indexOf(Object o) method. This method returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element:
int index = listObject.indexOf(objectToFind);32.6.4 Finding the Last Index of an Element
In a list with duplicate elements, you might be interested in finding the last occurrence of an element. In this case, you can use the lastIndexOf(Object o) method, which returns the index of the last occurrence of the specified element in this list, or -1 if this list does not contain the element:
int lastIndex = listObject.lastIndexOf(objectToFind);32.6.5 Summary of Search Operations
Here is a summary of the search operations available in the java.util.List ADT:
| Modifier and Type | Method and Description |
|---|---|
| boolean | contains(Object o) Returns true if this list contains the specified element. |
| boolean | containsAll(Collection<?> c) Returns true if this list contains all of the elements of the specified collection. |
| int | indexOf(Object o) Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element. |
| int | lastIndexOf(Object o) Returns the index of the last occurrence of the specified element in this list, or -1 if this list does not contain the element. |
Search operations are a fundamental part of manipulating lists. They allow us to locate and verify the presence of data, enhancing our ability to interact with our list and derive meaningful results.
32.7 Miscellaneous Operations on a List
In addition to adding, removing, and searching elements in our list, Java’s List ADT provides a variety of other useful operations. These allow us to manipulate and inquire our list in a more sophisticated manner.
32.7.1 Accessing an Element
Sometimes, we need to retrieve the element at a specific position in our list without removing it. The get(int index) method provides this functionality, returning the element at the specified position:
E element = listObject.get(index);32.7.2 Modifying an Element
What if we need to change an element at a specific position? Java provides the set(int index, E element) method. This method replaces the element at the specified position in this list with the specified element:
listObject.set(index, newElement);32.7.3 Determining the Size of the List
When working with lists, it’s often necessary to know the number of elements present. The size() method returns the number of elements in this list:
int size = listObject.size();32.7.4 Converting the List to an Array
On occasion, we may need to convert our list into an array. The toArray() method fulfills this purpose, returning an array containing all the elements in this list in proper sequence:
Object[] array = listObject.toArray();32.7.5 Summary of Miscellaneous Operations
Here is a summary of the miscellaneous operations available in the java.util.List ADT:
| Modifier and Type | Method and Description |
|---|---|
| E | get(int index) Returns the element at the specified position in this list. |
| E | set(int index, E element) Replaces the element at the specified position in this list with the specified element (optional operation). |
| int | size() Returns the number of elements in this list. |
| Object[] | toArray() Returns an array containing all of the elements in this list in proper sequence (from first to last element). |
These miscellaneous operations on a list help us to manipulate and utilize our lists effectively. In the subsequent sections, we will delve deeper into different types of lists and how these operations can be applied differently. Stay tuned!
32.8 Summary and Conclusion
This chapter aimed to offer a comprehensive understanding of operations that can be performed on lists using the Java programming language. It introduced key manipulations including adding, removing, and searching for elements in a list, as well as several other useful list operations.
We began by delving into the process of adding elements to a list, where we considered various insertion methods such as appending, prepending, and inserting at a specific index. We also explored the ability to add all elements from another list into the current list. These addition operations provide flexibility and adaptability in managing data in our list as required by the program.
Next, we moved on to the concept of removing elements from a list. We investigated removing elements at specific indices, removing the first occurrence of an element, and removing all elements from a list or all elements present in another list. These removal operations are just as vital in data management, providing diverse ways to regulate the contents of our list.
Subsequently, we analyzed search operations within a list. These operations are crucial in data retrieval, determining the existence and position of data elements in our list. Methods like contains(Object o), containsAll(Collection<?> c), indexOf(Object o), and lastIndexOf(Object o) were discussed in depth.
Furthermore, we examined miscellaneous operations that provide additional functionality in our list. These include accessing and modifying elements at specific indices, determining the size of the list, and converting the list into an array.
Throughout our exploration, we highlighted the significant role of Abstract Data Types (ADTs). By standardizing the operations that can be performed on a list, the List ADT allows us to focus on what we want to accomplish without concerning ourselves with the underlying implementation details. This abstraction brings forth code consistency, reliability, and the potential for seamless integration of different list implementations.
In conclusion, understanding and utilizing list operations in Java is fundamental for effective data management in programming. The breadth of operations available affords us immense flexibility in manipulating lists to align with our program’s requirements. As we proceed in this course, we will delve deeper into the different types of lists and their unique characteristics, all the while, leveraging the power and versatility of the List ADT.