1
\$\begingroup\$

I recently reviewed some data structure concepts, so I implemented my own templated linked list. I am very interested about the code efficient and performance.

LinkedList class

package linkedlist;

public class Linkedlist<T> {
protected Node<T> head;
protected Node<T> tail;
protected int size;

public Linkedlist() {
    // TODO Auto-generated constructor stub
    head = null;
    tail = null;
    size = 0;

}

public void append(T value) {
checkValue(value, "not allow to insert null value");    
    if (head == null) {
        head = tail = new Node<T>(value);
        size++;
    } else {
        Node<T> tmp = new Node<T>(value);
        tail.setNext(tmp);
        tail = tmp;
        size++;
    }
}

public int findIndexOf(T value) {
checkValue(value, "can't search for null value");
    Node<T> tmp = head;
    int counter = 0;
    while (tmp != null) {
        counter++;
        if (tmp.getValue().equals(value)) {
            return counter-1;
        }
        tmp = tmp.getNext();
    }
    return -1;
}

public T findValueOf(int index) {
checkIndex(index);
        Node<T> tmp = head;
        int counter = 0;
        while (counter <= index) {
            if (counter == index) {
                return tmp.getValue();
            } else {
                tmp = tmp.getNext();
                counter++;
            }
        }   
    return null;
}

 public void insert(T value,int index){
checkIndex(index);
checkValue(value, "not allow to insert null value");
Node<T> node=new Node<T>(value);

    Node<T> tmp = head;
    if(index==0){

        node.setNext(head);
        head=node;
    }
    else if(index == size-1){
        node.setNext(tail);
        tail=node;
    }
    else
    {
    int counter = 1;
    while (counter <= index) {
        if (counter == index-1) {
            node.setNext(tmp.getNext());
            tmp.setNext(node);
                break;
        } 
        else {
            tmp = tmp.getNext();
            counter++;
            }
    }

    }

  }

public void delete(int index){
checkIndex(index);
    Node<T> tmp = head;
    int counter = 0;
    while (counter <= index) {
        if (counter == index-1) {
            Node<T> dTmp=tmp.getNext();
            if(tmp.getNext().getNext()==null)
                tail=tmp;
            tmp.setNext(tmp.getNext().getNext());
            dTmp=null;
            size--;
           break;           
        } else {
            tmp = tmp.getNext();
            counter++;
        }
    }

 }
  public void deleteValue(T value){
  checkValue(value, "there are no null value in linked list");

 Node<T> tmp=head;
 if(head.getValue().equals(value)){
    head=head.getNext();
    tmp=null;
    size--;
 }
 else{
 while(tmp.getNext()!=null){

    if(tmp.getNext().getValue().equals(value)){
        Node<T> preTmp=tmp.getNext();
        if(tmp.getNext().getNext()==null)
            tail=tmp;
        tmp.setNext(tmp.getNext().getNext());
         preTmp=null;
        size--;
         break;
    }
     else
        tmp=tmp.getNext();
 }
 }
 }

 private void checkValue(T value,String message){
 if(value == null){
       throw new IllegalArgumentException(message);
    }

}
private void checkIndex(int index) {
if(index < 0 ||index >= size){
    throw new IndexOutOfBoundsException("index "+index+" out of rang");
}
}
public int size() {
    return size;
}

public Node<T> getHead() {
    return head;
}

public Node<T> getTail() {
    return tail;
}

public void display(){
    Node<T> tmp=head;
    while (tmp!=null) {
        System.out.print(tmp.getValue()+" -> ");
        tmp=tmp.getNext();
    }
    System.out.println(" ");
}
}

Node class:

package linkedlist;

public class Node <T>{
private T value;
private Node<T> next;

public Node(T value) {
// TODO Auto-generated constructor stub
this.value=value;
this.next=null;
}

public T getValue() {
 return value;
}

public Node<T> getNext() {
 return next;
}

 public void setNext(Node<T> next) {
 this.next = next;
}


}

