Java: Double Linked List which uses a sentinel node as zero element

Question

I have to implement a double linked list as an exercise for a further education.

There are three interfaces which have to be implemented:

IValueElement

package schnittstellen; // schnittstellen == interfaces
public interface IValueElement
{
 public String getName();
 public void setName (String paramName);
 public int getValue() ;
 public void setValue(int paramValue);
}

IListElement

package schnittstellen; 
public interface IListElement
{
 public IValueElement getValueElement();
 public void setValueElement(IValueElement value);
 public IListElement getPredecessor();
 public void setPredecessor (IListElement predecessor);
 public IListElement getSuccessor();
 public void setSuccessor (IListElement successor);
}

IList

package schnittstellen; 
public interface IList
{
 public IListElement getHead ( ) ;
 public void insertAtTheEnd(IValueElement value);
 public void insertAtPos(int pos , IValueElement value);
 public IValueElement getElementAt(int position);
 public int getFirstPosOf(IValueElement value);
 public void deleteFirstOf(IValueElement value);
 public void deleteAllOf(IValueElement value);
 public boolean member (IValueElement value);
 public void reverse();
 public String toString();
}

Requirements for the implementation of IList:

• Has a default constructor.

• Head of the list isn't allowed to become null.

• A dummy element has to used as 0th element of the list.

• The predecessor reference of the the head has to point to the last element of the list.

Here are my implementations of the interfaces:

Class IValueElement

package implementierung;
import schnittstellen.IValueElement;
public class ValueElement implements IValueElement
{
 private String name;
 private int value;
 public ValueElement(String name, int value) {
 if (name == null) {
 this.name = "";
 } else {
 this.name = name;
 }
 this.value = value;
 }
 public String getName() {
 return this.name;
 }
 public void setName(String paramName) {
 if (name == null) {
 this.name = "";
 } else {
 this.name = paramName;
 }
 }
 public int getValue() {
 return this.value;
 }
 public void setValue(int paramValue) {
 this.value = paramValue;
 }
 public String toString() {
 return "Name : " + this.name + ", "
 + "Value : " + this.value;
 }
}

Class IListElement

package implementierung;
import schnittstellen.IListElement;
import schnittstellen.IValueElement;
public class ListElement implements IListElement
{
 private IValueElement valueElement;
 private IListElement predecessor;
 private IListElement successor;
 public ListElement(IValueElement value) {
 if (value == null) {
 value = new ValueElement("", 0);
 } 
 this.valueElement = value;
 this.predecessor = null;
 this.successor = null;
 }
 public IValueElement getValueElement() {
 return this.valueElement;
 }
 public void setValueElement(IValueElement value) {
 if (value == null) {
 value = new ValueElement("", 0);
 } else {
 this.valueElement = value;
 }
 }
 public IListElement getPredecessor() {
 return this.predecessor;
 }
 public void setPredecessor (IListElement predecessor) { 
 this.predecessor = predecessor;
 }
 public IListElement getSuccessor() {
 return this.successor;
 }
 public void setSuccessor(IListElement successor) {
 this.successor = successor;
 }
}

Class List

