How to implement my own LinkedList<LinkedList> data structure in Java?

Question

I am working on something which would make it easier if several of the objects I use would be written by me (instead of using Java's libraries). I am currently stuck at implementing an ArrayList<ArrayList> object (which we can call MyHashTable) using my LinkedList class and my Node class. Here is my correctly implemented LinkedList class so far:

public class LinkedList{
 Node start;
 int length;
 public LinkedList(){
 start = new Node();
 length= 0;
 }
 public void addNode(Node node){
 Node s= start;
 while (s.next != null){
 s= s.next;
 }
 s.next= node;
 length++;
 }
 public int getLength(){
 return length;
 }
 public boolean findNode(Node node){
 Node s= start;
 while(s.next != null){
 if (s == node){
 return true;
 }
 s.next= node;
 }
 return false;
 }
}

So I am having trouble modifying this class to accept Java generics (so I could make a Linked List of Linked Lists instead of simply Linked List of Nodes). Let me know if I should provide how my Node class looks.

• Sotirios Delimanolis: Where are you storing the values? That's where you should be using generics.
• 3yakuya: I believe you should show code for Node, as in your idea you'd just create a LinkedList of nodes, where each node is of type X.
• Dawood ibn Kareem: You want to make ArrayList<ArrayList> and call it MyHashTable? I have a bad feeling about this.
• Radiodef: Like @DavidWallace I'm also wondering how you plan to make an ArrayList out of a LinkedList and call it a HashTable. All three are completely different data structures. A linked list cannot be an ArrayList by definition because an ArrayList uses an array. You could possible use an ArrayList<ArrayList> like a hash table but it's not a good idea. This sounds like an XY problem to me. Why is it "easier" to make your own data structures from scratch?
• keshlam: You want to make ArrayList<ArrayList> out of a Linked List and call it MyHashTable? I have a worse feeling about that. What problem are you really trying to solve?

Answer 1

A generic LinkedList just substitutes the type of the value. You don't show your Node class so I don't understand how you're using it. Here is a generic linked list:

class LinkedList<E> {
 static class Node<E> {
 E value;
 Node<E> next;
 Node(E value) {
 this.value = value;
 }
 }
 Node<E> head = new Node<E>(null);
 Node<E> tail = head;
 int size;
 void add(E value) {
 tail = tail.next = new Node<E>(value);
 size++;
 }
 E get(int index) {
 if(index < 0 || size <= index)
 throw new OutOfBoundsException(index);
 Node<E> node = head.next;
 while(index > 0) {
 node = node.next;
 index--;
 }
 return node.value;
 }
}

But I'm not sure what you mean by make that in to an ArrayList. An ArrayList is completely different, it is an array that resizes itself automatically:

class ArrayList<E> {
 Object[] array = new Object[10];
 int size;
 void add(E value) {
 if(size >= array.length) {
 array = Arrays.copyOf(array, (int)(size * 3L / 2L));
 }
 array[size++] = value;
 }
 E get(int index) {
 return (E)array[index];
 }
}

And while I suppose you could hack together a hash table by using a multidimensional array, I don't recommend it. You cannot just go and instantiate an array with 2^32 elements so that means you have to manage intersections. I don't see how an ArrayList<ArrayList> could ever be a working hash table. Here is a simple hash table implementation similar to the Java one. The table is an array of linked lists.

class HashTable<K, V> {
 static class Entry<K, V> {
 K key;
 V value;
 Entry<K, V> next;
 Entry(K key, V value) {
 this.key = key;
 this.value = value;
 }
 }
 Entry[] table = new Entry[8];
 int size;
 void put(K key, V value) {
 Entry<K, V> entry = table[indexFor(key)];
 while(entry != null) {
 if(entry.key.equals(key)) {
 entry.value = value;
 return;
 }
 entry = entry.next;
 }
 resizeIfNeeded();
 addEntry(new Entry<K, V>(key, value));
 size++;
 }
 void addEntry(Entry<K, V> newEntry) {
 int index = indexFor(newEntry.key);
 Entry<K, V> entry = table[index];
 if(entry == null) {
 table[index] = newEntry;
 } else {
 while(entry.next != null)
 entry = entry.next;
 entry.next = newEntry;
 }
 }
 void resizeIfNeeded() {
 if(size < table.length)
 return;
 Entry[] old = table;
 table = new Entry[old.length << 1];
 for(Entry<K, V> entry : old) {
 while(entry != null) {
 addEntry(entry);
 Entry<K, V> next = entry.next;
 entry.next = null;
 entry = next;
 }
 }
 }
 V get(K key) {
 Entry<K, V> entry = table[indexFor(key)];
 while(entry != null) {
 if(entry.key.equals(key))
 return entry.value;
 entry = entry.next;
 }
 return null;
 }
 int indexFor(K key) {
 return key.hashCode() & table.length - 1;
 }
}

As I mentioned in my comment, this sounds like an XY problem. I don't see how this is easier than using the Java data structures. Perhaps you have a different question to ask.

• under_the_sea_salad: Hi, thanks for you input. I actually think my question is valid, but I might have confused the community with references to ArrayList and hash-tables. In fact, all I am looking to do is be able to iterate through some number of objects. And each of these objects must be a Linked List. In this fashion, it "looks" like a hash-table because you can put collisions into Linked Lists.
• under_the_sea_salad: I might have actually solved my own question by adding a field next to my LinkedList implementation. This way, I can build MyHashTable (or whatever you'd like to call it) and iterate jump from first LinkedList to the next LinkedList much like LinkedList iterates through Nodes. Does this make sense? Sorry again, for any confusion.
• Radiodef: You can do what you describe but using generics it's pretty trivial to make any kind of List<List>. It also doesn't require you to add a provision internally to the class.
• under_the_sea_salad: At first I thought that I would have to change LinkedList to accept either Node or another LinkedList, but I'm all good now. Should I delete this question?
• Radiodef: Generics are really a better approach. As far as deleting it, you can't because it has an answer. The only way to delete it now is to flag it for a moderator to consider. In general questions should be deleted when they are of bad quality or not useful to others. If you leave it, please do consider accepting my answer as a solution even if you decide not to use generics after all.