Problem
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;
}
}
}
Solution
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).
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.
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
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.
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("]");