Given the Node class implementation, select one of the following that…

2024

Given the Node class implementation, select one of the following that correctly inserts a node at the tail of the list.

public class Node

{

protected int data;

protected Node prev;

protected Node next;

public Node(int data)

{

this.data = data;

prev = null;

next = null;

}

public Node(int data, Node prev, Node next)

{

this.data = data;

this.prev = prev;

this.next = next;

}

public int getData()

{

return data;

}

public void setData(int data)

{

this.data = data;

}

public Node getPrev()

{

return prev;

}

public void setPrev(Node prev)

{

this.prev = prev;

}

public Node getNext()

{

return next;

}

public void setNext(Node next)

{

this.next = next;

}

}

public class DLL

{

protected Node head;

protected Node tail;

int length;

public DLL()

{

head = new Node(Integer.MIN_VALUE,null,null);

tail = new Node(Integer.MIN_VALUE,null,null);

head.setNext(tail);

tail.setPrev(head);

length = 0;

}

}

  1. A.

    public void insertRear(int data)

    {

    Node node = new Node(data,tail.getPrev(),tail);

    node.getPrev().setNext(node);

    tail.setPrev(node);

    length++;

    }

  2. B.

    public void insertRear(int data)

    {

    Node node = new Node(data,tail.getPrev(),tail);

    node.getPrev().getPrev().setNext(node);

    tail.setPrev(node);

    length++;

    }

  3. C.

    public void insertRear(int data)

    {

    Node node = new Node(data,tail.getPrev(),tail);

    node.setNext(tail);

    tail.setPrev(node);

    length++;

    }

  4. D.

    public void insertRear(int data)

    {

    Node node = new Node(data,tail,tail.getPrev());

    node.getPrev().setNext(node);

    tail.setPrev(node);

    length++;

    }

Attempted by 1 students.

Show answer & explanation

Correct answer: A

Concept: In a doubly linked list that uses a sentinel tail node, inserting a node “at the rear” means splicing it in between the current last real node (tail.getPrev()) and the sentinel tail itself. Because every node carries both a next and a prev reference, a correct insertion must update BOTH links: the old last node's next must point to the new node, AND the sentinel's prev must point to the new node. Skipping or misdirecting either update breaks the agreement between forward and backward traversal. The constructor establishes this sentinel linkage in both directions — head.setNext(tail) and tail.setPrev(head) — so even on an EMPTY list, tail.getPrev() correctly returns head, letting the same splice logic handle the very first insertion consistently.

Application: The new node is created as new Node(data, tail.getPrev(), tail), so its own prev/next are already correct — pointing at the current last node and at the sentinel respectively. What remains is to make the SURROUNDING nodes point back at it:

  1. The node held by node.getPrev() — the old last real node — must have its next updated to the new node. Calling node.getPrev().setNext(node) does exactly this.

  2. The sentinel's prev must be updated to the new node. Calling tail.setPrev(node) does exactly this.

Both updates together correctly splice the new node in immediately before tail.

Cross-check: Trace it on a small list — sentinels head, tail plus one real node X. Before insertion, tail.getPrev() is X. After node.getPrev().setNext(node), X's next becomes the new node (it was tail). After tail.setPrev(node), tail's prev becomes the new node. Walking forward from head: head → X → new node → tail. Walking backward from tail: tail → new node → X → head. Both directions agree, confirming the splice is correct.

Base case: On an initially empty list, tail.getPrev() is head (per the constructor linkage above). Tracing option 0: node.getPrev().setNext(node) becomes head.setNext(node) — head's next changes from tail to the new node — and tail.setPrev(node) updates tail's prev to the new node. Walking forward: head → new node → tail. Walking backward: tail → new node → head. The same splice logic is consistent for the very first insertion too, not just for a list that already has a real node.

The implementations that instead call node.getPrev().getPrev().setNext(node) reach one node further back than the true predecessor, so THAT node’s next gets redirected to the new node instead — the true last node itself becomes an orphan in forward traversal (it is still linked backward via the new node’s own prev, but nothing forward-facing points into it any more), even though tail.getPrev() was updated to the new node. The implementation that never calls setNext on the predecessor at all leaves the old last node still pointing forward to tail, so the new node itself is unreachable by forward traversal. The implementation that swaps the constructor’s prev/next arguments gives the new node itself the wrong neighbours from the very start, before any pointer updates even run.

Explore the full course: Amcat Preparation