Register

# 17.13. Lists¶

## 17.13.1. Lists¶

### 17.13.1.1. Lists¶

A list is a finite, ordered sequence of data items.

Important concept: List elements have a position.

Notation: $<a_0, a_1, …, a_{n-1}>$

What operations should we implement?

### 17.13.1.2. List Implementation Concepts¶

Our list implementation will support the concept of a current position.

Operations will act relative to the current position.

$<20, 23\ |\ 12, 15>$

List: $<12\ |\ 32, 15>$

L.insert(99);

Result: $<12\ |\ 99, 32, 15>$

Iterate through the whole list:

for (L.moveToStart(); !L.isAtEnd(); L.next()) {
it = L.getValue();
doSomething(it);
}

for (L.moveToStart(); !L.isAtEnd(); L.next()) {
it = L.getValue();
doSomething(it);
}


### 17.13.1.7. List Find Function¶

// Return true if k is in list L, false otherwise
static boolean find(List L, Object k) {
for (L.moveToStart(); !L.isAtEnd(); L.next())
if (k == L.getValue()) return true; // Found k
}

// Return true if k is in list L, false otherwise
static boolean find(List<Integer> L, int k) {
for (L.moveToStart(); !L.isAtEnd(); L.next()) {
if (k == L.getValue()) {
return true; // Found k
}
}
}


### 17.13.1.8. Array-Based List Class (1)¶

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

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


Settings

Saving...
Server Error
Resubmit

Settings

Saving...
Server Error
Resubmit

Settings

Saving...
Server Error
Resubmit

Settings

Saving...
Server Error
Resubmit

Settings

Saving...
Server Error
Resubmit

Settings

Saving...
Server Error
Resubmit

### 17.13.1.17. Removal¶

Settings

Saving...
Server Error
Resubmit

• Container classes store elements. Those take space.

• Container classes also store additional space to organize the elements.

### 17.13.1.20. Comparison of Implementations¶

• Array-Based Lists:
• Insertion and deletion are $\Theta(n)$.

• Prev and direct access are $\Theta(1)$.

• Array must be allocated in advance.

• No overhead if all array positions are full.

• Insertion and deletion are $\Theta(1)$.

• Prev and direct access are $\Theta(n)$.

• Space grows with number of elements.

### 17.13.1.21. Space Comparison¶

“Break-even” point:

$DE = n(P + E)$

$n = \frac{DE}{P + E}$

E: Space for data value.

P: Space for pointer.

D: Number of elements in array.

### 17.13.1.22. Space Example¶

• Array-based list: Overhead is one pointer (8 bytes) per position in array – whether used or not.

• Data is the same for both.

• When is the space the same?

• When the array is half full

### 17.13.1.23. Freelist¶

System new and garbage collection are slow.

Settings

Saving...
Server Error
Resubmit

Settings

Saving...
Server Error
Resubmit