How to implement a Linked List in Java?

Question

I am trying to implement a simple HashTable in Java that uses a Linked List for collision resolution, which is pretty easy to do in C, but I don't know how to do it in Java, as you can't use pointers...

First, I know that those structures are already implemented in Java, I'm not planning on using it, just training here...

So I created an element, which is a string and a pointer to the next Element:

public class Element{
        private String s;
        private Element next;

        public Element(String s){
            this.s = s;
            this.next = null;
        }

        public void setNext(Element e){
            this.next = e;
        }

        public String getString(){
            return this.s;
        }

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

        @Override
        public String toString() {
            return "[" + s + "] => ";
        }
    }

Of course, my HashTable has an array of Element to stock the data:

public class CustomHashTable {
    private Element[] data;

Here is my problem:

For example I want to implement a method that adds an element AT THE END of the linked List (I know it would have been simpler and more efficient to insert the element at the beginning of the list, but again, this is only for training purposes). How do I do that without pointer?

Here is my code (which could work if e was a pointer...):

public void add(String s){
        int index = hash(s) % data.length;
        System.out.println("Adding at index: " + index);
        Element e = this.data[index];
        while(e != null){
            e = e.getNext();
        }
        e = new Element(s);
    }

Thanks!

Solution 1

public void add(String s){
    int index = hash(s) % data.length;
    System.out.println("Adding at index: " + index);
    Element curr = new Element(s);
    Element e = this.data[index];
    if (e == null) {
       this.data[index] = curr;
       return;
    }
    while(e.getNext() != null){
        e = e.getNext();
    }
    e.setNext(curr);
}

Solution 2

If you want to write your own, start by having it implement the java.util.List interface.

If you can use a library class, use the java.util.LinkedList.

Now it's been pointed out to me that you're "practicing", so some good advice might be off limits according to some, but you should be aware of generics. I'd recommend reading up on them and building them into your Element (Node?) and List implementations. Generics were born for use with collections in just this way. I'd start here:

package list;

public class Node<T>
{
    private T value;
    private Node<T> prev;
    private Node<T> next;
    // You add the rest.
}

Solution 3

For your purposes here Java's references are not used differently from C's pointers. In fact, the major problem (or benefit, depending on who you ask) pointers have in C is not that they can point to something, but that you can do math with them.

For just the pointing purposes, you can do the same here:

e.setNext(new Element(s));

instead of

e = new Element(s);

(which would just let the variable e point to a new element, but won't change anything on the old ones).

and you're done.