Singly linked list implementation in Java without help of java.util.linkedlist

Question

I am learning Java and as a first exercise I tried to implement singly linked list without the help of java.util. I tested my program for basic operations and it seems to work fine. But I still want to know if there are any improvements I could do in terms of design or implementation in OOP.

Node.java

            public class Node{ 

            // immutable class representing head node of linked list

            private DataItems dataItems;
            private Node nextNode;

            public void setNextNode(Node _nextNode){
                this.nextNode=_nextNode;
            }

            public Node getNextNode(){
                return nextNode;
            }

            public DataItems getDataItems(){
                return dataItems;
            }

            public void setDataItems(DataItems _dataItems){
                this.dataItems=_dataItems;
            }

            }

HeadNode.java

public class HeadNode{ 

// immutable class representing head node of linked list

Node nextNode;

public void setNextNode(Node _nextNode) {
    nextNode=_nextNode;
}

public Node getNextNode() {
    return nextNode;
}

}

DataItems.java

public class DataItems{

private int key;
private String value;

public DataItems(int _key, String _value){
    this.key=_key;
    this.value=_value;
}

public int getKey() {
    return key;
}

public String getValue() {
    return value;
}

public String toString() {
    return "("+getKey()+","+getValue()+")";
}

}

LinkedList.java

public class LinkedList{

HeadNode head;

public LinkedList(){
    head = new HeadNode();
}

// insert node at the beginning of the list
public void insertNode(DataItems _data){
    Node newNode = new Node();
    newNode.setDataItems(_data);
    Node nextNode = head.getNextNode();
    head.setNextNode(newNode);
    newNode.setNextNode(nextNode);
}

// delete node at the beginning of the list
public void deleteNode(){
    Node toBeDeletedNode = head.getNextNode();
    if(toBeDeletedNode!=null) {
        Node nextNode = toBeDeletedNode.getNextNode();
        head.setNextNode(nextNode);
        toBeDeletedNode.setNextNode(null);
    } else {
        System.out.println("No nodes to be deleted");
    }

}

// display all nodes data
public void displayList(){
    Node nodes = head.getNextNode();
    int i=0;
    while(nodes!=null) {
        DataItems data = nodes.getDataItems();
        System.out.println("Node "+i+" : "+data.toString());
        nodes = nodes.getNextNode();
        i++;
    }
}

// reverse order of linked list
public void reverseLinkedList(){
    int sizeOfList = size();
    Node lastNode = nodeAtIndex(sizeOfList-1);
    Node snode, tnode;
    for(int i=sizeOfList-2;i>=0;i--){
        snode = nodeAtIndex(i);
        tnode = snode.getNextNode();
        tnode.setNextNode(snode);
    }
    nodeAtIndex(0).setNextNode(null);
    head.setNextNode(lastNode);
}

// reverse order of linked list
public void searchKey(int _key){
    int i=0;
    DataItems data = dataAtNodeIndex(i);
    while(data!=null){
        if(data.getKey()== _key){
            System.out.println("Node at index : "+i+" has data item : "+data.toString());
        }
        i++;
        data = dataAtNodeIndex(i);
    }
}

// insert a node at index
public void insertNodeAtIndex(int _index, DataItems _data){
    Node newNode = new Node();
    newNode.setDataItems(_data);
    if(_index==0) {
        insertNode(_data);
    } else {
        Node prevNode = nodeAtIndex(_index-1);
        if(prevNode!=null) {
            Node nextNode = prevNode.getNextNode();
            newNode.setNextNode(nextNode);
            prevNode.setNextNode(newNode);
        }
    }
}

// delete a node at index
public void deleteNodeAtIndex(int _index){
    if(_index==0) {
        deleteNode();
    } else {
        Node prevNode = nodeAtIndex(_index-1);
        if(prevNode!=null) {
            Node targetNode = prevNode.getNextNode();
            Node nextNode = targetNode.getNextNode();
            targetNode.setNextNode(null);
            prevNode.setNextNode(nextNode);
        }
    }
}

// return data item at particular node
public DataItems dataAtNodeIndex(int _index){
    Node nodes = nodeAtIndex(_index);
    if(nodes!=null) {
    return nodes.getDataItems();
} else {
    return null;
}
}

// return node at particular index
private Node nodeAtIndex(int _index){
    if(_index<0) {
        return null;
    } else {
        Node nodes = head.getNextNode();
        int i=0;
        while(i<_index && nodes!=null) {
            nodes = nodes.getNextNode();
            i++;
        }
        return nodes;
    }
}

// return the size of linked list
public int size() {
    int count=0;
    Node nodes = nodeAtIndex(count);
    while(nodes!=null) {
        nodes = nodeAtIndex(++count);
    }
    return count;
}

}

Tester.java

public class Tester{

public static void main(String[] args){

// create new linked list
LinkedList ll = new LinkedList();

// insert 5 data to the list
for(int i=0; i<5; i++)
{
    DataItems data = new DataItems(i,"Data_"+i);
    ll.insertNode(data);
}
System.out.println("\n");

// display the inserted data
System.out.println("5 inserted datas are : \n");
ll.displayList();
System.out.println("\n");

// testing deleting node at the beginning
System.out.println("list after deleting first node data : \n");
ll.deleteNode();
ll.displayList();
System.out.println("\n");

// testing deleting node at the index
System.out.println("list after deleting second index data : \n");
ll.deleteNodeAtIndex(2);
ll.displayList();
System.out.println("\n");

// testing inserting node at the index
System.out.println("list after inserting second index data : \n");
DataItems data = new DataItems(11,"Data_11");
ll.insertNodeAtIndex(2,data);
ll.displayList();
System.out.println("\n");

// testing searching node with key
System.out.println("Searching list for key 11 : \n");
ll.searchKey(11);
System.out.println("\n");
System.out.println("size of list : "+ll.size());
System.out.println("\n");

// testing reversing linked list
System.out.println("list after reversing linked list : \n");
ll.reverseLinkedList();
ll.displayList();
}

}

