22
\$\begingroup\$

I created my own implementation of a Singly Linked List. Is there anything I can improve on, in terms of effciency. Also, what other methods would you recommend for me to try and implement. My goal is to just understand the components of basic data structures.

LinkedList:

public class StratchLinkedList {

private Node head;
private int size;

public StratchLinkedList() {
    head = null;
    size = 0;
}

public void add(Object data) {

    Node temp = new Node(data);
    Node curr = head;

    if (head == null) {
        head = temp;
    } else {
        while (curr.getNext() != null) {
            curr = curr.getNext();
        }

        curr.setNext(temp);
    }
}

public void add(Object data, int index) {

    Node temp = new Node(data);
    Node curr = head;

    if (index == 0){
        temp.setNext(head);
        this.head = temp;
    } else{
        for(int i = 1; i < index; i++){
            curr = curr.getNext();
        }
        temp.setNext(curr.getNext());
        curr.setNext(temp);
    }

    this.size++;
}

public void replace(Object data, int index) {
    Node curr = head;
    for (int i = 0; i < 0; i++){
        curr = curr.getNext();
    }

    curr.setData(data);
}

public Object get(int index) {

    Node curr = head;
    for (int i = 0; i < index; i++){
        curr = curr.getNext();
    }

    return curr.getData();
}

public void remove(int index) {

    Node curr = head;

    if (index == 0) {
        head = head.getNext();
    } else {
        for (int i = 1; i < index; i++){
            curr = curr.getNext();
        }

        curr.setNext(curr.getNext().getNext());
    }

    this.size--;
}

public int size() {
    return this.size;
}

public String toString() {
    String list = "";
    list += "[" + this.head.getData() + "]";

    Node curr = head.getNext();
    while (curr != null){
        list += "[" + curr.getData() + "]";
        curr = curr.getNext();
    }

    return list;

}

}

Node:

public class Node {

Node next;
Object data;

public Node(Object data) {
    this(data, null);
}

public Node(Object data, Node next) {
    this.next = next;
    this.data = data;
}

public Object getData() {
    return this.data;
}

public void setData(Object data) {
    this.data = data;
}

public Node getNext() {
    return this.next;
}

public void setNext(Node nextNode) {
    this.next = nextNode;
}

}

EDIT: Code working in progress.

public class StratchLinkedList<T> {

private Node head;
private Node tail;
private int size;

public StratchLinkedList() {
    head = null;
    tail = null;
    size = 0;
}

public void insert(T data, int index) {

    if (index > size) {
        throw new IllegalArgumentException("The index [" + index
                + "] is greater than the currentent size [" + size + "].");
    } else {

        Node temp = new Node(data);
        Node current = getNode(index);

        if (index == 0) {
            temp.setNext(head);
            head = temp;
            tail = head;
        } else {
            temp.setNext(current.getNext());
            current.setNext(temp);
        }

        if ( index == size - 1 ) {
            tail.setNext(temp);
            tail = temp;
        }

    }

    size++;
}

public void append(T data) {
    insert(data, size);
}

public void replace(T data, int index) {
    getNode(index).setData(data);
}

public void remove(int index) {

    if (index == 0) {
        head = head.getNext();
    } else {
        getNode(index).setNext(getNode(index).getNext().getNext());
    }

    this.size--;
}

private Node getNode(int index) {

    if ( index > size ) {
        throw new IllegalArgumentException("The index [" + index + "] is greater than the current size [" + size + "].");
    }
    Node current = head;
    for (int i = 1; i < index; i++) {
        current = current.getNext();
    }

    return current;
}

public T get(int index) {
    return getNode(index).getData();
}

public int size() {
    return this.size;
}

public String toString() {
    StringBuilder builder = new StringBuilder();

    Node current = head;
    while( current != null ) {
        builder.append("[" + current.getData() + "]");
        current = current.getNext();
    }

    return builder.toString();

}



private class Node {

    Node next;
    T data;

    public Node(T data) {
        this(data, null);
    }

    public Node(T data, Node next) {
        this.next = next;
        this.data = data;
    }

    public T getData() {
        return this.data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public Node getNext() {
        return this.next;
    }

    public void setNext(Node nextNode) {
        this.next = nextNode;
    }

}

}
\$\endgroup\$
18
\$\begingroup\$

Don't Repeat Yourself (DRY)

public void add(Object data) {

    Node temp = new Node(data);
    Node curr = head;

    if (head == null) {
        head = temp;
    } else {
        while (curr.getNext() != null) {
            curr = curr.getNext();
        }

        curr.setNext(temp);
    }
}

You have a size field, so you should update it in this function.

Actually though, you can write this function more simply:

public void add(Object data) {
    add(data, size);
}

That reduces your duplicated code, easing maintenance. It also eliminates the bug where you weren't updating the size. This is one of the main reasons why duplicate code is bad: it is easy to have inconsistent results.

Don't trust your input

public void add(Object data, int index) {

    Node temp = new Node(data);
    Node curr = head;

    if (index == 0){
        temp.setNext(head);
        this.head = temp;
    } else{
        for(int i = 1; i < index; i++){
            curr = curr.getNext();
        }
        temp.setNext(curr.getNext());
        curr.setNext(temp);
    }

    this.size++;
}

What happens if index > size? You'll throw a NullPointerException when you try to dereference the null pointer at the end of the list. This is rather uninformative. There are several alternatives. You could pad the list with blank nodes when this happened, but that would be just as uninformative if this was unintentional. You could throw a more informative exception:

