4.4. Array-Based List Implementation¶
4.4.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 : public List {
ListItemType listArray[MAX_SIZE]; //Array holding list elements
int listSize; //Current number of list items
int curr; //Position of current element
public:
//Constructor
// Create a new list element with maximum size "MAX_SIZE"
AList() : listSize(0) {
//Initial the array
for (int k = 0; k < MAX_SIZE; k++) listArray[k] = 0;
} //end constructor
bool isEmpty() const {
return listSize == 0;
}
void clear() { // Reinitialize the list
listSize = curr = 0; // Simply reinitialize values
}
// Insert "it" at current position
bool insert(const ListItemType& it) {
if (listSize >= MAX_SIZE) 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 >= MAX_SIZE ) return false;
listArray[listSize++] = it;
return true;
}
// Remove and return the current element
ListItemType remove() {
if( (curr < 0) || (curr >= listSize) ) // No current element
return 0;
ListItemType it = listArray[curr]; // Copy the element
for (int i = curr; i < listSize; 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 to 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
return 0;
return listArray[curr];
}
};
// 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() {
if ((curr<0) || (curr>=listSize)) // No current element
return null;
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() {
if ((curr < 0) || (curr >= listSize)) // No current element
return null;
return listArray[curr];
}
// Check if the list is empty
public boolean isEmpty() { return listSize == 0; }
public String toString() {
StringBuffer out = new StringBuffer((listSize + 1) * 4);
out.append("< ");
for (int i = 0; i < curr; i++) {
out.append(listArray[i]);
out.append(" ");
}
out.append("| ");
for (int i = curr; i < listSize; i++) {
out.append(listArray[i]);
out.append(" ");
}
out.append(">");
return out.toString();
}
}
// 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
void clear() // Reinitialize the list
{ listSize = curr = 0; } // Simply reinitialize values
// Insert "it" at current position
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
boolean append(Object it) {
if (listSize >= maxSize) return false;
listArray[listSize++] = it;
return true;
}
// Remove and return the current element
Object remove() {
if ((curr<0) || (curr>=listSize)) // No current element
return null;
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;
}
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"
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
boolean isAtEnd() { return curr == listSize; }
// Return the current element
Object getValue() {
if ((curr < 0) || (curr >= listSize)) // No current element
return null;
return listArray[curr];
}
}
// 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() {
if ((curr<0) || (curr>=listSize)) // No current element
return null;
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() {
if ((curr < 0) || (curr >= listSize)) // No current element
return null;
return listArray[curr];
}
public String toString() {
StringBuffer out = new StringBuffer((listSize + 1) * 4);
out.append("< ");
for (int i = 0; i < curr; i++) {
out.append(listArray[i]);
out.append(" ");
}
out.append("| ");
for (int i = curr; i < listSize; i++) {
out.append(listArray[i]);
out.append(" ");
}
out.append(">");
return out.toString();
}
//Tell if the list is empty or not
public boolean isEmpty() {
return listSize == 0;
}
}
4.4.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.
4.4.1.2. Insert Practice Exericse¶
4.4.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)\).
4.4.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.
