Win a copy of Getting started with Java programming language this week in the Beginning Java forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

My ADT is disorganized  RSS feed

 
Naziru Gelajo
Ranch Hand
Posts: 166
1
Java Netbeans IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello, I am attempting to create an LRUCacheLinkedList. My get method though is not working the way it should be. Technically speaking, when a call to the method 'V LRUGet(K)' (Where V is some generic value and K (also a generic value) is a key linked to the value). The purpose of this method is


Theoritically speaking, I was smiling at myself thinking my LinkedList code would work, but boy was I wrong. Here is what I have and I will explain what I believe the function of my code was supposed to be.



So step my step, what I did was I created a new Node of type CacheNode (another class I created from scratch for the sake of this LRUCacheLinkedList ADT) called theNode. The method's intention is supposed to return a value based on the Key that is passed via the parameter. So I assign theNode to the next Node after head and I have it traverse the entire array before it gets to tail. So, if the Node's key matches with the parameter, I attempt to move the node to the Node before the tail Node in the doubly linked list. Thus, I first unlink the currentNode pointing to tail and instead have it point to 'theNode' (tail.previous.next now points to theNode). Next I have theNode next pointing to the tail Node and the Node previous pointing to the node that used to point to tail which now points to theNode (I assume this would now be tail.previous.previous.next as it is now 2 nodes before the tail Node.) I then have tail.previous point to theNode and then I return the value associated with the key. In theory, one would assume it would work, but I tested my code with a main method, and it definitely is not working as intended. Any ideas?
 
Norm Radder
Rancher
Posts: 1733
22
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
  it definitely is not working as intended.

Can you explain what it does
and what you intended it to do?
Can you post some debug output that shows what happened and add some comments showing what you expected?
 
Naziru Gelajo
Ranch Hand
Posts: 166
1
Java Netbeans IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Norm Radder wrote:
  it definitely is not working as intended.

Can you explain what it does
and what you intended it to do?
Can you post some debug output that shows what happened and add some comments showing what you expected?


Most certainly Norm, what my ADT does is that it effectively creates an LRU Linked List (least recently used) and it allows for the adding of a cached node which holds a key and a value (both of which are generic values). Essentially, what happens is that when a new value with the same key is added, the old value is overwritten and a new value is placed where the key is, however, the dataset moves to the back of the list. LRU is essentially a widely used algorithm for memory management. A cache is too small to hold all the data we need, so eventually some of these values get removed. We retain items in the cache that we use over and over, but get rid of the items in the cache that are not used often. So I've implemented this in an ADT. For the most part it works, but somewhere, where the retrieve method is called (LRUGet(Key)) the linked list goes bonkers as if I'm not linking things properly.
 
Campbell Ritchie
Sheriff
Posts: 53612
127
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome to the Ranch

Why are you using the == operator (line 10) on a reference type? That won't work reliably.
 
Naziru Gelajo
Ranch Hand
Posts: 166
1
Java Netbeans IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:Welcome to the Ranch

Why are you using the == operator (line 10) on a reference type? That won't work reliably.


LOL good question I will go ahead and fix that. Thanks!
 
Naziru Gelajo
Ranch Hand
Posts: 166
1
Java Netbeans IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I just don't get where I'm going wrong. I thought I linked everything correctly in this linked list.
 
Norm Radder
Rancher
Posts: 1733
22
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
the linked list goes bonkers

Can you post some debug output that shows what happened and add some comments showing what you expected?
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!