HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaMinor

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

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
withoutimplementationutillinkedlisthelpjavasinglylistlinked

Problem

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(toBeDelet

Solution

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.

Code Snippets

// immutable class representing head node of linked list

Context

StackExchange Code Review Q#151995, answer score: 4

Revisions (0)

No revisions yet.