Linked list node implementation with maximum code reuse

Question

Currently as an exercise to practicing SOLID principles and basic data structures, I am trying to implement linked list type structures with as much code reuse as possible. Currently, I have:

package structures.linked; public class SingleNode<T> { private T data; private SingleNode<T> next; public SingleNode(T data, SingleNode<T> next) { this.data = data; this.next = next; } public T getData() { return data; } public void setData(T data) { this.data = data; } public SingleNode<T> getNext() { return next; } public void setNext(SingleNode<T> next) { this.next = next; } } 

and...

package structures.linked; public class DoubleNode<T> extends SingleNode<T> { private DoubleNode<T> prev; public DoubleNode(T data, DoubleNode<T> next, DoubleNode<T> prev) { super(data, next); this.prev = prev; } public DoubleNode<T> getPrev() { return prev; } public void setPrev(DoubleNode<T> prev) { this.prev = prev; } public DoubleNode<T> getNext() { return (DoubleNode<T>) super.getNext(); } public void setNext(DoubleNode<T> next) { super.setNext(next); } } 

It seems to me that getNext() inside of DoubleNode<T> is a violation of Liskov's substitution principle. Is this the case? Is there a better way to implement this while still reusing the code in SingleNode<T> and without breaking SOLID principles?

Answer 1

Don't use inheritance if it's just to write less code. Use inheritance if it makes sense to add behaviour to a valid base class.

Like you have noticed yourself you're violating Liskov's substitution principle. The easiest way for me to think about this is by imagining a method taking the base class as input:

public void doSomething(BaseClass mything)

If we then pass an instance of a subclass to that method:

BaseClass myActualThing = new SomeSubClass(); doSomething(myActualThing); 

Would that method notice anything different than if we had passed an actual instance of BaseClass?

The answer has to be no. It should have exactly the same methods as the BaseClass (I mean, the name, parameter types and return type. The implementation can of course differ).

---

In your case I'm wondering how you intend to use these nodes in an actual program.

If we take a quick look at the standard library we find the LinkedList class. Creating a list, adding/removing elements, getting an iterator, etc... are all called on this class. The internal representation of a list however, is a Node based.

Notice that this is the entire implementation of that internal Node class:

private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } } 

There's no difference in nodes with 2 links or 1 link. If it's the first node in a list it just means prev=null and if it's the last next=null.

All the case handling happens inside the LinkedList class.

It could be a fun exercise to write your own implementation of a linked list where you do handle special cases with specialised classes (be sure to implement the List and/or Deque interfaces). In that case I would start with a Node interface like J H suggested. This interface should contain ALL the methods you expect from a node (for example: hasNext(), hasPrevious(), add(), ...).

Then think about which cases you want to handle with different classes. (Like FirstNode, LastNode, DoublyLinkedNode, EmptyNode).

If there are methods that are the same for all of these classes you can choose to change the interface into an abstract class that implements those common methods. That way you reduce the amount of code you write in a way that actually makes sense.

---

Afterwards it could also be interesting to compare your implementation with the standard java LinkedList implementation. Notice which of their complex methods became easier in your implementation, and which things are super simple in their implementation but where you are struggling.

Answer 2

Usually linked lists keep most methods as private and the actual nodes cannot be accessed by the public API.

If you start implementing the different methods for adding, removing, etc. you might have on singly and doubly linked lists, you will find the implementations are quite different. So much so that I think it would be simpler to have two completely separate classes. They could both implement the java.util.List interface. I'm a huge fan of code reuse, but I don't think it's a good idea in this case. Trying to share some code between singly and doubly linked list would end up making the code less readable. This is just a guess since I have not actually tried implementing them.

Answer 3

Yes, it is the case, you are correct. A better way would use an interface.

You want to implement SingleNode in terms of a Node interface. The public API would accept Nodes (never SingleNodes), and would return Nodes. That gives DoubleNode's getNext() license to hand back a doubly linked object, which is a Node.