LinkedList
From CS315
LinkedLists are a fundamental data structure in Java. They function as doubly-linked lists of Entries. Each Entry contains a value, a pointer to the previous Entry in the LinkedList, and a pointer to the next Entry. LinkedList extends AbstractSequentialList and implements the List<E>, Deque<E>, Cloneable, and Serializable interfaces.
Contents |
LinkedList
A LinkedList maintains four references:
- head - A pointer to the first Entry in the list, possibly a sentinel.
- tail - A pointer to the last Entry in the list, possibly a sentinel.
- size - The size of the list. Sentinels do not count towards size.
- mod count - A counter that is incremented anytime an Entry is added to or removed from the list. This is necessary because LinkedLists can have more than one iterator at a time. If one iterator adds or removes an Entry, all other iterators on this list are out of sync and must be removed, otherwise they may cause runtime errors.
While not required, many LinkedLists are implemented using a sentinel. Sentinels help avoid some of the complications that can arise from having an empty or single-element list. If a sentinel is used, the LinkedList's head and tail point to the sentinel. The sentinel's value is always set to null, since it merely serves as a placeholder. If the list is empty, the sentinel's previous and next simply point back to the sentinel itself. If the list contains only one element, the sentinel's previous and next both point to that element. If the list contains at least two elements, the sentinel's next points to the list's first element, and the sentinel's previous points to the list's last element. The first element's previous and the last element's next point to the sentinel.
In the absence of a sentinel, head simply points to the first Entry of the list, if any. Similarly, tail points to the last Entry in the list. If the list is empty, head and tail are set to null.
LinkedLists can be circular. In this case, the last Entry's next points the first entry, and the first entry's previous points to the last entry.
Basic Methods
add(int index, E e) - adds the given element at the specified index clear() - removes all elements from the list contains(Object o) - returns true if the list contains the specified element get(int index) - returns the element at the specified position listIterator(int index) - returns a ListIterator on this list, starting at the specified position remove(int index) - removes the element at the specified position remove(Object o) - removes the first occurence of the specified element, if any set(int index, E e) - replaces the element at the given index with the specified element size() - returns the size of this list
EntryIterator
EntryIterator is an inner class of LinkedList. It extends the Java API's ListIterator interface, which in turn implements the Iterator interface. ListIterators are a special kind of iterator because they can traverse lists in both ways. Therefore in addition to Iterator's hasNext(), next(), and remove() methods, the ListIterator interface has the following methods:
add(E e) - inserts the given element into the list hasPrevious() - returns true if the current element is preceded by another element nextIndex() - returns the index of the next Entry previous() - returns the element that precedes the current element previousIndex() - returns the index of the previous element set(E e) - replaces the last element returned by next() or previous() with the specified element
EntryIterator also maintains the following four references:
- nextEntry - A pointer to the Entry that will be returned by the next call to next().
- lastEntry - A pointer to the last Entry returned by the iterator.
- nextIndex - The index of the Entry that will be returned by the next call to next().
- expectedModCount - A counter that checks if this iterator is in sync with the list. If expectedModCount does not equal the list's modCount, this iterator is discarded. expectedModCount is incremented each time this iterator adds or removes an Entry.
When moving forward through the list, lastEntry trails nextEntry by one. When moving backwards through the list, lastEntry and nextEntry coincide.
Pros and Cons of LinkedList
Advantages
- No resizing necessary when adding or removing Entries
- Accessing the first and last elements are constant-time operations
- In the absence sentinels, LinkedLists can share tail elements
Disadvantages
- Accessing an arbitary element in the list is a linear-time operation
- LinkedLists have more references than ArrayLists, which requires extra memory space
References
Written by Alex Minssieux