package implementierung;
import schnittstellen.IList;
import schnittstellen.IListElement;
import schnittstellen.IValueElement;
public class List implements IList
{
 private IListElement head;
 private IListElement end;
 private int length;
 public List() {
 this.head = new ListElement(new ValueElement("Dummy", 0));
 this.end = this.head;
 this.length = 1;
 }
 public IListElement getHead() {
 return this.head;
 }
 private ListElement createListElement(IValueElement value) {
 if (value == null) {
 return new ListElement(new ValueElement("", 0));
 } else {
 return new ListElement(value);
 }
 }
 public void insertAtTheEnd(IValueElement value) { 
 ListElement newElement = createListElement(value);
 IListElement currentEnd = this.end;
 currentEnd.setSuccessor(newElement); 
 newElement.setPredecessor(currentEnd);
 this.end = newElement; 
 this.length++;
 }
 @Override
 public void insertAtPos(int pos , IValueElement value) {
 ListElement newElement = createListElement(value);
 if (pos <= 1) { 
 newElement.setSuccessor(this.head.getSuccessor());
 newElement.setPredecessor(this.head);
 this.head.setSuccessor(newElement);
 } else if (pos > this.length) {
 newElement.setSuccessor(null);
 newElement.setPredecessor(this.end);
 this.end = newElement;
 } else {
 IListElement currentElement = this.head;
 for (int i = 1; i <= pos; i++) {
 currentElement = currentElement.getSuccessor();
 if (i == pos) {
 IListElement predecessor = currentElement.getPredecessor(); 
 newElement.setPredecessor(predecessor);
 newElement.setSuccessor(currentElement);
 predecessor.setSuccessor(newElement);
 currentElement.setPredecessor(newElement);
 break;
 }
 }
 }
 this.length++;
 }
 public IValueElement getElementAt(int position) {
 if (position <= 0 || position > this.length) {
 return null;
 } else if (position == 1) {
 return this.head.getSuccessor().getValueElement();
 } else {
 IListElement ret = this.head;
 for (int i = 1; i < position; i++) {
 ret = ret.getSuccessor();
 }
 return ret.getSuccessor().getValueElement();
 }
 }
 public int getFirstPosOf(IValueElement value) {
 IListElement currentElement = this.head;
 int i = 1;
 while ((currentElement = currentElement.getSuccessor()) != null) { 
 IValueElement currentValueElement =
 currentElement.getValueElement();
 if (value == currentValueElement) {
 return i;
 }
 i++;
 }
 return -1;
 }
 public void deleteFirstOf(IValueElement value) {
 IListElement currentElement = this.head;
 while ((currentElement = currentElement.getSuccessor()) != null) {
 IValueElement currentValueElement =
 currentElement.getValueElement();
 if (value == currentValueElement) {
 IListElement predecessor = currentElement.getPredecessor();
 IListElement successor = currentElement.getSuccessor();
 predecessor.setSuccessor(successor);
 // Successor? => Then it is NOT the last element in the list.
 if (successor != null) {
 successor.setPredecessor(predecessor);
 } else {
 this.end = predecessor; // In case it's the last element in the list it becomes the new end.
 }
 this.length--;
 return;
 }
 }
 }
 public void deleteAllOf( IValueElement value) {
 IListElement currentElement = this.head.getSuccessor();
 while (currentElement != null) {
 IValueElement currentValueElement =
 currentElement.getValueElement();
 if (value == currentValueElement) {
 IListElement predecessor = currentElement.getPredecessor();
 IListElement successor = currentElement.getSuccessor();
 predecessor.setSuccessor(successor);
 if (successor != null) {
 successor.setPredecessor(predecessor);
 } else {
 this.end = predecessor;
 }
 currentElement = successor;
 this.length--;
 } else {
 currentElement = currentElement.getSuccessor();
 } 
 }
 }
 public boolean member (IValueElement value) {
 IListElement currentElement = this.head;
 while ((currentElement = currentElement.getSuccessor()) != null) {
 IValueElement currentValueElement =
 currentElement.getValueElement();
 if (value == currentValueElement) {
 return true;
 }
 }
 return false;
 }
 public void reverse() {
 IListElement currentElement = this.head.getSuccessor();
 IListElement currentNext = currentElement; 
 IListElement currentFirst = currentElement;
 while (currentNext != null) {
 currentNext = currentElement.getSuccessor();
 if (this.getHead() == currentElement.getPredecessor()) {
 currentElement.setSuccessor(null);
 currentElement.setPredecessor(currentNext);
 } else if (currentNext != null) {
 currentElement.setSuccessor(currentElement.getPredecessor());
 currentElement.setPredecessor(currentNext);
 } else {
 currentElement.setSuccessor(currentElement.getPredecessor());
 currentElement.setPredecessor(this.head);
 }
 currentElement = currentNext;
 }
 this.head.setSuccessor(this.end);
 this.head.setPredecessor(currentFirst);
 this.end = currentFirst;
 }
 @Override
 public String toString() {
 IListElement currentElement = this.head;
 String ret = "Head: " + this.head.getValueElement().getName() + ", "
 + this.head.getValueElement().getValue() + "\n";
 while ((currentElement = currentElement.getSuccessor()) != null) {
 IValueElement currentValueElement =
 currentElement.getValueElement();
 ret += currentValueElement.getName() + ", "
 + currentValueElement.getValue() + "\n";
 }
 return ret + "End: " + this.end.getValueElement().getName() + ", " +
 this.end.getValueElement().getValue() + "\n";
 }
}

Moreover I have made (voluntarily) a test Class. For trying out what I got so far.