Answer 1

I've only glanced at your code, but two things stood out.

Immutable

In HeadNode you have a comment:

// immutable class representing head node of linked list

Either immutable doesn't mean what you think it does, or this comment is confused. Immutable classes don't change after they've been constructed. They typically have final members so that they can't be assigned to. You HeadNode class provides bother a getter and a setter for its only field nextNode. This isn't an immutable class.

Testing

Rather than rolling your own tests in main, consider looking into a testing framework like JUnit. It allows you to encapsulate tests for different functionality in a more expressive way, so that you can clearly tell from the test runs what is failing if you introduce bugs.

A few afterthoughts to add to @Jonas' answer.

Node

At the moment you have a distinction between nodes that have data (Node) and nodes that don't have data (HeadNode). Does it really make sense to have a Node that doesn't have a dataitem associated with it? Looking at your code, the answer is probably not, the first thing you do after creating a new Node is to call setDataItems. With that in mind, it would be better to add a constructor to your Node class that takes in a data item, rather than requiring the client to call a member function immediately after construction.

Efficiency

As @Janos pointed out, some of your methods are not very efficient. The one that most struck me was your searchKey method. It relies on your dataAtNodeIndex method which in turn relies on nodeAtIndex. Since your nodeAtIndex always starts from head, you end up searching the list over and over again from the start, going one item further each time until you find they key you're looking for.

Error Checking

Some of your methods can fail, but don't have a method for telling the client. For example, insertNodeAtIndex and deleteNodeAtIndex both return void. They also have ways that they can fail to deliver on their promises and fail silently. If a client calls insertNodeAtIndex(5) when the list only has 3 items, then you have a few options. At the moment, you effectively ignore the request (the client has no way to know that the item hasn't been added to the list). It would be better to at the item to the tail of the list (this fulfils the insert promise). However, it would be better still to throw an exception to indicate to the client that they've made an invalid request and that the item hasn't been inserted into the list.

Answer 2

Adding to forsvarir's Answer:

Code Style

Whitespace

Try to use whitespace more consistently. Correct indentation can make code much more readable. Sometimes you put a space before the opening braces after a method definition or around operators (=, +, etc.), sometimes you don't. I won't tell you to put spaces there or to leave them out, that's mostly personal preference or convention (I prefer putting spaces), but when you decide to do one or the other, stick to it.

Parameter Names

All your method parameter's names start with an underscore, which doesn't look particularly nice. If you're already using the this-Keyword to access your object's properties, there is no need to give the parameter a different name than your attributes, since prefixing the name with this. will already tell Java to use the object's property instead of the parameter.

Method Names

insertNode gives the impression it inserts a Node at a freely specified point in the list. Actually, it does neither: it adds the element at the front of the list (making it the new head) and it (from the user's perspective) doesn't add a Node, but a DataItems element to the list. Maybe prependElement would be better suited here. Same goes for deleteNode and generally any method with "node" in its name - of course it is a linked list and thus uses nodes underneath, but that detail should probably be hidden from the user.

Class Names

DataItems only represents a single item, it would be better to not use the pllural form for its name.

Architecture

Unnecessary HeadNode

Your LinkedList stores a reference to a HeadNode. HeadNodes only purpose seems to be to hold a reference to a Node, so why not remove the HeadNode-class altogether and directly use a Node in your LinkedList?

Coupling

Your LinkedList and Node implementations directly use the DataItems class for storing data. The whole linked list-scenario seems like a perfect example for learning to use Java's Generics: That way you can not only use your LinkedList to store DataItems, but any object. You can modify DataItems in the same way to use any type as key or value. See Generic Types for more information on that topic.

If you implemented your list like this, you could also consider implementing Java's List<E> interface to make it completely interchangable with other List-type in Java. While that violates not using the java.util package, it offers quite a range of new things to learn, while trying to implement all methods required by the interface.

Of course, when you use Generics instead of DataItems directly, your searchKey method cannot be implemented as it is now. Instead, you'd need a method (let's call it find), which takes a predicate (i.e. a function taking the datatype stored in your list and returning a true if the item matches whatever you're looking for) as its parameter.

Implementation

Insertion and Deletion

Your insertNode and deleteNode methods both are called when executing insertNodeAtIndex(0, data) and deleteNodeAtIndex(0), respectively. I recommend doing it the other way around, i.e. calling deleteNodeAtIndex(0) from deleteNode in order to keep the insertion/deletion code neatly in a single method instead of splitting it over two separate methods. Also, I would move the method definitions closer together, so you don't have to search too much to find the related method. Always try to keep methods with similar responsibilities closely together in the source file.

Reversing the List

Your implementation of reverseLinkedList is pretty inefficient. For each node in your list, it calls the nodeAtIndex method, which itself iterates over the whole list, causing it to fall in the \$O(n²)\$ group of algorithms. Reversing the list could be done in \$O(n)\$ when using a Stack or recursion.

Calculating the List's Size

This implementation, too, is in \$O(n²)\$ while it could be done in \$O(n)\$. Instead of always calling nodeAtIndex, just put the first node in a variable and in the while loop, check if the element is null, incrementing count and replacing the node with the next node.