OOP paradigm implementation of a linked list

Question

Can this code be improved from an OOP paradigm perspective?

package JavaCollections;
import java.util.Iterator;
/**
 * Dlist using sentinel node
 * 
 * @author mohet01
 *
 * @param <T>
 */
public class DblyLinkList<T> implements Iterable<T>{
 /*
 * Representation - starts
 * 
 *
 */
 /**
 * 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.item = null;
 this.prev = null;
 this.next = null;
 }
 DListNode(T item) {
 this.item = item;
 this.prev = null;
 this.next = null;
 }
 }
 /**
 * 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 long size;
 private class Itr implements Iterator<T>{
 private DListNode<T> currentPosition; 
 public Itr(){
 currentPosition = head.next;
 }
 @Override
 public boolean hasNext() {
 return currentPosition.next != currentPosition;
 }
 @Override
 public T next() {
 currentPosition = currentPosition.next;
 return currentPosition.item;
 }
 }
 /*
 * Representation - end
 * 
 * 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.
 */
 /*
 * Interface - starts
 */
 /**
 * DblyLinkList() constructor for an empty DblyLinkList.
 */
 public DblyLinkList() {
 this.head = new DListNode<T>();
 this.head.item = null;
 this.head.next = this.head;
 this.head.prev = this.head;
 this.size = 0;
 }
 /**
 * DblyLinkList() constructor for a one-node DblyLinkList.
 */
 public DblyLinkList(T item) {
 this.head = new DListNode<T>();
 this.head.item = null;
 this.head.next = new DListNode<T>();
 this.head.next.item = item;
 this.head.prev = this.head.next;
 this.head.next.prev = this.head;
 this.head.prev.next = this.head;
 this.size = 1;
 }
 /**
 * 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.next.prev;
 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.item = null;
 head.next.next.prev = head;
 head.next = head.next.next;
 if(this.size > 0){
 this.size--;
 }
 }
 public T get(int index){ // index 1 is first element
 if (index <= size){ 
 DListNode<T> node = head; //sentinel node 
 while(index > 0){
 node = node.next; //linear search
 index--;
 }
 return node.item;
 }else{
 return null;
 }
 }
 @Override
 public Iterator<T> iterator() {
 return new Itr();
 }
}

DblyLinkList is a data abstraction which is nothing but a barrier between representation and usage (interface as mentioned).

Answer 1

Organization

I'd prefer to see the inner classes defined first. Having the head and size declarations in between the two inner classes makes the code less readable. (I think it's OK if the iterator references members that are declared further down.)

You don't have to write noisy comments like /* Representation */ and /* Interface */. The private and public modifiers already serve that purpose.

Iterator

The iterator is completely buggy! For any non-empty list, hasNext() will always return true. The first time you call next(), it will skip over the first item. Calling next() when the list is exhausted fails to trigger a NoSuchElementException as required by the Iterator contract.

I would expect remove() to be implemented, since that is one of the few things that a linked list excels at.

Implementation

The DListNode(T) constructor need not explicitly set prev and next to null; those are the default values. The DListNode() constructor should chain to the DListNode(T) constructor: DListNode() { this(null); }.

I think that you should expose the size via a size() method. Does size really need to be a long, though? Doubly-linked lists are quite horrible data structures in terms of space efficiency and traversal performance. I'd hate to imagine a list with 2³¹ elements being used.

In the DblyLinkList() constructor, you shouldn't set this.head.item to null, since the DListNode<T>() constructor already did that. You also don't need to explicitly set this.size = 0;.

The DblyLinkList(T) constructor should just be DblyLinkList(T item) { this(); this.insertFront(item); }. But I wouldn't even bother offering this second constructor at all, since it seems like such a useless special case.

In insertFront(), node.prev = head.next.prev; could just be node.prev = head;.

In removeFront(), you don't need to set head.next.item = null;, and furthermore I think you should treat the .item as immutable.

The get() method could be more succinctly written as:

public T get(int index) {
 if (index > size) return null;
 DListNode<T> node;
 for (node = head; index-- > 0; node = node.next);
 return node.item;
}

However, the one-based indexing in get() is non-idiomatic for Java, and returning null for indexes beyond the end instead of throwing an exception is unusual. Furthermore, you could traverse the list backwards when looking for an index that is in the latter half of the list. Otherwise, there is no point at all in writing a doubly-linked list — if the only operations you support are forward iteration, insertFront(), and removeFront(), then you would be better off with a singly-linked list.

• overexchange: Can you please provide comments on the modfications done here based on your answer?
• 200_success: Follow-up question