LLab $13$ List Implementation

Goal

In this lab you will explore two implementations of the ADT list. The first implementation will use an array

and the second will use a linked structure. In both cases you will create new methods that work directly with the

implementations. You will implement a reverse method that will reverse the order of the items in the list.

You will also implement a cycle method that will move the first item in the list to the last position.

Resources

$$ Appendix A: Creating Classes from Other Classes

$$ Chapter $12$: Lists

$$ Chapter $13$: List Implementations That Use Arrays

$$ Chapter $14$: A List Implementation That Links Data

In javadoc directory

$$ ListInterface.html $$Interface documentation for the interface ListInterface

Java Files

$$ AList.java

$$ ArrayListExtensionsTest.java

$$ LList.java

$$ LinkedListExtensionsTest.java

$$ ListInterface.java

Introduction

As was seen in the last lab, a list is an ordered collection of elements supporting basic operations such as add

and remove. One way to implement a list is to use an array. The other standard implementation is a linked

structure. In this lab, you will take a working implementation of each basic type and create two new methods.

If you have not done so already, take a moment to examine the code in AList.java $.$

Consider the code that implements the add method.

public void add$($int newPosition, T newEntry$)\{$

checkInitialization$()$;

if $(($newPosition $>=1)$ && $($newPosition $<=$ numberOfEntries $+1))\{$

if $($newPosition $<=$ numberOfEntries$)\{$

makeRoom$($newPosition$)$;

$\}$

list$[$newPosition$]=$ newEntry;

numberOfEntries$++$;

ensureCapacity$()$; $//$ Ensure enough room for next add

$\}$ else $\{$

throw new IndexOutOfBoundsException$($

"Illegal position given to add operation."$)$;

$\}$

$\}//$ end add

Lab $13$ List Implementation$174$

$//$ Doubles the size of the array list if it is full.

private void ensureCapacity$()\{$

int capacity $=$ list.length $-1$;

if $($numberOfEntries $>=$ capacity$)\{$

int newCapacity $=2*$ capacity;

checkCapacity$($newCapacity$)$; $//$ Is capacity too big?

list $=$ Arrays.copyOf$($list$,$ newCapacity $+1)$;

$\}$

$\}//$ end ensureCapacity

$/**$ Makes room for a new entry at newPosition.

$*$ Precondition: $1<=$ newPosition $<=$ numberOfEntries$+1$;

$*$ numberOfEntries is list's length before addition.

$*$ checkInitialization has been called.

$*/$

private void makeRoom$($int newPosition$)\{$

assert $($newPosition $>=1)$ && $($newPosition $<=$ numberOfEntries $+1)$;

int newIndex $=$ newPosition;

int lastIndex $=$ numberOfEntries;

$//$ Move each entry to next higher index, starting at end of

$//$ array and continuing until the entry at newIndex is moved

for $($int index $=$ lastIndex; index $>=$ newIndex; index$--)\{$

list$[$index $+1]=$ list$[$index$]$;

$\}$

$\}//$ end makeRoom

Let's trace the last statement in the following code fragment.

AList x $=$ new AList$(5)$;

x$.$add$("$a$")$;

x$.$add$("$b$")$;

x$.$add$("$c$")$;

x$.$add$("$d$")$;

x$.$add$(2,"$x$")$;