CODEWITHSUNDEEP
javasingly-linked-list
Kashfi
Kashfi

Reputation: 46

For addHead method why check if tail == null?

I'm taking a Java data structures course and currently studying singly linked list. In the method for addHead, why do we need to check if the tail == null? And when true, why is tail = head?

public void addHead(T d){
  Node<T> n = new Node<>(d, head);
  head = n;
  size++
  if(tail == null)
   tail = head;
}

Full code here: https://venus.cs.qc.cuny.edu/~ryba/cs313/linkedList/LinkedList.java

Upvotes: 0

Views: 931

Answers (2)

Istador
Istador

Reputation: 173

In head is a reference to the first node in the list.
In tail is a reference to the last node in the list.
(The tail reference is used to allow adding elements to the end of the list in constant time.)

A empty list has head == null and tail == null.
A list with one element has head == tail, head != null and tail != null.
Lists with more than one element have head != tail, head != null and tail != null.

addHead creates a new Node n for the new element d, with a reference to the next node in the list that is stored in head (which is null for the first element). The head is assigned the reference to that newly created node n.

The if(tail == null) is true, when adding the first element to the list. The reference to n was already saved in head and also needs to be saved in tail with tail = head; (also possible: tail = n;) to fulfill the head == tail condition.

When adding additional elements to the head of the list (addHead), then tail isn't changed, but should continue to point to the last node of the list.

Upvotes: 1

Thilo
Thilo

Reputation: 262824

Your list implementation also allows appending to the end.

To make this work efficiently, the list maintains a tail pointer to its last element. It is possible to do it without that pointer, but then you'd need to go through the whole list to find the last element everytime, making appending O(N) instead of O(1). For the same reason, your implementation also has a size counter.

When you add a new element to a previously empty list that tail pointer needs to be adjusted to point at the newly created single node.

Note that when adding to the front of the list, you only have to adjust the tail when the list was empty before. In all other cases, the tail stays where it was, and only the head and size change.

Upvotes: 1

Related Questions