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)¶
2.1.1.4. List ADT (2)¶
2.1.1.5. List ADT (3)¶
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<Integer> L, int 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<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
2.1.1.10. Link Class¶
Dynamic allocation of new list elements.
class Link<E> { // Singly linked list node class private E e; // Value for this node private Link<E> n; // Point to next node in list // Constructors Link(E it, Link<E> inn) { e = it; n = inn; } Link(Link<E> inn) { e = null; n = inn; } E element() { return e; } // Return the value E setElement(E it) { return e = it; } // Set element value Link<E> next() { return n; } // Return next link Link<E> setNext(Link<E> inn) { return n = inn; } // Set next link }
2.1.1.13. Linked List Position (3)¶
We will add list header and list trailer nodes. This eliminates all the special cases.
2.1.1.14. Design Principle: Design to Avoid Special Cases¶
Adding list header/trailer nodes add a little space and (simple) code to the list class constructor.However, adding them avoids dealing with special cases that potentially involve bug-prone codeAvoids writing code for most special cases when inserting into empty list, at head of list, or at end of list.Avoids writing code for most special cases when deleting first, last, or only element in list.
2.1.1.20. 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.21. 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.22. 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.23. 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.24. Freelist¶
2.1.1.25. Doubly Linked Lists¶
2.1.1.26. Doubly Linked Node (1)¶
class Link<E> { // Doubly linked list node private E e; // Value for this node private Link<E> n; // Pointer to next node in list private Link<E> p; // Pointer to previous node // Constructors Link(E it, Link<E> inp, Link<E> inn) { e = it; p = inp; n = inn; } Link(Link<E> inp, Link<E> inn) { p = inp; n = inn; } // Get and set methods for the data members public E element() { return e; } // Return the value public E setElement(E it) { return e = it; } // Set element value public Link<E> next() { return n; } // Return next link public Link<E> setNext(Link<E> nextval) { return n = nextval; } // Set next link public Link<E> prev() { return p; } // Return prev link public Link<E> setPrev(Link<E> prevval) { return p = prevval; } // Set prev link }
