patternjavaMinor
Linked list implementation - follow-up
Viewed 0 times
listimplementationlinkedfollow
Problem
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
*/
public class DblyLinkList implements Iterable{
/**
* DListNode is a node in a DblyLinkList
*
* @author mohet01
*
*/
private class DListNode {
/**
* 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 prev;
DListNode 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{
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 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.pre
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
*/
public class DblyLinkList implements Iterable{
/**
* DListNode is a node in a DblyLinkList
*
* @author mohet01
*
*/
private class DListNode {
/**
* 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 prev;
DListNode 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{
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 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.pre
Solution
Bug
In the
Poor performance scaling
Your iterator's
Error handling
Pointless overriding
In the
DblyLinkList(T) constructor, this.head = new DListNode(); 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.Code Snippets
public DblyLinkList(T item) {
this();
this.insertFront(item);
}Context
StackExchange Code Review Q#98593, answer score: 5
Revisions (0)
No revisions yet.