Linked list implementation - follow-up

Question

Follow-up to this question as recommended.

Can this code be improved from an OOP paradigm perspective?

package JavaCollections;
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
 * Dlist using sentinel node
 * 
 * @author mohet01
 *
 * @param <T>
 */
public class DblyLinkList<T> implements Iterable<T>{
 /**
 * DListNode is a node in a DblyLinkList
 * 
 * @author mohet01
 *
 */
 private class DListNode<T> {
 /**
 * item references the item stored in the current node. prev references the
 * previous node in the DList. next references the next node in the DList.
 *
 * 
 */
 T item;
 DListNode<T> prev;
 DListNode<T> next;
 /**
 * DListNode() constructor.
 */
 DListNode() {
 this(null);
 }
 DListNode(T item) {
 this.item = item;
 this.prev = null;
 this.next = null;
 }
 @Override
 public boolean equals(Object obj) {
 return super.equals(obj);
 }
 }
 private class Itr implements Iterator<T>{
 private int currentPosition = 0; 
 private int lastRet = -1;
 @Override
 public boolean hasNext() {
 return currentPosition != size();
 }
 @Override
 public T next() throws NoSuchElementException {
 if (currentPosition > size()){
 throw new NoSuchElementException();
 }
 T next = get(currentPosition);
 lastRet = currentPosition;
 currentPosition++;
 return next; 
 } 
 @Override
 public void remove() throws NoSuchElementException{
 if(lastRet < 0 ){
 throw new IllegalStateException();
 }else{
 DblyLinkList.this.remove(currentPosition);
 lastRet = -1;
 }
 }
 }
 /**
 * head references the sentinel node.
 *
 * Being sentinel as part of implementation detail, will avoid null checks,
 * while performing mutable operations on list.
 * 
 * DO NOT CHANGE THE FOLLOWING FIELD DECLARATIONS.
 * 
 */
 private DListNode<T> head;
 private int size;
 /*
 * 
 * 
 * DblyLinkList invariants: 
 * 1) head != null. 
 * 2) For any DListNode x in a DblyLinkList, x.next != null. 
 * 3) For any DListNode x in a DblyLinkList, x.prev != null. 
 * 4) For any DListNode x in a DblyLinkList, if x.next == y, then y.prev == x.
 * 5) For any DListNode x in a DblyLinkList, if x.prev == y, then y.next == x.
 * 6) size is the number of DListNode's, NOT COUNTING the sentinel (referenced
 * by "head"), that can be accessed from the sentinel by a sequence of "next" references.
 */
 /**
 * DblyLinkList() constructor for an empty DblyLinkList.
 */
 public DblyLinkList() {
 this.head = new DListNode<T>();
 this.head.next = this.head;
 this.head.prev = this.head;
 }
 /**
 * DblyLinkList() constructor for a one-node DblyLinkList.
 */
 public DblyLinkList(T item) {
 this.head = new DListNode<T>();
 this.insertFront(item);
 }
 /**
 * Return the size of the linked list
 * @return
 */
 public int size(){
 return size;
 }
 void remove(int index) throws NoSuchElementException{
 if(index > size()){
 throw new NoSuchElementException();
 }
 DListNode<T> node;
 for (node = head; index-- > 0; node = node.next);
 node.item = null;
 node.prev.next = node.next;
 node.next.prev = node.prev;
 }
 /**
 * Inserts a non-sentinel node at front of the list.
 * 
 * @param item
 */
 public void insertFront(T item){
 DListNode<T> node = new DListNode<>(item);
 node.next = head.next;
 node.prev = head;
 node.next.prev = node;
 head.next = node;
 this.size++;
 }
 /**
 * Remove first non-sentinel node from the list.
 * Do not require size check before remove operation
 * 
 */
 public void removeFront(){
 head.next.next.prev = head;
 head.next = head.next.next;
 if(this.size() > 0){
 this.size--;
 }
 }
 public T get(int index) throws NoSuchElementException{
 if (index > size()) throw new NoSuchElementException();
 DListNode<T> node;
 for (node = head; index-- > 0; node = node.next);
 return node.item;
 }
 @Override
 public Iterator<T> iterator() {
 return new Itr();
 }
}

Answer 1

Bug

In the DblyLinkList(T) constructor, this.head = new DListNode<T>(); sets up a sentinel node with dangling, rather than self-referencing, next and prev pointers. Rather, you should take advantage of your default constructor:

public DblyLinkList(T item) {
 this();
 this.insertFront(item);
}

Poor performance scaling

Your iterator's next() calls get(currentPosition), and remove() calls remove(currentPosition), both of which work by traversing nodes starting from the head. These methods are going to get slower and slower as you move towards the tail of the list. They should both be O(1).

Error handling

removeFront() quietly does nothing if the list is already empty, in contrast to get(index), which throws NoSuchElementException.

Pointless overriding

DListNode has an equals() method that just calls super.equals(obj). You can just remove that code and inherit equals() from the superclass.

• overexchange: I have made the changes here just for reference.
• overexchange: Is encapulation taken care in this code?
• 200_success: DblyLinkList.remove() should probably be public. Other than that, it looks OK.
• overexchange: Can you please answer this linked question?

Answer 2

Only one thing to point out...

/**
 * head references the sentinel node.
 *
 * Being sentinel as part of implementation detail, will avoid null checks,
 * while performing mutable operations on list.
 * 
 * DO NOT CHANGE THE FOLLOWING FIELD DECLARATIONS.
 * 
 */
private DListNode<T> head;
private int size;

This comment sounds scary, which is why it's probably an indication of a potential weakness in your implementation. Comments lie, especially when they get outdated, or copied-and-pasted wrongly to other parts of your code. If I want to be even more particular, you are using the plural form here (head references and field declarations), so are you really referring to both head and size fields? What happens when someone changes them? If the code is improved upon, when can someone remove the comments?

• overexchange: comments refer about head

Answer 3

As far as OOP paradigm is to be considered, I do not see any problem with the implementation and as per my knowledge and experience of OOP, I can not find any mistake or make any suggestion for any improvement. Well, here are few pointers that I will consider if I will implement the same thing:

1. Naming Convention: DblyLinkList, DNode doesn't make sense to me. If I were you, I will be making them more readable e.g. DoublyLinkList etc.. But this is just my opinion.

2. Your default constructor DListNode(), you don't need to do this(null) as T item, prev and next are object members so these will be auto initialized as null, so I don't see any good reason to do this(null).

Well, these are just few things as per my humble opinion.

• overexchange: Please read this comment
• 200_success: In an empty list, the sentinel's next and prev pointers need to refer to itself. You can't leave them uninitialized to null.