20. Linked Lists
LinkedList is a List that has the ability to add items quickly on the front or back.
The linked list is like our familiar ArrayList, except that one can quickly add items anywhere in the list.
Summary: insertion at the first or last index is a constant time O(1) operation. Getting the first or last item from a list is also fast O(1). Getting items from the middle is a slower O(n) operation.
| operation \ location | first | middle | last |
|---|---|---|---|
| add | addFirst(e) | add(idx, e) | addLast(e) |
| get | getFirst() | get(idx) | getLast() |
| poll (get and remove) | pollFirst() | none | pollLast() |
These are the fundamentals. There are many more convenience operations; read the linked list documentation to learn them.