package implementierung;
import schnittstellen.*;
public class ListTest
{
 public static void main (String[] args) {
 IList list = new List();
 IValueElement data01 = new ValueElement("K1", 10);
 IValueElement data02 = new ValueElement("K2", 20);
 IValueElement data03 = new ValueElement("K3", 30);
 IValueElement data04 = new ValueElement("K4", 40);
 IValueElement data05 = new ValueElement("K5", 50);
 list.insertAtTheEnd(data01);
 list.insertAtTheEnd(data02);
 list.insertAtTheEnd(data03);
 list.insertAtTheEnd(data04);
 list.insertAtTheEnd(data05);
 System.out.println(list.toString());
 // Testing reverse()
 list.reverse();
 System.out.println("After reverse --- \n" + list.toString());
 // Testing getHead()
 System.out.println(
 "Name of head element: "
 + list.getHead().getValueElement().getName() + "\n");
 // Testing getElementAt()
 System.out.println("At 2: " + list.getElementAt(2).getName());
 System.out.println("At 3: " + list.getElementAt(3).getName());
 System.out.println("At 5: " + list.getElementAt(5).getName());
 // Testing insertAtPos()
 IValueElement atPosN = new ValueElement("A-B", 99);
 list.insertAtPos(3, atPosN);
 // Testing insertAtTheEnd()
 IValueElement atTheEnd = new ValueElement("X-Y-Z", 100);
 list.insertAtTheEnd(atTheEnd);
 // Testing getElementAt() after additional insert
 System.out.println("After additional insert : ");
 System.out.println("At 2: " + list.getElementAt(2).getName());
 System.out.println("At 3: " + list.getElementAt(3).getName());
 System.out.println("At 5: " + list.getElementAt(5).getName());
 // Testing getFirstPosOf
 System.out.println("Element found at : " + list.getFirstPosOf(data03));
 System.out.println("Element found at : " + list.getFirstPosOf(atPosN));
 IValueElement test1 = new ValueElement("D-E-F", 10);
 System.out.println("Element found at : "
 + list.getFirstPosOf(test1) + "\n");
 System.out.println(list.toString());
 // Testing member()
 IValueElement notMember = new ValueElement("x-y", 12);
 System.out.println(list.member(atPosN));
 System.out.println(list.member(notMember));
 System.out.println(list.member(data03));
 // Testing deleteFirstOf() 
 System.out.println("\nTrying to delete K3 - \n");
 list.deleteFirstOf(data03);
 System.out.println(list.toString());
 // Testing deleteAllOf() 
 System.out.println("\nTrying to delete all of K2 - \n");
 list.insertAtTheEnd(data02); // Add data02 a second time.
 System.out.println(list.toString());
 list.deleteAllOf(data02);
 System.out.println(list.toString());
 }
}

I should mention that I've tried to implement everything based upon what I've understood in the corresponding lecture. I avoided to lookup the internet. Instead figured out everything myself to become more confident with these data structures.

I seems to work alright. But I'm sure there are flaws. Perhaps even errors.

So therefore: All hints, comments and suggestions concerning improvements highly welcomed.

• rolfl: For what it's worth, the technical English term for using a dummy head/tail element is called a "Sentinel". If you want to read more about it, there's Wikipedia: en.wikipedia.org/wiki/Sentinel_node
• michael.zech: Awesome resource. Very interesting indeed. Thanks a lot. :)

Answer 1

Advice 1: a bug

You reversal operation will enter an infinite loop on empty list. In order to remedy this, write

public void reverse() {
 if (length == 1) {
 // Otherwise, on empty list infinite loop.
 return;
 }
 IListElement currentElement = this.head.getSuccessor();
 IListElement currentNext = currentElement; 
 IListElement currentFirst = currentElement;
 ...
}

Advice 2

Also, it is kind of funny you count the sentinel element in your length. Better design was ignoring it and start counting only the actual elements. Furthermore, what you call "element" is actual is called list node.

Advice 3

Prepending an I to interface names is a C# convention, not a Java convention.

Advice 4

You can be more clear in your code by simply swapping the element/node data instead of restructuring the entire list:

public void reverseV2() {
 IListElement element1 = head.getSuccessor();
 IListElement element2 = end;
 while (head != end) {
 String tmpString = element1.getValueElement().getName();
 element1.getValueElement().setName(element2.getValueElement().getName());
 element2.getValueElement().setName(tmpString);
 int tmpInt = element1.getValueElement().getValue();
 element1.getValueElement().setValue(element2.getValueElement().getValue());
 element2.getValueElement().setValue(tmpInt);
 element1 = element1.getSuccessor();
 if (element1 == element2) {
 return;
 }
 element2 = element2.getPredecessor();
 if (element2 == element1) {
 return;
 }
 }
}

In overall, your code is pretty clear and well written.