7.1. Array-Based List Implementation¶
7.1.1. Array-Based List Implementation¶
Here is an implementation for the array-based list, named AList.
AList inherits from the List ADT,and so must implement all of the member functions of List.
// Array-based list implementation
class AList<E> implements List<E> {
private E listArray[]; // Array holding list elements
private static final int DEFAULT_SIZE = 10; // Default size
private int maxSize; // Maximum size of list
private int listSize; // Current # of list items
private int curr; // Position of current element
// Constructors
// Create a new list object with maximum size "size"
@SuppressWarnings("unchecked") // Generic array allocation
AList(int size) {
maxSize = size;
listSize = curr = 0;
listArray = (E[])new Object[size]; // Create listArray
}
// Create a list with the default capacity
AList() { this(DEFAULT_SIZE); } // Just call the other constructor
public void clear() // Reinitialize the list
{ listSize = curr = 0; } // Simply reinitialize values
// Insert "it" at current position
public boolean insert(E it) {
if (listSize >= maxSize) return false;
for (int i=listSize; i>curr; i--) // Shift elements up
listArray[i] = listArray[i-1]; // to make room
listArray[curr] = it;
listSize++; // Increment list size
return true;
}
// Append "it" to list
public boolean append(E it) {
if (listSize >= maxSize) return false;
listArray[listSize++] = it;
return true;
}
// Remove and return the current element
public E remove() throws NoSuchElementException {
if ((curr<0) || (curr>=listSize)) // No current element
throw new NoSuchElementException("remove() in AList has current of " + curr + " and size of "
+ listSize + " that is not a a valid element");
E it = listArray[curr]; // Copy the element
for(int i=curr; i<listSize-1; i++) // Shift them down
listArray[i] = listArray[i+1];
listSize--; // Decrement size
return it;
}
public void moveToStart() { curr = 0; } // Set to front
public void moveToEnd() { curr = listSize; } // Set at end
public void prev() { if (curr != 0) curr--; } // Move left
public void next() { if (curr < listSize) curr++; } // Move right
public int length() { return listSize; } // Return list size
public int currPos() { return curr; } // Return current position
// Set current list position to "pos"
public boolean moveToPos(int pos) {
if ((pos < 0) || (pos > listSize)) return false;
curr = pos;
return true;
}
// Return true if current position is at end of the list
public boolean isAtEnd() { return curr == listSize; }
// Return the current element
public E getValue() throws NoSuchElementException {
if ((curr < 0) || (curr >= listSize)) // No current element
throw new NoSuchElementException("getvalue() in AList has current of " + curr + " and size of "
+ listSize + " that is not a a valid element");
return listArray[curr];
}
//Tell if the list is empty or not
public boolean isEmpty() {
return listSize == 0;
}
}
// Array-based list implementation
class AList implements List {
private Object listArray[]; // Array holding list elements
private static final int DEFAULT_SIZE = 10; // Default size
private int maxSize; // Maximum size of list
private int listSize; // Current # of list items
private int curr; // Position of current element
// Constructors
// Create a new list object with maximum size "size"
AList(int size) {
maxSize = size;
listSize = curr = 0;
listArray = new Object[size]; // Create listArray
}
// Create a list with the default capacity
AList() { this(DEFAULT_SIZE); } // Just call the other constructor
public void clear() // Reinitialize the list
{ listSize = curr = 0; } // Simply reinitialize values
// Insert "it" at current position
public boolean insert(Object it) {
if (listSize >= maxSize) return false;
for (int i=listSize; i>curr; i--) // Shift elements up
listArray[i] = listArray[i-1]; // to make room
listArray[curr] = it;
listSize++; // Increment list size
return true;
}
// Append "it" to list
public boolean append(Object it) {
if (listSize >= maxSize) return false;
listArray[listSize++] = it;
return true;
}
// Remove and return the current element
public Object remove() throws NoSuchElementException {
if ((curr<0) || (curr>=listSize)) // No current element
throw new NoSuchElementException("remove() in AList has current of " + curr + " and size of "
+ listSize + " that is not a a valid element");
Object it = listArray[curr]; // Copy the element
for(int i=curr; i<listSize-1; i++) // Shift them down
listArray[i] = listArray[i+1];
listSize--; // Decrement size
return it;
}
public void moveToStart() { curr = 0; } // Set to front
public void moveToEnd() { curr = listSize; } // Set at end
public void prev() { if (curr != 0) curr--; } // Move left
public void next() { if (curr < listSize) curr++; } // Move right
public int length() { return listSize; } // Return list size
public int currPos() { return curr; } // Return current position
// Set current list position to "pos"
public boolean moveToPos(int pos) {
if ((pos < 0) || (pos > listSize)) return false;
curr = pos;
return true;
}
// Return true if current position is at end of the list
public boolean isAtEnd() { return curr == listSize; }
// Return the current element
public Object getValue() throws NoSuchElementException {
if ((curr < 0) || (curr >= listSize)) // No current element
throw new NoSuchElementException("getvalue() in AList has current of " + curr + " and size of "
+ listSize + " that is not a a valid element");
return listArray[curr];
}
// Check if the list is empty
public boolean isEmpty() { return listSize == 0; }
}
// Array-based list implementation
class AList : public List {
ListItemType* listArray; // Array holding list elements
static const int DEFAULT_SIZE = 10; // Default size
int maxSize; // Maximum size of list
int listSize; // Current # of list items
int curr; // Position of current element
public:
// Constructors
// Create a new list object with maximum size "size"
AList(int size = DEFAULT_SIZE) : listSize(0), curr(0) {
maxSize = size;
listArray = new ListItemType[size]; // Create listArray
}
~AList() { delete [] listArray; } // destructor to remove array
// Reinitialize the list
void clear() { listSize = curr = 0; } // Simply reinitialize values
// Insert "it" at current position
bool insert(const ListItemType& it) {
if (listSize >= maxSize) return false;
for (int i = listSize; i > curr; i--) // Shift elements up
listArray[i] = listArray[i-1]; // to make room
listArray[curr] = it;
listSize++; // Increment list size
return true;
}
// Append "it" to list
bool append(const ListItemType& it) {
if (listSize >= maxSize) return false;
listArray[listSize++] = it;
return true;
}
// Remove and return the current element
ListItemType remove() {
if ((curr < 0) || (curr >= listSize)) // No current element
throw std::out_of_range("remove() in AList has current of " + to_string(curr) + " and size of "
+ to_string(listSize) + " that is not a a valid element");
ListItemType it = listArray[curr]; // Copy the element
for(int i = curr; i < listSize-1; i++) // Shift them down
listArray[i] = listArray[i+1];
listSize--; // Decrement size
return it;
}
void moveToStart() { curr = 0; } // Set to front
void moveToEnd() { curr = listSize; } // Set at end
void prev() { if (curr != 0) curr--; } // Move left
void next() { if (curr < listSize) curr++; } // Move right
int length() { return listSize; } // Return list size
int currPos() { return curr; } // Return current position
// Set current list position to "pos"
bool moveToPos(int pos) {
if ((pos < 0) || (pos > listSize)) return false;
curr = pos;
return true;
}
// Return true if current position is at end of the list
bool isAtEnd() { return curr == listSize; }
// Return the current element
ListItemType getValue() {
if ((curr < 0) || (curr >= listSize)) // No current element
throw std::out_of_range("getvalue() in AList has current of " + to_string(curr) + + " and size of "
+ to_string(listSize) + " that is not a a valid element");
return listArray[curr];
}
// Check if the list is empty
bool isEmpty() { return listSize == 0; }
};
7.1.1.1. Insert¶
Because the array-based list implementation is defined to store list
elements in contiguous cells of the array, the insert, append,
and remove methods must maintain this property.
7.1.1.2. Insert Practice Exericse¶
7.1.2. Append and Remove¶
Removing an element from the head of the list is similar to insert in that all remaining elements must shift toward the head by one position to fill in the gap. If we want to remove the element at position \(i\), then \(n - i - 1\) elements must shift toward the head, as shown in the following slideshow.
In the average case, insertion or removal each requires moving half of the elements, which is \(\Theta(n)\).
7.1.2.1. Remove Practice Exericise¶
Aside from insert and remove, the only other operations that
might require more than constant time are the constructor and
clear.
The other methods for Class AList simply
access the current list element or move the current position.
They all require \(\Theta(1)\) time.
