Singly linked list with generics and comparable data - corrected code

Question

I am currently reading about the thread-safe implementation of a linked list. I would like someone to point out some mistakes that will create issues if I try to make it thread-safe in the future.

I've corrected the buggy code from my original post.

Information:

1. Please review the SinglyLinkedList mainly.
2. You may point out any design issue in classes or suggest another function that should be implemented.
3. I have written the code for practice purpose only. I know its not Java-linked-list compatible.
4. I tried to apply all the test cases. Please don't answer if you found another bug; just mention it in a comment. I will introduced it in test cases then get reviewed.

SinglyLinkedList:

package com.atleyvirdee.myDataStructures.linkedlist.implemtations;

import com.atleyvirdee.myDataStructures.linkedlist.ILinkedList;
import com.atleyvirdee.myDataStructures.linkedlist.ILinkedListNode;
import com.atleyvirdee.myDataStructures.linkedlist.LinkedListerTraverser;

public class SinglyLinkedList<T extends Comparable<T>> implements ILinkedList<T> {

  ILinkedListNode<T>       root      = null;
  ILinkedListNode<T>       last      = null;
  int                      size      = 0;
  LinkedListerTraverser<T> traverser = new LinkedListerTraverser<T>(root, size);

  @Override
  public ILinkedListNode<T> getRoot() {
    return root;
  }

  @Override
  public LinkedListerTraverser<T> getTraverser() {
    traverser.setRoot(root, size);
    return traverser;
  }

  @Override
  public void prepend( T data ) {
    if ( this.root == null ) {
      append(data);
      return;
    }
    size++;
    ILinkedListNode<T> node = new NodeImpl<T>(data);
    node.setNext(this.root);
    this.root = node;
  }

  @Override
  public void append( T data ) {
    size++;
    ILinkedListNode<T> node = new NodeImpl<T>(data);
    if ( this.root == null ) {
      this.root = node;
      this.last = node;
      return;
    }
    this.last.setNext(node);
    this.last = node;
  }

  @Override
  public void remove( T data ) {
    ILinkedListNode<T> parent = null;
    ILinkedListNode<T> node = root;
    ILinkedListNode<T> child = root.getNext();
    if ( root != null && root.getData() == data ) {
      root = root.getNext();
      size--;
      return;
    }
    while (node.getData() != data) {
      if ( node.getNext() == null ) {
        return;
      }
      parent = node;
      node = node.getNext();
      child = node.getNext();
    }
    parent.setNext(child);
    node.setNext(null);
    size--;
  }

  @Override
  public void insertAfter( int index, T data ) {
    if ( index < 0 ) {
      throw new RuntimeException("Negative Index not accepted.");
    }
    if ( index > size ) {
      throw new RuntimeException("Out of Bound Exception.");
    }
    if ( index == 0 ) {
      this.prepend(data);
      return;
    }
    ILinkedListNode<T> node = root;
    while (node != null && index > 1) {
      index--;
      node = node.getNext();
    }
    size++;
    ILinkedListNode<T> newNode = new NodeImpl<T>(data);
    newNode.setNext(node.getNext());
    node.setNext(newNode);
  }

  @Override
  public T find( T data ) {
    ILinkedListNode<T> node = root;
    while (node != null) {
      if ( node.getData().compareTo(data) == 0 ) {
        return node.getData();
      }
      node = node.getNext();
    }
    return (node == null) ? null : node.getData();
  }

  @Override
  public int size() {
    return size;
  }


  class NodeImpl<E extends Comparable<E>> implements ILinkedListNode<E> {

    private ILinkedListNode<E> nextNode;
    private E                  data;

    public NodeImpl( E data ) {
      this.data = data;
    }

    @Override
    public ILinkedListNode<E> getNext() {
      return this.nextNode;
    }

    @Override
    public void setNext( ILinkedListNode<E> node ) {
      this.nextNode = node;
    }

    @Override
    public E getData() {
      return data;
    }

    @Override
    public void setData( E data ) {
      this.data = data;
    }
  }
}

Helper classes

Test cases

package com.atleyvirdee.myDataStructures.linkedlist;

import com.atleyvirdee.myDataStructures.linkedlist.implemtations.SinglyLinkedList;

public class LinkedListTester {

