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.
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.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments