Before we can use any linked list operations, we need to initialize the data structure and mark it as empty. Conceptually, this is when the head of the list is pointing to nothing. We can do this in Java by adding this logic in a constructor.

The following code snippet shows this. Notice that, once again, we use generics to hold the type of the items we want to store in the linked list:

public class LinkedList<V> {
  private LinkedListNode<V> head;
  public LinkedList() {
    head = null;
  }
}  

How can we add and remove items from the head of the list? Adding a node in a linked list requires a two pointer reassignment. On the new node, you set the next pointer to point to whatever the head pointer is assigned to. Then, you set the head pointer to point to this newly created node. This process is shown in Figure 2.6. Deleting from the front of the list is the reverse. You set the head pointer to point to the next pointer of the node at the old head. For completeness, you can set this next pointer to point to nothing:

To locate an item in a list, we need to traverse the entire list until we find the item we're searching or reach the end of the list. This can be done easily by starting at the head pointer and always following the node's next pointer until you either find the node with the value you're looking for or you run out of nodes. For example, the next pointer is a null one.

The following code snippet shows the addFront() and deleteFront() operations for a linked list. For the addFront() method, we simply create a new node with its next pointer set as the current head pointer. Then, we assign the head to the new node. Notice in the delete method how we make use of Java's Optional objects. If the head pointer is null, it will stay null and we don't change anything. Otherwise, we flatten it to the next pointer. Finally, we set the first node's next pointer as null. This last step is not necessary since the orphaned node will be garbage collected; however, we're including it for completeness.

The code is as follows:

public void addFront(V item) {
  this.head = new LinkedListNode<>(item, head);
}
public void deleteFront() {
  Optional<LinkedListNode<V>> firstNode = Optional.
  ofNullable(this.head);
  this.head = firstNode.flatMap(LinkedListNode::getNext).
  orElse(null);
  firstNode.ifPresent(n -> n.setNext(null));
}  

The following code snippet shows one way to implement a find method. Again, observe how we make use of Java's Optional methods. We start a while loop from the head pointer and keep on moving to the next node as long as there is a node present and that node doesn't contain the item we're looking for. We then return the last pointer, which can be an empty optional or a node containing a match:

public Optional<LinkedListNode<V>> find(V item) {
  Optional<LinkedListNode<V>> node = Optional.ofNullable(this.head);

  while (node.filter(n -> n.getValue() != item).isPresent()) {
    node = node.flatMap(LinkedListNode::getNext);
  }
  return node;
}  

In the preceding example, we have shown how to add an item at the head of the list. How can we insert this into a linked list at an arbitrary point? Figure 2.7 shows how we can do this in two steps:

Snippet 2.18 shows how we can do this. It is a Java method called addAfter() accepting a node and an item to insert. The method adds a node, containing the item, after the aNode argument. The implementation follows the steps shown in Figure 2.7.

public void addAfter(LinkedListNode<V> aNode, V item) {
  aNode.setNext(new LinkedListNode<>(item, aNode.getNext().orElse(null)));
}