  public static void main( String[] args ) {





    // ============== APPEND TESTING =================//
    System.out.println("Test Case 1: Appending 1 element.");
    ILinkedList<Integer> LT = new SinglyLinkedList<Integer>();
    LT.append(1);
    LT.getTraverser().traverseList();
    if ( LT.size() != 1 ) {
      throw new RuntimeException("Error in Size.");
    };



    System.out.println("\n\n\n\n\nTest Case 2: Appending multiple element.");
    LT = new SinglyLinkedList<Integer>();
    LT.append(1);
    LT.append(2);
    LT.append(3);
    LT.append(4);
    LT.append(5);
    LT.getTraverser().traverseList();
    if ( LT.size() != 5 ) {
      throw new RuntimeException("Error in Size.");
    };




    System.out.println("\n\n\n\n\nTest Case 3: Null List");
    LT = new SinglyLinkedList<Integer>();
    LT.getTraverser().traverseList();
    if ( LT.size() != 0 ) {
      throw new RuntimeException("Error in Size.");
    };




    // ============== PREPEND TESTING =================//

    System.out.println("\n\n\n\n\nTest Case 4: Prepending 1 element.");
    LT = new SinglyLinkedList<Integer>();
    LT.prepend(1);
    LT.getTraverser().traverseList();
    if ( LT.size() != 1 ) {
      throw new RuntimeException("Error in Size.");
    };


    System.out.println("\n\n\n\n\nTest Case 5: Prepending many element.");
    LT = new SinglyLinkedList<Integer>();
    LT.prepend(5);
    LT.prepend(4);
    LT.prepend(3);
    LT.prepend(2);
    LT.prepend(1);
    LT.getTraverser().traverseList();
    if ( LT.size() != 5 ) {
      throw new RuntimeException("Error in Size.");
    };



    System.out.println("\n\n\n\n\nTest Case 6: prepend and append together.");
    LT = new SinglyLinkedList<Integer>();
    LT.append(4);
    LT.prepend(3);
    LT.append(5);
    LT.prepend(2);
    LT.append(6);
    LT.prepend(1);
    LT.append(7);
    LT.prepend(0);
    LT.getTraverser().traverseList();
    if ( LT.size() != 8 ) {
      throw new RuntimeException("Error in Size.");
    };




    // ============== REMOVE TESTING =================//
    System.out.println("\n\n\n\n\nTest Case 7: Remove some Element.");
    LT = new SinglyLinkedList<Integer>();
    LT.append(4);
    LT.append(3);
    LT.append(6);
    LT.append(7);
    LT.remove(3);
    LT.getTraverser().traverseList();
    if ( LT.size() != 3 ) {
      throw new RuntimeException("Error in Size.");
    };



    System.out.println("\n\n\n\n\nTest Case 8: Remove root element.");
    LT = new SinglyLinkedList<Integer>();
    LT.append(4);
    LT.remove(4);
    LT.getTraverser().traverseList();
    if ( LT.size() != 0 ) {
      throw new RuntimeException("Error in Size.");
    };



    System.out.println("\n\n\n\n\nTest Case 9: Remove last element.");
    LT = new SinglyLinkedList<Integer>();
    LT.append(4);
    LT.append(5);
    LT.append(4);
    LT.append(6);
    LT.append(7);
    LT.append(8);
    LT.remove(8);
    LT.getTraverser().traverseList();
    if ( LT.size() != 5 ) {
      throw new RuntimeException("Error in Size.");
    };



    System.out.println("\n\n\n\n\nTest Case 10: Remove All element.");
    LT = new SinglyLinkedList<Integer>();
    LT.append(4);
    LT.append(5);
    LT.append(10);
    LT.append(6);
    LT.append(7);
    LT.append(8);
    LT.remove(8);
    LT.remove(7);
    LT.remove(5);
    LT.remove(4);
    LT.remove(6);
    LT.remove(10);
    LT.getTraverser().traverseList();
    if ( LT.size() != 0 ) {
      throw new RuntimeException("Error in Size.");
    };



    System.out.println("\n\n\n\n\nTest Case 11: Remove element not existing.");
    LT = new SinglyLinkedList<Integer>();
    LT.append(4);
    LT.append(5);
    LT.append(10);
    LT.append(6);
    LT.append(7);
    LT.append(8);
    LT.remove(41);
    LT.getTraverser().traverseList();
    if ( LT.size() != 6 ) {
      throw new RuntimeException("Error in Size.");
    };




    // ============== FIND TESTING =================//
    System.out.println("\n\n\n\n\nTest Case 12: find element at root.");
    LT = new SinglyLinkedList<Integer>();
    LT.append(4);
    LT.append(5);
    LT.append(10);
    LT.append(6);
    LT.append(7);
    LT.append(8);
    Integer a = new Integer(4);
    System.out.println(LT.find(a));
    if ( a.compareTo(LT.find(a)) != 0 ) {
      throw new RuntimeException("Error in find.");
    };
    LT.getTraverser().traverseList();
    if ( LT.size() != 6 ) {
      throw new RuntimeException("Error in Size.");
    };




    System.out.println("\n\n\n\n\nTest Case 13: find element at last.");
    LT = new SinglyLinkedList<Integer>();
    LT.append(4);
    LT.append(5);
    LT.append(10);
    LT.append(6);
    LT.append(7);
    LT.append(8);
    a = new Integer(8);
    System.out.println(LT.find(a));
    if ( a.compareTo(LT.find(a)) != 0 ) {
      throw new RuntimeException("Error in find.");
    };
    LT.getTraverser().traverseList();
    if ( LT.size() != 6 ) {
      throw new RuntimeException("Error in Size.");
    };



    System.out.println("\n\n\n\n\nTest Case 14: find element non existing.");
    LT = new SinglyLinkedList<Integer>();
    LT.append(4);
    LT.append(5);
    LT.append(10);
    LT.append(6);
    LT.append(7);
    LT.append(8);
    a = new Integer(21);
    System.out.println(LT.find(a));
    if ( LT.find(a) != null ) {
      throw new RuntimeException("Error in find.");
    };
    LT.getTraverser().traverseList();
    if ( LT.size() != 6 ) {
      throw new RuntimeException("Error in Size.");
    };




    // ============== INSERT AFTER TESTING =================//
    System.out.println("\n\n\n\n\nTest Case 15: Inserting at negative index.");
    LT = new SinglyLinkedList<Integer>();
    try {
      LT.insertAfter(-3, 5);
    } catch (Exception e) {
      if ( e.getMessage() != "Negative Index not accepted." ) {
        throw new RuntimeException("Error in Size.");
      }
      System.out.println("Tested");
    }
    LT.getTraverser().traverseList();





    System.out.println("\n\n\n\n\nTest Case 16: Inserting at 0 index.");
    LT = new SinglyLinkedList<Integer>();
    LT.insertAfter(0, 5);
    LT.getTraverser().traverseList();



    System.out.println("\n\n\n\n\nTest Case 17: Inserting at some index.");
    LT = new SinglyLinkedList<Integer>();
    LT.append(1);
    LT.append(2);
    LT.append(4);
    LT.append(5);
    LT.append(6);
    LT.insertAfter(2, 3);
    LT.getTraverser().traverseList();



    System.out.println("\n\n\n\n\nTest Case 18: Inserting at last index.");
    LT = new SinglyLinkedList<Integer>();
    LT.append(1);
    LT.append(2);
    LT.append(3);
    LT.append(4);
    LT.append(5);
    LT.insertAfter(5, 6);
    LT.getTraverser().traverseList();



    System.out.println("\n\n\n\n\nTest Case 19: Inserting at Out of Bound index.");
    LT = new SinglyLinkedList<Integer>();
    try {
      LT.insertAfter(4, 5);
    } catch (Exception e) {
      if ( e.getMessage() != "Out of Bound Exception." ) {
        throw new RuntimeException("Error in insertion.");
      }
      System.out.println("Tested");
    }
    LT.getTraverser().traverseList();
  }
}

