8.4. List ADT - Examples with Both Implementations¶

Now that we’ve seen how the List ADT is intended to function from the user’s perspective, we can focus on how to make it work (implement it) with both an array and a linked list. In this section, we will discuss the two different ways to implement the ADT at a high level. Then, we will go into more detail in the subsequent sections.

Let’s take a look at how the array and linked list implementations would look internally after executing some of our List ADT methods.

For each of the operations in the List ADT (except the print operation), we show a few lines of Java code along with images demonstrating the internal state of the List object, myList, using both an array and a linked list as the internal data structure. We chose to use two instance variables in each class. You will likely use the same instance variables when implementing a list in the future.

Important

Both the array implementation and the list implementation provide the same functionality (they both implement the List ADT). However, the internal details are quite different. One stores the list data in an array and the other uses a linked list structure. To keep the examples simple, we only allow each list to hold strings. Other datatypes could be used with small changes to the code.

8.4.1. Operation 1: Construct a New List¶

Regardless of the implementation, a newly constructed list contains zero elements. Therefore, regardless of the underlying storage mechanism, a newly constructed list should have a list size of 0. The array-based implementation will need to create some initial storage space (in this case we chose 3 elements), but don’t confuse storage space with the number of items in the list. If you have 100 empty boxes, there are no items in those boxes.

If we execute the code below, myList will refer to an ArrayBasedList object:

List myList = new ArrayBasedList();

If we were to draw a memory map of how the variables/objects look in memory after executing this line of code, we would expect something like this:

In the array list implementation, a non-zero length array is created upon the initial construction of the list for potential future storage by the list.

If we declared and initialized the myList variable to refer to an object of type LinkedBasedList instead, the code and memory map would look like this:

List myList = new LinkedBasedList();

In the linked list implementation, no head node is created upon the initial construction of the list

Test Yourself

Regardless of whether myList refers to an object of type ArrayBasedList or an object of type LinkedBasedList, the following code should have the same output. Write the output you would expect in your notes:

List myList = // ... new LinkedBaseList() or new ArrayBasedList();
System.out.println("List Size: " + myList.size());
System.out.println("List Contents: " + myList.makeString(","));

8.4.2. Operation 2: Add an Element¶

Add element into index position 0. Adding an item to index 0 conceptually adds the item to the beginning of the list. If this add operation is successful, then we expect the list size to increase to 1.
Remember, myList could refer to either an ArrayBasedList or a LinkedBasedList¶
```
myList.add(0, "Bread");
System.out.println("List Size: " + myList.size());
System.out.println("List Contents: " + myList.makeString(","));
```
```
List Size: 1
List Contents: Bread
```
In the array list implementation, the item is stored at index position 0 within the array.

In the linked list implementation, a node object is created that contains the item, then head is assigned a reference to that node.

Note

Notice how the link-based (linked list) implementation has only created a single Node object. The array-based implementation has empty storage space
Add another element into index position 0. Remember, if the add method shifts the object currently at that position (in this case, "Bread") and any subsequent objects to the right (i.e. it adds one to their indices). Therefore, if this add operation is successful, then we expect "Bread" to shift to index position 1 and the list size to increase to 2.
Remember, myList could refer to either an ArrayBasedList or a LinkedBasedList¶
```
myList.add(0, "Cheese");
System.out.println("List Size: " + myList.size());
System.out.println("List Contents: " + myList.makeString(","));
```
```
List Size: 2
List Contents: Cheese, Bread
```
In the array list implementation, the current contents of the array were shifted to the right, as needed, and the item is stored at index position 0 within the array.

In the linked list implementation, a new node is created that contains the item, then the newly created node’s next variable and the list head are updated accordingly.

Add element into index position 1. Just like with the previous operation, some items in the the list will conceptually shift to the right.

Remember, myList could refer to either an ArrayBasedList or a LinkedBasedList¶

myList.add(1, "Milk");
System.out.println("List Size: " + myList.size());
System.out.println("List Contents: " + myList.makeString(","));

List Size: 3
List Contents: Cheese, Milk, Bread

In the array list implementation, only the elements in indices 1 and greater are shifted to the right before the item is stored at index position 1 within the array.

In the linked list implementation, a new node is created that contains the item, then the next variable of both the newly created node and the node referred to by head are updated accordingly.

Add element into index position 3. In this example, this conceptually places the item at the end of the list.
Remember, myList could refer to either an ArrayBasedList or a LinkedBasedList¶
```
myList.add(3, "Ice Cream");
System.out.println("List Size: " + myList.size());
System.out.println("List Contents: " + myList.makeString(","));
```
```
List Size: 4
List Contents: Cheese, Milk, Bread, Ice Cream
```
In the array list implementation, the internal array capacity needed to be increased before the item could be stored at index position 3 within the array.

In the linked list implementation, a new node is created that contains the item, then the next` variable of the node in list position 2 is updated accordingly.

8.4.3. Operation 3: Remove an Element¶

Remove the first element. Remember, the remove operation will shift any subsequent elements in the list to the left (i.e. subtracts one from their indices).
Remember, myList could refer to either an ArrayBasedList or a LinkedBasedList¶
```
System.out.println("Removed: " + myList.remove(0));
System.out.println("List Size: " + myList.size());
System.out.println("List Contents: " + myList.makeString(","));
```
```
Removed: Cheese
List Size: 3
List Contents: Milk, Bread, Ice Cream
```
In the array list implementation, the contents of the array at index position 1 and greater were shifted to the left by one position.

In the linked list implementation, head is simply assigned a reference to the node that was previously referred to by the next variable in the first node.

8.4.4. Operation 4: Get an Element¶

Get the first element. After all the changes to the list, we expect "Milk" to be the first item in the list.

System.out.println("Item at index 0: " + myList.get(0));
System.out.println("List Size: " + myList.size());
System.out.println("List Contents: " + myList.makeString(","));

Item at index 0: Milk
List Size: 3
List Contents: Milk, Bread, Ice Cream

In the array list implementation, no changes are needed internally to accommodate this operation. That location in the array can be accessed directly.

In the linked list implementation, no changes are needed internally to accommodate this operation. That location cannot be accessed directly; it must be reached starting with the node referred to by head.

8.4.5. Operation 5: Clear the List¶

After a list is cleared, it conceptually has no items.

Test Yourself

Write down what you expect the following code to output:

Remember, myList could refer to either an ArrayBasedList or a LinkedBasedList¶

myList.clear();
System.out.println("List Size: " + myList.size());
System.out.println("List Contents: " + myList.makeString(","));

In the array list implementation, the size is updated to 0. It’s up to the implementer whether or not the contents of the array are modified since the user of the list does not interact with them directly.

In the linked list implementation, the size is updated to 0 and the head is set to null.