Linked List: A Dynamic Data Structure

  • Define what a linked list is.

A linked list is a linear data structure where each element is a separate object made of at least two items: the data and a reference to the next element. Conventionally, each element of a Linked List is called a node.

public class Node<E> {
  private E data;
  private Node<E> next;
  
  // we can have constructors, setters, getters, etc.
}

Here is a minimal implementation for a Linked List:

public class LinkedList<T> {
  private Node<T> head;
  
  // we can have constructors, methods to add/remove nodes, etc.
}
  • The entry point into a linked list is called the head of the list.
  • The head is not a separate node but a reference to the first node.
  • The last node has a reference to null.
  • If the list is empty, then the head is a null reference.
Aside: Java Reference vs. C/C++ Pointer

If you are here from Intermediate Programming, you may be wondering about C++ pointers. Java's reference variable plays a similar role to the C++ pointer. A Java variable of object type stores a reference to an object, which is just a pointer giving the address of that object in memory. When you use an object variable in a Java program, it automatically follows the pointer stored in that variable to find the actual object in memory. All this happens automatically, behind the scenes.

Resource