to each node in the DLL. Since the access to an element in an array-based list is O(1),
this will allow the users of IDLL to enjoy the benefits of fast access, and at the same time,
use a list implementation which does not waste memory given that it may shrink or grow
dynamically, a property which is known to be one of the advantages of linked-lists in general.
The way faster access is achieved is that the get(int i) operation, in its implementation,
rather than starting from the head of the list and traversing each node until the i-th node is
reached, it simply uses the get(int i) operation of an array-based list or index called indices
which it maintains, together with the other data fields.
This does come at a price though. We need more memory to store the array-based list
indices for one thing. Another is that all the operations of IDLL will have to maintain
the indices up to date. For example, whenever a new element is added to the DLL, the
array-based indices will have to be updated by inserting the new reference.
You are requested to implement a class IDLList<E> that encodes Indexed DLLs, following
the guidelines presented in the next section.
2
.1 Design of the Class IDLList<E>
2.1.1 The Inner Class Node<E>
First of all, an inner class Node<E> should be declared. This class should include three data
fields:
•
•
•
E data
Node<E> next
Node<E> prev
It should also include the following operations:
•
•
Node (E elem), a constructor that creates a node holding elem.
Node (E elem, Node<E> prev, Node<E> next), a constructor that creates a node holding
elem, with next as next and prev as prev.
2.1.2 The Class IDLList<E>
The class IDLList<E> should include the declaration of this inner private class Node<E>. Apart
from that, it should have four data fields:
•
•
•
•
Node<E> head
Node<E> tail
int size
ArrayList<Node<E>> indices
2