Interfaces

ILinkedList

package com.atleyvirdee.myDataStructures.linkedlist;

/**
 * @author jaspinder
 *
 */
public interface ILinkedList<T extends Comparable<T>> {
  public LinkedListerTraverser<T> getTraverser();
  public void prepend( T data );
  public void append( T data );
  public void remove( T data );
  public int size();
  public void insertAfter( int index, T data );
  public T find( T data );
  public ILinkedListNode<T> getRoot();
}

ILinkedListNode

package com.atleyvirdee.myDataStructures.linkedlist;

public interface ILinkedListNode<T extends Comparable<T>> {
  public ILinkedListNode<T> getNext();
  public void setNext( ILinkedListNode<T> node );
  public T getData();
  public void setData( T data );
}

Traverser

LinkedListerTraverser

package com.atleyvirdee.myDataStructures.linkedlist;

public class LinkedListerTraverser<T extends Comparable<T>> {

  ILinkedListNode<T> root = null;
  int                size = 0;

  public LinkedListerTraverser( ILinkedListNode<T> root, int size ) {
    this.root = root;
    this.size = size;
  }

  public LinkedListerTraverser( ILinkedListNode<T> root ) {
    this.root = root;
    this.size = -1;
  }

  public void setRoot( ILinkedListNode<T> root, int size ) {
    this.root = root;
    this.size = size;
  }

  public void setRoot( ILinkedListNode<T> root ) {
    this.root = root;
    this.size = -1;
  }

