My own expandable list

Question

I wondered how an expandable list could be implemented. My first thought: You could create a class that has an array and you can create a new array each time the user wants to append an element and than you can copy the old array plus the new element into the new array. But this seems very inefficient to me. Then I read something about so called linked lists. The idea is very simple. Such a list has nodes. Nodes contain an object and another node. The nodes can be linked as required. I had my thoughts about that and I tried to write a class that follows this thought.

LinkedList.java

package linkedList;
public class LinkedList<T> {
 private Node<T> startNode;
 public LinkedList() {
 startNode = new Node<T>();
 }
 private Node<T> getEmptyNode() {
 Node<T> currentNode = this.startNode;
 while (currentNode.hasObject()) {
 currentNode = currentNode.getNextNode();
 }
 return currentNode;
 }
 public void insert(T object) {
 Node<T> emptyNode = getEmptyNode();
 emptyNode.setObject(object);
 emptyNode.setNextNode(new Node<T>());
 }
 public int getNumberOfElements() {
 Node<T> currentNode = startNode;
 int numberOfElements = 0;
 while (currentNode.hasObject()) {
 numberOfElements++;
 currentNode = currentNode.getNextNode();
 }
 return numberOfElements;
 }
 private Node<T> getNodeByIndex(int index) {
 Node<T> currentNode = startNode;
 for (int i = 0; i < index; i++) {
 currentNode = currentNode.getNextNode();
 }
 return currentNode;
 }
 public T get(int index) {
 return getNodeByIndex(index).getObject();
 }
 public void delete(int index) {
 if (index == 0) {
 startNode = getNodeByIndex(1);
 return;
 }
 // if index equals last available index
 if (index == (getNumberOfElements() - 1)) {
 Node<T> nodeBefore = getNodeByIndex(index - 1);
 nodeBefore.setNextNode(null);
 return;
 }
 Node<T> nodeBefore = getNodeByIndex(index - 1);
 Node<T> nodeBehind = getNodeByIndex(index + 1);
 nodeBefore.setNextNode(nodeBehind);
 }
}

Node.java

package linkedList;
public class Node<T> {
 private T object;
 private Node<T> nextNode;
 public Node() {
 this.object = null;
 this.nextNode = null;
 }
 public boolean hasObject() {
 return object != null;
 }
 public boolean hasNextNode() {
 return nextNode != null;
 }
 public T getObject() {
 return object;
 }
 public Node<T> getNextNode() {
 return nextNode;
 }
 public void setNextNode(Node<T> nextNode) {
 this.nextNode = nextNode;
 }
 public void setObject(T object) {
 this.object = object;
 }
}

Main.java

package linkedList;
public class Main {
 public static void main(String[] args) {
 LinkedList<String> linkedList = new LinkedList<>();
 linkedList.insert("Hallo");
 linkedList.insert("Test");
 linkedList.insert("Wie gehts?");
 linkedList.insert("Freuen sie sich?");
 System.out.println("Anzahl der Elemente: " + linkedList.getNumberOfElements());
 System.out.println("Drittes Element: " + linkedList.get(2));
 System.out.println("Alle Elemente:");
 for (int i = 0; i < linkedList.getNumberOfElements(); i++) {
 System.out.println(linkedList.get(i));
 }
 linkedList.delete(2);
 System.out.println("Alle Elemente:");
 for (int i = 0; i < linkedList.getNumberOfElements(); i++) {
 System.out.println(linkedList.get(i));
 }
 }
}

Because this is my first attempt to do such stuff I am wondering what things can be improved. Is there a way to make this more efficient? Is the code clean and readable enough?

• Graipher: Since you are not asking for a comparative review or the review of one implementation modeled after an already existing implementation, I think it would be better if you split this into two questions, one containing the Java implementation and one containing the Python version. This also makes it a lot easier for the reviewers. Since the two questions are related, you should probably add a link to the other one in both questions (by editing them after having created them).
• Dexter Thorn: Ok I will do so
• potato: On a side note: a list based on arrays doesn't have to be mutated every time you add a single element, you can have an array of size capacity and when the array is full you can mutate it into an array of size capacity * 2, then capacity * 3 and so on. That's how java.util.ArrayList is implemented.

Answer 1

Node<T> nodeBefore = getNodeByIndex(index - 1);
Node<T> nodeBehind = getNodeByIndex(index + 1);
nodeBefore.setNextNode(nodeBehind);

This is from the delete() function. You call getNodeByIndex() twice which iterates from the start of the list twice, instead you can just go 2 nodes forward from nodeBefore:

Node<T> nodeBefore = getNodeByIndex(index - 1);
Node<T> nodeBehind = nodeBefore.getNextNode().getNextNode();
nodeBefore.setNextNode(nodeBehind);

Also I would rename nodeBehind to nodeAfter for the sake of clarity.

---

In the implementation of getNumberOfElements() you don't check if the first element is null.

---

When deleting the last node in the list, you should turn the node into an empty node instead of removing it completely to ensure that getEmptyNode() will have a node to return.

---

You can keep track of the number of nodes instead of re-counting them every time, that would greatly improve the performance of getNumberOfElements() and the other methods that use it:

public class LinkedList<T> {
 private Node<T> startNode;
 private int length; // increment/decrement this every time you add/remove an element

---

I don't like the idea of keeping an empty node at the end and using getEmptyNode() to find it by iterating over the whole list, it would be much simpler if you didn't keep an extra empty node at the end but kept a reference to the last node for internal use.

---

In the constructor of Node you don't need to set the node's properties to null, they already are null.

Answer 2

You are on the right track, and I think you would benefit by having your class implement the Java List<T> interface like so:

public class LinkedList<T> implements List<T> {

You would then have to change your methods so that their names and signatures conform to the interface. You can read about the details here for Java 7 or here for Java 8. If you do this then you could pass instances of your class into already implemented functions like Collections.sort.