    if ( index > size ) {
        throw new IllegalArgumentException("The index [" + index + "] is greater than the current size [" + size + "].");
    }

Or you could silently act as if index were equal to size and continue:

    if ( index > size ) {
        index = size;
    }

If adding to the end of the list is common, you have another alternative:

        if ( null == tail ) {
            tail = head;
        }
    } else if ( index >= size ) {
        tail.setNext(temp);
        tail = temp;

This adds a new tail variable that points to the end of the list. Note that you'll have to make additional changes to maintain the tail variable if you go this way. If you don't maintain a tail, then consider making the default to add to the front of the list. That's simple in a linked list whereas adding to the end is difficult when the list is singly linked.

It's not necessary to use this. with field names unless you have a naming conflict (e.g. a function parameter). So you can just say

    size++;

DRY Part II

The functions replace, get, and remove also should watch for the situation where the index is outside the list. For replace and get, you may want to define a find function that you'd use like

    Node current = find(index);

and define as something like

private Node find(int index) {
    if ( index >= size ) {
        throw new IllegalArgumentException("The index [" + index + "] is greater than the current size [" + size + "].");
    }

    Node current = head;
    for ( int i = 0; i < index; i++ ) {
        current = current.getNext();
    }
}

Note that I'm writing out current rather than abbreviating it as curr. The fraction of the second that it saves when reading will outweigh the fraction of a second longer that it takes to type it. Not necessarily today, but six months from now, you'll need to spend a moment remembering what curr means. And of course anyone else who reads it has figure it out immediately. Useful code is read more than it is written, so it makes sense to optimize for the common case.

StringBuilder

public String toString() {
    String list = "";
    list += "[" + this.head.getData() + "]";

    Node curr = head.getNext();
    while (curr != null){
        list += "[" + curr.getData() + "]";
        curr = curr.getNext();
    }

    return list;
}

Rather than a String, consider using a StringBuilder instead. StringBuilder is designed for appending. Regular String values are not. Using += on a String implicitly creates a new String every time. If you're lucky, the compiler might rewrite your version to use StringBuilder instead.

public String toString() {
    StringBuilder builder = new StringBuilder();

    Node current = head;
    while ( current != null ) {
        builder.append("[" + current.getData() + "]");
        current = current.getNext();
    }

    return builder.toString();
}

Note that this code also handles the case of an empty list, which the original code did not (it would throw a NullPointerException if called with an empty list, as it would try to dereference the null head).

\$\endgroup\$
  • 1
    \$\begingroup\$ +1 for public void add(Object data) { add(data, size); } ...elegant and effective \$\endgroup\$ – Aneesh K Feb 27 '15 at 14:51
9
\$\begingroup\$

Welcome to CodeReview! I'm not much of a Java expert, but hopefully I can take a look.

It looks pretty good over all, but I have a few notes.


For learning purposes, Object is fine, but in a real implementation, you would want to use generics. Really, since the generics around this are pretty simple, it might be a good introduction to coding with generics.


for (int i = 0; i < 0; i++){
    curr = curr.getNext();
}

I'm assuming that's a typo? This could also be a good introduction to unit testing if you haven't done it before.


You seem to do the "get the node at index x" operation in a lot of different places. It should be pulled out into a method.


Node is an implementation detail of the List. It shouldn't be a public class that consumers can see.


Instead of traversing the list each time you append an element, you should store a tail reference so it can be constant time instead of linear.


I would consider omitting slow operations from the list. When people use a certain data structure, they tend to assume all of the methods on it are relatively efficient.


To do a linked list right in a high level language, you really need an iterator. That lets you do all kinds of things that are quite nice like a constant time add(Iterator location, Object data) without exposing the Node (the way to do it without an iterator is to just have a getHead() method and then iterate over the nodes directly :/). It also makes travseral of the list a bit cleaner, and, as a bonus, if the list were to implement Iterable, you can use it in for-each loops.


Class contents are usually indented under the class declaration:

public class SomeClass {
    public SomeClass() {}
}

It of course comes down to personal style, but I've never seen class implementation flush with the declaration.

This is an even smaller thing, but people tend to omit the this when accessing properties unless it's required.


public void replace(Object data, int index)

I would expect a replace method to return the old value that was stored in the list.


You should verify that index values are within the range of the list. An IllegalArgumentException is a bit more meaningful than a NullPointerException. (Although, a case could certainly be made for just letting the NPE happen...)

Note: iterators make it a bit more difficult to provide an invalid index.


You should use StringBuilder in toString. Usually it doesn't matter much, but for a container that might be fairly large, it could be a meaningful performance difference.


You could consider using a sentinel node. It lets you simplify some of the special cases around the head node (like I tried to do before Brython caught my mistake), and it makes reasoning about the list a little easier. It also unfortunately wastes a tiny bit of space, costs an allocation, and makes an empty list actually do something non-trivial on construction, but meh... In all but the most constrained of situations, none of the downsides tend to matter.

\$\endgroup\$
  • 1
    \$\begingroup\$ +1 for avoiding slow operations. Either make add(Object) insert a mode at the head, or maintain a pointer to the last node so that appending to the end is fast. \$\endgroup\$ – 200_success Feb 27 '15 at 6:39
6
\$\begingroup\$

Here is a bug:: Your loop logic is incorrect!

 public void replace(Object data, int index) {
    Node curr = head;
    for (int i = 0; i < 0; i++){
        curr = curr.getNext();
    }

    curr.setData(data);
}

For fun:

  • Implement a method that can merge 2 like nodes
  • Method to insert node at head of list
  • Find smallest / largest value
  • Search for specific value
\$\endgroup\$
4
\$\begingroup\$

To make your class more usable in a real project, you could turn it into a generic class. That way users of your class can create a StratchLinkedList<String>, StratchLinkedList<Integer> or StratchLinkedList<SomeClassOfMyOwn> where all methods take and return the given type instead of Object. This prevents unnecessary typecasting and improves type safety when interacting with your class.

Another improvement you could consider is to implement some interfaces like Iterable or even Collection. That would allow a lot of algorithms from the standard library to interact with your class seamlessly.

\$\endgroup\$
2
\$\begingroup\$

I know the thread is over a year old, but for posterity...

Brythan's answer is excellent, but there is still room for improvement with the StringBuilder section.

builder.append("[" + current.getData() + "]");

as found inside the loop, is likely to be transformed by the Java compiler into:

builder.append(new StringBuilder().append("[").append(current.getData()).append("]").toString());

However, we can append directly to builder and avoid both the creation of a new StringBuilder object and the toString() call, per iteration:

builder.append("[").append(current.getData()).append("]");
\$\endgroup\$
  • \$\begingroup\$ I upvoted your answer since I think doing the multiple append is cleaner, but do you have clear example of the compiler transforming the code to what you think it will do or is it just a guess based on your knowledge ? (I would have the same guess but I would really like to see a proof) \$\endgroup\$ – Marc-Andre Apr 4 '16 at 14:58
  • \$\begingroup\$ The byte-code generated by the original code "compile" may indeed have the nested StringBuilder calls, so this answer is correct with that. What happens to the bytecode nowdays when it goes through multiple levels of optimization, etc. is much less predictable. Regardless, this answer contains good advice. \$\endgroup\$ – rolfl Apr 4 '16 at 15:22
1
\$\begingroup\$

I'm going to assume that you're doing this in order to learn more Java, and not as some actual project as a salaried employee.

For starters, other people have told you about bugs in size. I'm going to be a heretic here, and say that since you're doing this for learning, calculate it every call using recursion.

This will be a decent first recursion method, and since it's for learning, who cares about speed, as long as it's not horrible.

Secondly, you have two methods called add. Add just adds to the end of the list, right? What it should do is to calculate what index that would be (by calling size(), of course), and then telling add(Object, int) where to add it.

add(Object item) {
  int index = size() - 1; // assumes zero-indexing
  add(item, index);
}

This is pretty clear to everyone what's happening. We all know that the last element of an array is array.length - 1, so this is no surprise to anyone.

Now, after you've done that Philipp had the excellent suggestion to make it Generic, and to implement interfaces. I would add to that and suggest learning about annotations, such as the @NonNull annotation. These can be pretty nice to know about, even if you're not going to use them yourself that much.

As for StringBuilder, it's good to see how it works, not just because it's faster, but more importantly because if you're just learning, then it's likely the first meeting you'll have with the Builder pattern, which you'll learn to love the second you see some class with 14 String arguments in its constructor. (That code was outsourced to deep beneath the see in R'Lyeh.) At that point you'll know what to do and have some better understanding.

One thing that really saddens me though is that you haven't added on any Javadocs. Javadocs are one of the best things about Java, and caused competing platforms to step up their game when it came to documentation. You really should learn how to write them. Oracle has a guide

Everything else has been said n times already, so I'll just not say it again.

\$\endgroup\$
1
\$\begingroup\$

Just a very small bug I think there may be in your remove function. Won't calling .getNext().getNext on the last element give you a NullPointerException where you are calling .getNext() on Null?

\$\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.