Linked Lists
Recursive Definition
A linked list is one of the following:
- A reference to a null value (an empty list)
- A reference to a node containing a content item and a reference to a linked list.
Construction
Nodes have this definition in Java:
private class Node
{
Item item;
Node next;
}
The Item can be a generic type or specialized for certains classes (e.g. Packet class holding Card objects).
Discussion questions
- Why is the Node class private?
- Why doesn't the Node class need methods?
- Does the Java compiler catch reference-point errors? How does this compare to Python (and other dynamically typed languages)?
- What is the cost of inserting any item at the beginning of the list? How does this compare to an array (i.e. a data structure of contiguously stored items)?