HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaMinor

Linked list implementation - follow-up

Submitted by: @import:stackexchange-codereview··
0
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

Solution

Bug

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.