2.3. Lists¶
2.3.1. Lists¶
2.3.1.1. Lists, Stacks, Queues¶
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?
2.3.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>\)
2.3.1.3. List ADT (1)¶
// List class ADT. Generalize by using "Object" for the element type. // An alternative would be to use Java Generics. public interface List { // List class ADT // Remove all contents from the list, so it is once again empty public void clear(); // Insert "it" at the current location // The client must ensure that the list's capacity is not exceeded public boolean insert(Object it); // Append "it" at the end of the list // The client must ensure that the list's capacity is not exceeded public boolean append(Object it); // Remove and return the current element public Object remove();
2.3.1.4. List ADT (2)¶
// Set the current position to the start of the list public void moveToStart(); // Set the current position to the end of the list public void moveToEnd(); // Move the current position one step left, no change if already at beginning public void prev(); // Move the current position one step right, no change if already at end public void next(); // Return the number of elements in the list public int length();
2.3.1.5. List ADT (3)¶
// Return the position of the current element public int currPos(); // Set the current position to "pos" public boolean moveToPos(int pos); // Return true if current position is at end of the list public boolean isAtEnd(); // Return the current element public Object getValue(); }
2.3.1.6. List ADT Examples¶
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); }
2.3.1.7. List Find Function¶
// Return true if k is in list L, false otherwise static boolean find(List L, int k) { for (L.moveToStart(); !L.isAtEnd(); L.next()) if (k == (Integer)L.getValue()) return true; // Found k return false; // k not found }
2.3.1.8. Array-Based List Class (1)¶
class AList implements List { private Object listArray[]; // Array holding list elements private static final int defaultSize = 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(defaultSize); } // Just call the other constructor
2.3.1.10. Link Class¶
Dynamic allocation of new list elements.
class Link { // Singly linked list node class private Object e; // Value for this node private Link n; // Point to next node in list // Constructors Link(Object it, Link inn) { e = it; n = inn; } Link(Link inn) { e = null; n = inn; } Object element() { return e; } // Return the value Object setElement(Object it) { return e = it; } // Set element value Link next() { return n; } // Return next link Link setNext(Link inn) { return n = inn; } // Set next link }
2.3.1.13. Linked List Position (3)¶
2.3.1.19. Overhead¶
Container classes store elements. Those take space.
Container classes also store additional space to organize the elements.
- This is called overhead
The overhead fraction is: overhead/total space
2.3.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.
- Linked Lists:
- Insertion and deletion are \(\Theta(1)\).
- Prev and direct access are \(\Theta(n)\).
- Space grows with number of elements.
- Every element requires overhead.
2.3.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.
2.3.1.22. Space Example¶
- Array-based list: Overhead is one pointer (8 bytes) per position in array – whether used or not.
- Linked list: Overhead is two pointers per link node one to the element, one to the next link
- Data is the same for both.
- When is the space the same?
- When the array is half full
2.3.1.23. Freelist¶
2.3.1.24. Doubly Linked Lists¶
2.3.1.25. Container Class Design Issues¶
- Storing a record vs. Storing a reference to a record
- Homogeneity: Allow different record types? Check and block?
- Deletion: What happens to the record?
2.3.1.26. Doubly Linked Node (1)¶
class Link { // Doubly linked list node private Object e; // Value for this node private Link n; // Pointer to next node in list private Link p; // Pointer to previous node // Constructors Link(Object it, Link inp, Link inn) { e = it; p = inp; n = inn; } Link(Link inp, Link inn) { p = inp; n = inn; } // Get and set methods for the data members public Object element() { return e; } // Return the value public Object setElement(Object it) { return e = it; } // Set element value public Link next() { return n; } // Return next link public Link setNext(Link nextval) { return n = nextval; } // Set next link public Link prev() { return p; } // Return prev link public Link setPrev(Link prevval) { return p = prevval; } // Set prev link }
2.3.1.29. Stacks¶
LIFO: Last In, First Out.
Restricted form of list: Insert and remove only at front of list.
Notation:
- Insert: PUSH
- Remove: POP
- The accessible element is called TOP.
2.3.1.30. Stack ADT¶
public interface Stack { // Stack class ADT // Reinitialize the stack. public void clear(); // Push "it" onto the top of the stack public boolean push(Object it); // Remove and return the element at the top of the stack public Object pop(); // Return a copy of the top element public Object topValue(); // Return the number of elements in the stack public int length(); }
2.3.1.31. Array-Based Stack (1)¶
Issues:
- Which end is the top?
- Where does “top” point to?
- What are the costs of the operations?
2.3.1.32. Array-Based Stack (2)¶
class AStack implements Stack { private Object stackArray[]; // Array holding stack private static final int defaultSize = 10; private int maxSize; // Maximum size of stack private int top; // First free position at top // Constructors AStack(int size) { maxSize = size; top = 0; stackArray = new Object[size]; // Create stackArray } AStack() { this(defaultSize); }
2.3.1.33. Linked Stack¶
// Linked stack implementation class LStack implements Stack { private Link top; // Pointer to first element private int size; // Number of elements // Constructors LStack() { top = null; size = 0; } LStack(int size) { top = null; size = 0; }What are the costs of the operations?
How do space requirements compare to the array-based stack implementation?
2.3.1.34. Queues¶
FIFO: First in, First Out
Restricted form of list: Insert at one end, remove from the other.
Notation:
- Insert: Enqueue
- Delete: Dequeue
- First element: Front
- Last element: Rear