Questions:

  1. Is there a more efficient way of implementing what I am doing here?
  2. Are there some bad practices in there?
\$\endgroup\$
  • 3
    \$\begingroup\$ For the record, "templates" are called "generics" in Java, because they work differently from C++ templates. A C++ compiler will generate a separate copy of the code as necessary. Java emits generic bytecode that works for all classes; the type safety is enforced at compile-time. \$\endgroup\$ – 200_success Feb 4 '16 at 6:29
4
\$\begingroup\$

Formatting

 public void deleteValue(T value){
  checkValue(value, "there are no null value in linked list");

Node<T> tmp=head;
 if(head.getValue().equals(value)){
    head=head.getNext();
    tmp=null;
    size--;
 }
 else{
 while(tmp.getNext()!=null){

   if(tmp.getNext().getValue().equals(value)){
        Node<T> preTmp=tmp.getNext();
        if(tmp.getNext().getNext()==null)
            tail=tmp;
        tmp.setNext(tmp.getNext().getNext());
         preTmp=null;
        size--;
         break;
    }
     else
        tmp=tmp.getNext();
 }
 }
 }

Your code seems to be poorly indented, this is either because you had problems pasting it to CodeReview, or didn't notice it was like that. By using indention that follows the curly brackets, you get more clear code.

