In a circular doubly-linked list, the previous reference of the first node points to the last node, and the next reference of the last node points to the first node. Change the doubly-linked list implementation of Worked Example 16.1 into a circular list. You should remove the last instance variable because you can reach the last element as first.previous.

Data from worked example 16.1.

Transcribed Image Text:

WORKED EXAMPLE 16.1 Implementing a Doubly-Linked List Problem Statement Provide two enhancements to the linked list implementation from Section 16.1 so that it is a doubly-linked list. In a doubly-linked list, each node has a reference to the node preceding it, so we will add an instance variable previous: class Mode { public Object data; public Mode next; public Node previous; } We will also add a reference to the last node, which speeds up adding and removing elements at the end of the list: public class Linked List ( private Mode first; private Mode last; } We need to revisit all methods of the Linked List and ListIterator classes to make sure that these instance variables are properly updated. We will also add methods to add, remove, and get the last element. } Changes in the Linked List Class In the constructor, we simply add an initialization of the last instance variable: public Linked List() { first = null; last = null;