current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote -1 down vote favorite

I am currently reading about the thread-safe implementation of a linked list. Although I implemented this linked list while keeping in mind the issues from the first code review (Binary Tree). I would like someone to point out some mistakes that will create issues if I try to make it thread-safe in the future.

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);

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

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

  @Override
  public void prepend( T data ) {
    size++;
    if ( this.root == null ) {
      append(data);
      return;
    }
    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();
      return;
    }
    while (node.getData() != data) {
      parent = node;
      node = node.getNext();
      child = node.getNext();
    }
    parent.setNext(child);
    node.setNext(null);
  }

  @Override
  public void insertAfter( int index, T data ) {
    if(index > size){
      throw new RuntimeException("Out of Bound Exception. index:"+index+" is more then the Size of LinkedList:"+size);
    }
    ILinkedListNode<T> node = root;
    while (node != null && index > 0) {
      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 && node.getData() != data) {
      node = node.getNext();
    }
    return (node == null) ? null : node.getData();
  }


  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;
    }
  }



}

Corrected code

share|improve this question

closed as off-topic by maaartinus, Hosch250, QPaysTaxes, Mat's Mug♦, Gary Storey Jun 22 at 20:50

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions containing broken code or asking for advice about code not yet written are off-topic, as the code is not ready for review. After the question has been edited to contain working code, we will consider reopening it." – maaartinus, Hosch250, QPaysTaxes, Mat's Mug, Gary Storey
If this question can be reworded to fit the rules in the help center, please edit the question.
1  
As mdfst13's review shows, the code contains quite a few bugs. You should look at warnings you get (Eclipse shows a warning when after ILinkedListNode<T> child = root.getNext(); the test root != null comes) and write at least some elementary tests). Obviously, you haven't even tried new SinglyLinkedList<String>().remove("") as it surely throws. Testing everything properly is hard, but writing some tests is simple and necessary as you can see. –  maaartinus Jun 22 at 19:23
    
@maaartinus I definitely do that first thing in the morning. Lesson learned. Although I did some basic testing in a test class. I agree I didn't wrote test cases for all functions. I will do that in a separate class. –  Jaspinde Virdee Jun 22 at 19:33

1 Answer 1

up vote 5 down vote

First Bug

    size++;
    if ( this.root == null ) {
      append(data);
      return;
    }
    ILinkedListNode<T> node = new NodeImpl<T>(data);

There's a bug here. If you're going to call append, you should do it before changing the size. Note that append also increments size. So this path will increment size twice. 

    if ( this.root == null ) {
      append(data);
      return;
    }
    size++;
    ILinkedListNode<T> node = new NodeImpl<T>(data);

This way will only increment size once.

Alternatively, you could simply write the two lines from append that you actually use in prepend: 

    size++;
    ILinkedListNode<T> node = new NodeImpl<T>(data);
    if ( this.root == null ) {
      this.root = node;
      this.last = node;
      return;
    }

Or create a helper method for this for use in both append and prepend:

  private void insertFirstNode(ILinkedListNode<T> node) {
      this.root = node;
      this.last = node;
  }

Although I'm not sure that's necessary. It's only two lines.

It seems odd that you have prepend call append but that you don't have append call insertAfter but instead rewrite it. Note that append can be written 

  public void append(T data) {
    insertAfter(size - 1, data);
  }

Second Bug (and Third and Fourth)

    ILinkedListNode<T> node = root;
    ILinkedListNode<T> child = root.getNext();
    if(root != null && root.getData() == data){
      root = root.getNext();
      return;
    }
    while (node.getData() != data) {
      parent = node;
      node = node.getNext();
      child = node.getNext();
    }
    parent.setNext(child);
    node.setNext(null);

If root is null, then node will be null. But you call getNext on both root and node without checking for that. You do check before calling getData on root but you'll never reach that if root is null. 

    if (root == null) {
      // return or throw an exception here
    }

    if (root.getData() == data){
      root = root.getNext();
      size--;
      return;
    }

    ILinkedListNode<T> parent = root;
    ILinkedListNode<T> node = root.getNext();
    if (node == null) {
      // return or throw an exception
    }

    while (node.getData() != data) {
      parent = node;
      node = node.getNext();
      if (node == null) {
        // return or throw an exception
      }
    }

    size--;
    parent.setNext(node.getNext());
    node.setNext(null);

This checks the empty case first.

Another problem is that you don't decrement size when you remove an element. You should do that.

You don't need child. You can just say node.getNext() directly rather than updating child multiple times.

You should check for the possibility that you won't find the data in the list.

I think that's enough bugs for one review. Please get your code working before putting it up for review.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.