Exposing Node?
- Understand the potential risks of exposing the Node inner class.
Consider the following operation which we have explored earlier:
public void delete(Node<T> target) { }
public void insertAfter(Node<T> target, T data) { }
public void insertBefore(Node<T> target, T data) { }
Exercise How does one get a reference to a node in an arbitrarily position among the nodes in a DLL?
Solution
We can update the get
method to return a reference to a node at the target position.
- public T get(int index) { }
+ public Node<T> get(int index) { }
We can also update the following methods to return a reference to a newly inserted node.
- public void addFirst (T data) { }
+ public Node<T> addFirst (T data) { }
- public void addLast(T data) { }
+ public Node<T> addLast(T data) { }
Exercise Is there any benefit in, e.g., having get
to return a Node and later pass this node to a method like insertAfter
in contrast to having a method like insertAfter
to recieve the target's position index?
Solution
Imagine this contrived example:
Node<T> node = get(3);
insertAfter(node, 4);
insertBefore(node, 2);
delete(node);
In contrast to:
insertAfter(3, 4);
insertBefore(3, 2);
delete(3);
In the first snippet, the $$\Omicron(n)$$ search to find the node at index 3 happens once when we call get
. On the other hand, in the secon snippet, the linear search happens for each operation.
When we use Node
as a type in the signature of any public operations (such as delete
), we must also make Node
available (change it from private
to a public
static nested class).
Exercise What are the potential risks of exposing Node
to clients of DLL?
Solution
A deviant client can change the value stored at a node and change the next
/prev
pointers. The latter will corrupt the data structure.