Improving Java LinkList implementation

Question

I am trying to implement linklist data structure in java. Following is my implementation:

// A singly Linked List
class Node{

int value;
Node next;

Node(int n){
   this.value = n;
   this.next = null;
}

public void printNode(){
   System.out.println("Value: " + value);
}

}

class LinkList{

 private Node first;
 private Node last;

 public LinkList(){
  first = null;
  last = null;
}

public boolean isEmpty(){
   return first == null;
}

public void insertFirst(int n){


 Node node = new Node(n);


 if(first == null){
    System.out.println("1. Vlaue of n: "+n);
    first = node;
    last = node;
 }else{
    System.out.println("2. Vlaue of n: "+ n);
    Node tmp = first; 
    first = node;
    node.next = tmp;

  }

 }

 public void deleteFirst(){
   if (!isEmpty()){
      Node tmp = first; 
      first = tmp.next;
  }
}

public void deleteLast(){

 if(!isEmpty()){

    Node tmp = first;
    Node oneBeforeLast = null;

    while (tmp.next != null){
        oneBeforeLast = tmp;
        tmp = tmp.next;
    }

    oneBeforeLast.next = null;

   }
 }

 public void deleteNode(int value){

  if (!isEmpty()) {

    Node tmp = first;
    Node oneBeforeLast = first;

    while (tmp.next != null) {

        if (tmp.value == value) {

            if (oneBeforeLast == first) {
                first = tmp.next;
            } else
                oneBeforeLast.next = tmp.next;
        }
        oneBeforeLast = tmp;
        tmp = tmp.next;
        System.out.println("Btmp: " + oneBeforeLast.value + " tmp: 
        " + tmp.value);
    }

     if (tmp.next == null && tmp.value == value) {
        oneBeforeLast.next = null;
     }
    }
 }

public void printList(){

  Node tmp = first;

  System.out.println("\nPrinting List:");

  while(tmp != null){
     tmp.printNode();
     tmp = tmp.next;
   }
 }
}


public class LinkListTest {



 public static void main(String[] args) {

 // TODO Auto-generated method stub
 LinkList linklist = new LinkList();
   linklist.insertFirst(1);
   linklist.insertFirst(2);
   linklist.insertFirst(3);
   //linklist.insertFirst(3);
   linklist.insertFirst(4);

   linklist.printList();

   //linklist.deleteFirst();
   //linklist.printList();

  //linklist.deleteLast();
  //linklist.printList();

   linklist.deleteNode(1);
  linklist.printList();
 }

}

I would like to improve it further and check its efficiency for large inputs. Can anyone give some pointers on these two pointers, please?

Answer 1

One area you could improve performance is by making it a doubly linked list.

At the moment your deleteLast() method is an O(n) operation, meaning it needs to traverse the entire list to delete the last element. And since this is the case, there's no real reason for keeping a reference to it at all.

If each Node had a next and a prev Node, your delete last could look something like,

last.prev.next = null

and let the garbage collector worry about the rest. You would of course still need to check that all of these values are okay to use like this before hand.

LinkedLists are supposed to be good at adding and deleting elements from the start. And if it's a doubly linked list, also the end.

As side note, I would prefer to see your Node class as a private class inside your linked list class. As this Node class probably shouldn't be used anywhere else.

Your public interface is a bit unusual, for a list, I would expect to have public methods like list.add(element), list.removeAt(0) etc.

list.insertFirst(data) is an implementation detail, this should be a private method that's called when the list is empty. if I wanted to insert an element at the head of the list, I would prefer list.insertAt(0)

Another thing that stands out is your deleteNode method. This is definitely an implementation detail leaking out. A user of the list shouldn't know at all about Nodes.

The method doesn't even take a node, it takes an int, I would prefer list.delete(element).

Also, your list won't properly support duplicate values, if I have 3 nodes with the value if 5, and I try to delete 5, it will delete the first node with a value of 5 it finds.

As another side, you should make as many variables private as possible.

Answer 2

Since the question was moved, here is my answer from the old topic:

You could look into generics. (google it - this is too much to explain here)

Then at some points you use an extra Object for oneBeforeLast. You could try something like this instead:

public void deleteLast(){
    if(!isEmpty()){
        Node tmp = first;
        while (tmp.next != null && tmp.next.next != null){
            tmp = tmp.next;
        }
        tmp.next = null;
    }
}

Another point is: do you ever use the last variable? I don't think so and in singly linked lists there is no great use for it. (The only reason to have this might be to create a method getLast().)

And please try to keep code samples shorter by avoiding empty lines and such large main methods ;)