Inconsistent method curly bracket indention

                    public void append(T value) {
                public int findIndexOf(T value) {
                public T findValueOf(int index) {
          public void insert(T value,int index){
                  public void delete(int index){
private void checkValue(T value,String message){
             private void checkIndex(int index) {
                       public Node<T> getHead() {
                       public Node<T> getTail() {
                          public void display(){

You have 6 methods with a space before the curly bracket, and 4 without. Making this consistent improves the answer.

Useless commentary

public Linkedlist() {
    // TODO Auto-generated constructor stub
    head = null;
    tail = null;
    size = 0;

}

public Node(T value) {
// TODO Auto-generated constructor stub
this.value=value;
this.next=null;
}

No commentary is better than useless commentary, do we really need to know that that constructor is auto generated by eclipse? The constructor is really that simple that it doesn't need commentary.

Cannot delete index 0

You cannot delete the first index by number with your code, this is a bug that should have been catch by unit testing.

delete(int) optimization

public void delete(int index){
    checkIndex(index);
    Node<T> tmp = head;
    int counter = 0;
    while (counter <= index) {
        if (counter == index-1) {
            Node<T> dTmp=tmp.getNext();
            if(tmp.getNext().getNext()==null)
                tail=tmp;
            tmp.setNext(tmp.getNext().getNext());
            dTmp=null;
            size--;
           break;
        } else {
            tmp = tmp.getNext();
            counter++;
        }
    }
}

Your delete method seems to overly complex. Do you really need to check every iteration if the number is 1 before? Just use a for loop to skip index amount of entries, and then run the code to swap the entries:

public void delete(int index){
    checkIndex(index);
    if(size == 1) {
        assert index == 0;
        head = tail = null;
        return;
    }
    Node<T> tmp = head;
    for (int counter = 0; counter < index; counter++) {
        tmp = tmp.getNext();
    }
    Node<T> dTmp=tmp.getNext();
    if(tmp.getNext().getNext()==null)
        tail=tmp;
    tmp.setNext(tmp.getNext().getNext());
    size--;
}

Visibility of Node class

The Node class is not really useful for outsiders, you should make it package private, or a nested (static) subclass of your LinkedList. For example, you don't want outsiders to rudely mess up your code doing getTail().setNext(getHead()) or getHead().setNext(null). A class should be inbreakable when only calling its public methods.

Integer overflow

You are assuming nobody will even put more than Integer.MAX_VALUE entries in your List, if someone does this, the checkIndex check will break and all requests by index will bug.

Implementing standard java interfaces

Java comes with a set of default interfaces like List<>, Iterable<>, Collection<> that makes sense to implement for your class, this enabled code reusage.

I would except your class to be at least implementing a List<T> as its basicly a linked list.

Implementing unit tests

By implementing unit tests for the code, you can catch many bugs early while working on the code, and make it harder for accidental code breaking in the future. A few basic unit tests are:

@Test
public void insertTest() {
    LinkedList<Object> list = new LinkedList<Object>();
    assertEquals(0, list.size());
    list.append(new Object());
    assertEquals(1, list.size());
    list.append(new Object());
    assertEquals(2, list.size());
}

@Test
public void deleteHeadTest() {
    LinkedList<Object> list = new LinkedList<Object>();
    list.append(new Object());
    list.append(new Object());
    assumeEquals(2, list.size());
    list.delete(0);
    assertEquals(1, list.size());
}

@Test
public void deleteTailTest() {
    LinkedList<Object> list = new LinkedList<Object>();
    list.append(new Object());
    list.append(new Object());
    assumeEquals(2, list.size());
    list.delete(1);
    assertEquals(1, list.size());
}

@Test
public void findIndexTest() {
    LinkedList<Object> list = new LinkedList<Object>();
    Object toFind = "findme";
    list.append(new Object());
    list.append(new Object());
    list.append(new Object());
    list.append(toFind);
    list.append(new Object());
    assertEquals(3, list.findIndexOf(toFind));
    assertTrue(list.findIndexOf(new Object()) < 0);
}

@Test
public void dublicateRemovalOnlyRemovedOneResultTest() {
    LinkedList<Object> list = new LinkedList<Object>();
    Object toFind = "findme";
    list.append(toFind);
    list.append(toFind);
    list.append(toFind);
    list.append(toFind);
    list.append(toFind);
    assumeEquals(5, list.size());
    list.deleteValue(toFind);
    assertEquals(4, list.size());
    list.deleteValue(toFind);
    assertEquals(3, list.size());
}

Don't declare a variable before its used

Node<T> tmp = head;
... (11 skipped lines) ...
} else {
    int counter = 1;
    while (counter <= index) {

You declare tmp 11 lines before the scope it's actually used, by moving the declaration before the while loop you make the code more organized.

Implement toString

You should implement the toString method that returns a String instead of defining a display method, the advantage of the toString method is that it returns a String and that can be used with more ease in logging methods.

NPE if list is empty in void deleteValue(T)

public void deleteValue(T value){
  checkValue(value, "there are no null value in linked list");

 Node<T> tmp=head;
 if(head.getValue().equals(value)){

The above will throw a NullPointerException if the list is empty.

void deleteValue(T) leaves List in inconsistent state if size == 1

When we call this method when the list is exactly 1 in size and this method removes something, it leaves the list in the following state:

//Before:
head = tail = new Node<>("findme");
size = 1;

//After:
head = null;
tail = new Node<>("findme");
size = 0;

The object isn't fully removed, it it is still in the List, but inaccessible. It only becomes fully removed when a new Object is put in the List.

Useless -1 in int findIndexOf(T)

    int counter = 0;
    while (tmp != null) {
        counter++;
        if (tmp.getValue().equals(value)) {
            return counter-1;
        }
        tmp = tmp.getNext();
    }

By swapping the order of the if and the counter++, you don't need to use counter-1 anymore.

    int counter = 0;
    while (tmp != null) {
        if (tmp.getValue().equals(value)) {
            return counter;
        }
        counter++;
        tmp = tmp.getNext();
    }

Typo "rang"

throw new IndexOutOfBoundsException("index "+index+" out of rang");

"rang" is a very unusual word for this kind of sentence. Use "range".

throw new IndexOutOfBoundsException("index "+index+" out of range");

Not allowing the end of the list in insert(E,int)

I would expect that calling list.insert(obj,list.size()) has the same result as list.append(obj), your code doesn't do this, it throws a InderOutOfBoundsException instead of appending it to the end of the list.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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