We have been using arrays to store information in a format that can be iterated over (looped through). While arrays help to create more efficient code, they are not without their shortcomings. First, arrays are not dynamic. Once they have been created with a given size, they remain that size. Also, to add/delete an element in middle of the array requires extra code to shift all other elements appropriately. Second, arrays do not know their logical size (actual number of items), they only know their physical size (space allotted). This requires programmers to create extra variables if they want to keep track of the array's logical size.
The ArrayList Class
Many languages, Java included, incorporate a data structure called a list. In Java, we often use an ArrayList, as its structure mimics that of an array. The ArrayList class represents a dynamic list of elements. When we add or delete elements in the list, the list automatically resizes itself and performs any required shifting. Also, because an ArrayList is dynamic, it keeps track of its logical size. The ArrayList class requires the use of the java.util.ArrayList import.
Downcasting and Generics
Before we get started with the ArrayList class as it exists today, it is important to take a look back at how ArrayLists used to behave. The ArrayList class was designed to hold Objects, or reference type variables. In its early iterations, one ArrayList could hold different types of information at each index. In other words, index zero might have a String while index one might have a Date. So, the .get() method, used to retrieve values from the array, returned a type Object. This caused issues with the compiler as programmers knew that they had stored a String, but the compiler saw an Object being returned. The solution to this was downcasting (casting the Object to its specific class). This can be seen in the code below:
ArrayList names=new ArrayList(); //create an ArrayList
names.add('Mickey Mouse'); //add a String
String name=(String)(names.get(0)); //return the string 'Mickey Mouse'
//We have to cast the result of the .get
//as a String so that the compiler knows what
//type it is
When Java 5 was introduced, the ArrayList class, along with many other collections were changed. The major change in these classes was that they now worked with generics. The use of generics allows a programmer to create an ArrayList of a given type. This means that programmers can only add elements of that type, but also eliminates the need for downcasting.
ArrayList <String>names=new ArrayList<String>(); //create an ArrayList of Strings
names.add('Mickey Mouse'); //add a String
String name=names.get(0); //return the string 'Mickey Mouse'
//No need to downcast because the ArrayList returns
//type String, not Object
If you look at the API for the ArrayList class in Java 5 or later, you will see the following for the get method:
get(int index)
Returns the element at the specified position in this list.
Note that the .get method returns an element of type E. That E is the generic. What it means is that it is going to return an element of whatever type the ArrayList was declared as. In our example above, that means it returns a String.
Wrapper Classes and Autoboxing
Another new feature added to the ArrayList is the concept of Autoboxing. In previous versions (before Java 5), to add ints to an ArrayList, we needed to use the wrapper classes to both add the information and take it out. The code used to look as follows:
ArrayList <Integer>scores=new ArrayList<Integer>(); //create an ArrayList of Integers
scores.add(new Integer(5)); //add an Integer object with value 5
int score=scores.get(0).intValue(); //get the int value of the Integer object
Autoboxing recognizes the relationship between primitive types and their wrapper classes (int/Integer, double/Double, and boolean/Boolean). Java 5 eliminated the need for using the wrapper classes resulting in the following code:
ArrayList <Integer>scores=new ArrayList<Integer>(); //create an ArrayList of Integers
scores.add(5); //add an Integer object with value 5(automatically boxed to Integer by java
int score=scores.get(0); //get the int value of the Integer object
//automatically unboxed by java
The ArrayList Methods
The API shows us the following useful methods for the ArrayList class. There are many other methods that can be used. They can all be found at http://docs.oracle.com/javase/6/docs/api/java/util/ArrayList.html . The list below is the set of methods required for this course.
Return type
Method Call
Purpose
boolean
add(E e)
Appends the specified element to the end of this list.
void
add(int index, E, element)
Inserts the specified element at the specified position in this list.
void
clear()
Removes all of the elements from this list.
boolean
contains(Object o)
Returns true if this list contains the specified element
E
get(int index)
Returns the element at the specified position in this list
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
boolean
isEmpty()
Returns true if this list contains no elements.
E
remove(int index)
Removes the element at the specified position in this list
boolean
remove(Object o)
Removes the first occurrence of the specified element from this list, if it is present.
E
set(int index, E element)
Replaces the element at the specified position in this list with the specified element
int
size()
Returns the number of elements in this list.
* In all of the above methods, any reference to the type E is generic. In other words, the E is a generic reference for the data type that the ArrayList was declared with. Think of it as to help make the connection to ArrayList .
Below, you will see each of these methods in action:
ArrayList <String> list = new ArrayList<String>();
list.add('Mickey Mouse'); //add Mickey Mouse at index 0
list.add('Donald Duck'); //add Donald Duck at index 1
list.add('Goofy'); //add Goofy at index 2
System.out.println(list); //OUTPUT: [Mickey Mouse, Donald Duck, Goofy]
String name1=list.get(0); //return the value at index 0
System.out.println(name1);//OUTPUT: Mickey Mouse
String old=list.remove(1);//remove and return the value at index 1
System.out.println(old); //OUTPUT: Donald Duck
System.out.println(list); //OUTPUT: [Mickey Mouse, Goofy]
list.add(1, 'Pluto'); //insert Pluto at index 1
System.out.println(list); //OUTPUT: [Mickey Mouse, Pluto, Goofy]
boolean isRemoved=list.remove('Minnie Mouse'); //remove Minnie Mouse, it exists
System.out.println(isRemoved); //OUTPUT: false
String replaced=list.set(0, 'Bugs Bunny'); //set index 0 to Bugs Bunny and return original
System.out.println(replaced); //OUTPUT: Mickey Mouse
System.out.println(list); //OUTPUT: [Bugs Bunny, Pluto, Goofy]
boolean existsInList=list.contains('Bugs Bunny'); //return true if Bugs Bunny is in list
System.out.println(existsInList); //OUTPUT: true
System.out.println(list.isEmpty()); //OUTPUT: false
System.out.println(list.size()); //OUTPUT: 3
list.clear(); //clear all elements from the list
System.out.println(list.isEmpty()); //OUTPUT: true
System.out.println(list.size()); //OUTPUT: 0
Iterating Over an ArrayList
In the examples above, we were able to use System.out.println to output a visual display of the list without having to use a loop. This is due to a display method (called toString()) in the class that is automatically called in an output situation. However, should we want to traverse the list, as we would an array, and be able to handle each list member individually, we need merely call a for loop.
ArrayList <String> list = new ArrayList<String>();
list.add('Mickey Mouse'); //add Mickey Mouse at index 0
list.add('Donald Duck'); //add Donald Duck at index 1
list.add('Goofy'); //add Goofy at index 2
for(int x=0; x<list.size(); x++)
System.out.println(list);
Java's Enhanced For Loop - for each
Java, as well as many other languages, also has a for each loop for ease of iterating over a collection. The main thing to remember about a for each loop is that it is for access ONLY. You may not add, remove, or alter any elements in the list using a for each loop. Also, the for each loop will only traverse the list forwards (starting at index 0).
The syntax for a for each loop is as follows: for(String str:list). This can be read as for each String, str in list. The loop accesses each element in the list, and temporarily (for that iteration of the loop) stores the element in str. Of course, you need to replace the String type with whatever the ArrayList type is.
ArrayList <String> list = new ArrayList<String>();
list.add('Mickey Mouse'); //add Mickey Mouse at index 0
list.add('Donald Duck'); //add Donald Duck at index 1
list.add('Goofy'); //add Goofy at index 2
for(String str:list)
System.out.println(str);
Removing Elements from an ArrayList
Should the need arise to traverse a list and remove certain elements from it, programmers must be careful to be aware that an ArrayList is dynamic, always changing. Let's look at an example designed to remove all even numbers from a list.
ArrayList <Integer> values = new ArrayList<Integer>();
values.add(3);
values.add(4);
values.add(7);
values.add(8);
values.add(4);
values.add(9);
//remove all even values
for(int x=0; x<values.size(); x++)
if(values.get(x)%2==0)
values.remove(x);
System.out.println(values);
The output for the above code is:
[3, 7, 4, 9]
What happened? Well, since the ArrayList is dynamic, as we remove an element, all of the others “slide” into a new place. So, we end up skipping elements in our loop.
In the above example, we start out with the list [3, 4, 7, 8, 4, 9]. When x=0, the value at 0 is odd, so nothing changed. When x increases to 1, we find the value 4, which is even and removed, so the resulting list is [3,7,8,4,9]. Now, when x increases to 2, we are looking at the value 8 – we have skipped the value 7, but didn't notice because it was odd. So, 8 gets removed and we have the list [3,7,4,9]. Now, x is 3 and we are looking at 9, which is odd, but we have skipped looking at 4 because we moved x right and slid 4 left.
One possible solution is to decrement x if we remove an item. The resulting loop code would look as follows:
However, if we forget to decrement, we have a problem. A more common solution to avoid skipping elements in an ArrayList is to iterate over the list backwards. This way the index and elements are moving in the same direction and elements can't get skipped.
A linked list is a list structure that organizes data in a sequential path. A linked list is a set of separate nodes all of a certain type. Each node on the list holds its own information and a ‘link’ to the next node on the list. Thus, while a linked list is similar to an ArrayList in that there is some sequential nature to the storage of information, it is different in that there are no indices and the data can be stored anywhere in memory, instead of all in the same location.
How it Works...
A LinkedList relies on a set of ListNodes. A ListNode stores data (any reference type variable) and a pointer to the next node in the list. ListNode elements have methods to access and set both the data and the pointer.
When you create a LinkedList, it creates a pointer to a ListNode, somewhere in the memory. That ListNode has a value of null and a pointer value of null (it is not pointing anywhere). When you add the first value to the list, it simply fills in the value of the initial node (the pointer is still null as it has no second element). When a second node is created, the new value goes into the new node and the next pointer of the first node is set to the address of the second node (and so on).
The List Interface
Both ArrayList and LinkedList implement the List interface. This is a common set of functions that are to be included in data structures that store information in some type of ordered list. The list interface includes the following methods:
add(Object)
add(index, Object)
get(index)
indexOf(Object)
remove(index)
set(index, Object)
So, the main functionality for both ArrayList and LinkedList stays the same. Additionally, each structure has its own methods in addition to those provided by the list interface.
The benefit of this interface is that if we stick to using ONLY the methods provided in the interface, we can exchange the data structures and not have to change our code :)
LinkedList Considerations
In terms of storage, a linked list requires not only the value, but also a pointer to a node. However, the size of the list is only bound by the storage available in the computer. And, as these locations do not need to be consecutive, it can utilize small bits of memory that may otherwise go unused.
In terms of speed and access, LinkedLists have a linear run time for retrieval (as opposed to Array and ArrayList which have constant run time due to indexing). On the other hand, Linked Lists provide constant run time for insertion and deletion (while the Array based structures are linear due to the required shifting).