2.1. Lists¶
2.1.1. Lists¶
2.1.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?
2.1.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.1.1.3. List ADT (1)¶
// List class ADT. Generalize by using "Object" for the element type. 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() throws NoSuchElementException;
2.1.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.1.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() throws NoSuchElementException; public boolean isEmpty(); }
2.1.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.1.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 false; // k not found }
2.1.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// 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
2.1.1.9. Array-Based List Insert¶
2.1.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.1.1.11. Linked List Position (1)¶
2.1.1.12. Linked List Position (2)¶
2.1.1.13. Linked List Position (3)¶
2.1.1.14. Linked List Class (1)¶
2.1.1.15. Linked List Class (2)¶
2.1.1.16. Insertion¶
2.1.1.17. Removal¶
2.1.1.18. Prev¶
2.1.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.1.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.1.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.1.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.1.1.23. Freelist¶
2.1.1.24. Doubly Linked Lists¶
2.1.1.25. 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 }