  public void traverseList() {
    ILinkedListNode<T> node = root;
    if ( node == null ) System.out.println("Empty List.");
    StringBuffer output = new StringBuffer();
    size = 0;
    int i = 0;
    while (node != null) {
      output.append("Element @ " + i + " = " + node.getData().toString() + "\n");
      i++;
      size++;
      node = node.getNext();
    }
    System.out.println("Size of List: " + size);
    System.out.println(output.toString());
  }
}

Answer 1

I'll just focus on one method:

  @Override
  public T find( T data ) {
    ILinkedListNode<T> node = root;
    while (node != null) {
      if ( node.getData().compareTo(data) == 0 ) {
        return node.getData();
      }
      node = node.getNext();
    }
    return (node == null) ? null : node.getData();
  }

As pointed out in my answer to another of your questions, requiring the nodes to be Comparable is an unreasonable burden. If all you want to check is equality, then call node.getData().equals(data) — every Java object has a .equals() method.

Naming interfaces with the I… Hungarian prefix is unconventional for Java; it's more appropriate in C#.

For a linked list, the conventional terminology is "head" instead of "root".

The only way that the last line is reachable is if node is null. You don't need to test the while-loop condition again. I suggest writing it as a for loop instead, to make the pattern more easily recognizable:

@Override
public T find(T data) {
    for (LinkedListNode<T> node = head; node != null; node = node.getNext()) {
        if (node.getData().equals(data)) {
            return node.getData();
        }
    }
    return null;
}

Answer 2

While reinventing-the-wheel is often fun, you needn't go that far when exercising. Even when writing your own SinglyLinkedList, you should try to fit it to the existing interface List. This way you both exercise programming and learn about existing classes.

There's no equals and no hashCode. You really should write them.

SinglyLinkedList

  ILinkedListNode<T>       root      = null;
  ILinkedListNode<T>       last      = null;
  int                      size      = 0;

This looks more like a fill-in form than like a Java code. If you want a table, use a spreadsheet.

• It adds no value to your code and just costs time.
• It also breaks after renaming.
• Moreover, it makes problem together with version control (e.g., git) as it may force you to introduce needless changes (just imagine you use some reallyLongNameNotFittingInYour column.

Explicitly initializing fields to their default values buys you nothing. Just leave it out, there's no risk involved in

  ILinkedListNode<T> root;
  ILinkedListNode<T> last;
  int size;

This makes it also easier to spat the places where you do some non-default initialization.

---

  @Override
  public ILinkedListNode<T> getRoot() {
    return root;
  }

Look at java.util.LinkedList. It has a Node, but keeps it private. Always keep everything as much private as possible.

---

  LinkedListerTraverser<T> traverser = new LinkedListerTraverser<T>(root, size);

  @Override
  public LinkedListerTraverser<T> getTraverser() {
    traverser.setRoot(root, size);
    return traverser;
  }

This is probably wrong. You're reusing a traverser, so that there can be just one per list. Something like

for (String s1 : list) {
    for (String s2 : list) {
        ...
    }
}

wouldn't work with your list, even when you turned your traverser into an Iterator.

---

  throw new RuntimeException("Negative Index not accepted.");

Should be IllegalArgumentException or better IndexOutOfBoundsException.

LinkedListTester

public class LinkedListTester {

Use JUnit. It's not hard to learn and everybody uses it (or some better but similar alternative).

System.out.println("Test Case 1: Appending 1 element.");

You really don't want to print anything when you run thousands of tests.

ILinkedList<Integer> LT = new SinglyLinkedList<Integer>();

LT is a wrong name, it should start lowercase and why "T"? Just call it List.

---

Rewriting you whole test with JUnit should take 10 minutes at most. This is the start

public class LinkedListTest extends TestCase {
    public void testAppend_one_element() {
        ILinkedList<Integer> list = new SinglyLinkedList<Integer>();
        list.append(1);
        list.getTraverser().traverseList();
        assertEquals(1, list.size());
    }

    ...
}

As you can see, naming methods in tests is not that strict. It's usually test + capitalized method name and you may add an underscore and some details. Some people call their methods like test_that_adding_two_and_three_gives_five.

No idea what the traverser does in the above test. If you implemented List and used Guava, you could simplify your test to

    public void test_appending_one_element() {
        ILinkedList<Integer> list = new SinglyLinkedList<Integer>();
        list.append(1);
        assertEquals(ImmutableList.of(1), list);
    }

which is more descriptive.

LinkedListerTraverser

It looks like all it does is printing. Implement toString in your list (you may need a helper class for this, but probably not).