Ihr code hier
machen Sie das schneller
I love how they use the formal pronouns when addressing you. We barbaric Norwegians stopped doing that sometime around the 1960s. They insist on writing the Javadoc in German (they do the same thing here), which makes it a tad bit harder for me to get you some hints, but I'll give it a god*.
Doubly linked lists are pretty easy - you need a class DoublyLinkedList, and a (possibly inner) class DoublyLinkedListNode. The head should always have a previous value of null, and the tail should always have a next value of null. That's the java way of doing it.
public class DoublyLinkedList<DataType> {
MyLinkedListNode<DataType> head;
MyLinkedListNode<DataType> tail;
}
public class DoublyLinkedListNode<DataType> {
DataType data;
MyLinkedListNode<DataType> previous;
MyLinkedListNode<DataType> next;
}
Then the insertFirst method in the DoublyLinkedList would be:
public void insertFirst(DataType data) {
DoublyLinkedListNode<DataType> node = new DoublyLinkedListNode<DataType>(data);
head.setPrevious(node);
head = node;
}
And so on.
The hash table is also really straight forward - it's a map from an int to a resizable list of some kind, and you use the hashCode of the element you insert as the key of the map. The map can be implemented as an array, where you use the index of the array as the key.
This means that you have an array of lists (for example your doubly linked ones):
map = DoublyLinkedList[]
And inserting an element o means inserting into the array at index o.hashCode:
public void insert(DataType data) {
map[data.hashCode].addFirst(data);
}
Check that the map has that index. If it doesn't (IE. it's too small), you can make an array of double the size of the old one, and transfer all of the elements. Insertion is still an O(1) operation, if you look at the average insertion time (I'll save the proof for when you get it on an exercise sheet in some Data Structures or Algorithms course :p). You could also just use ArrayLists:
map = ArrayList<DoublyLinkedList>();
The way the built in ArrayList inserts elements is exactly the algorithm I just described. To do the LRU (if I've understood what the LRU is), simply removeLast on the LinkedList at the array space you're inserting in if it's got more than the max number of elements. Also, you shouldn't fill the array space with a list before you need that list, so the insert method will also need to check if the index of the array is currently null.
Hope that helps.
* When I found that typo, I realized that it needed to stay, because giving you a God is a pretty cool thing to do, I recon.