circular linked list queue issue

circular linked list with single external pointer

Page 1 of 1

6 Replies - 6511 Views - Last Post: 05 December 2010 - 08:56 PM Rate Topic: -----

#1 somewierdguy  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 05-December 10

circular linked list queue issue

Posted 05 December 2010 - 06:47 PM

I've unfortunately run out of ideas on what I'm doing wrong. I'm a little unsure of how exactly a circular list works with only one variable in terms of how you actually code it.
Currently, this is what I h ave for my list implementation. It's supposed to be a circular linked list queue with a single variable (rear) identifying the end of the queue. I keep getting null pointer exceptions when my programs hits the "dequeue" so I assume it's somewhere in there. Again, I'm not sure how these are implemented in terms of coding, and if additional information (i.e. what the interface it's extending looks like etc) let me know.

public class CircLinkedUnbndQueue implements UnboundedQueueInterface
{
    protected LLObjectNode rear;    // reference to the rear of this queue

  public CircLinkedUnbndQueue()
  {

    rear = null;
  }

  public void enqueue(Object element)
  // Adds element to the rear of this queue.
  {
    LLObjectNode newNode = new LLObjectNode(element);
    if (rear == null)
        rear = newNode;

    else
      rear.setLink(newNode);

    rear = newNode;

  }

  public Object dequeue()
  // Throws QueueUnderflowException if this queue is empty;
  // otherwise, removes front element from this queue and returns it.
  {
      Object element;
      element = rear.getInfo();
      rear = rear.getLink();
      if (rear == null)
        rear = null;

      return element;
  }

  public boolean isEmpty()
  // Returns true if this queue is empty; otherwise, returns false.
  {
    if (rear == null)
      return true;
    else
      return false;
  }
}



Is This A Good Question/Topic? 0
  • +

Replies To: circular linked list queue issue

#2 somewierdguy  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 05-December 10

Re: circular linked list queue issue

Posted 05 December 2010 - 07:20 PM

Didn't see an edit button, so here we go.
To be more specific, the enqueue portion seems to work fine. I tested it with a print statement to see what was being done and it seems to go thru ok. I've gotten the dequeue to "work" a few times by trying random getLink getInfo combinations but the best I could get it to do was spit out the last item i put in the queue and the first item with nothing between. I seem to be leaving null in there somehow, but I'm not entirely sure since, as I said before, I've been unable to find any good examples of how these single pointer circular queues work in terms of code to draw from.

Hopefully this helps clarify what issue I'm bumping up against and thanks to anyone who replies.
Was This Post Helpful? 0
  • +
  • -

#3 Dogstopper  Icon User is offline

  • The Ninjaducky
  • member icon



Reputation: 2857
  • View blog
  • Posts: 10,962
  • Joined: 15-July 08

Re: circular linked list queue issue

Posted 05 December 2010 - 07:24 PM

To be circularly linked, in the simplest definition, this means that once you hit the last node, you move back to the starting node. If you have double linked as well, then you have to swap that.

So, with one element, the head and tail nodes are the same. With two nodes, one is the head and the other is the tail. With more than that, other nodes go between. Always make sure that the tail node is ALWAYS connected to the head node.
Was This Post Helpful? 0
  • +
  • -

#4 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8315
  • View blog
  • Posts: 31,836
  • Joined: 06-March 08

Re: circular linked list queue issue

Posted 05 December 2010 - 07:24 PM

A List can exist with a pointer to the next node
A circular list requires also a pointer to the previous node

But for sure, a List cannot only have a pointer to the previous node
Was This Post Helpful? 0
  • +
  • -

#5 somewierdguy  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 05-December 10

Re: circular linked list queue issue

Posted 05 December 2010 - 08:05 PM

Ok, but, how would I link the first element entered to the last?
I understand the principle of linking the first to the last, but I'm not sure how one does that in terms of the code I suppose. If it doesn't qualify as doing my work for me I'd appreciate someone showing me how it's done, if I could doubly link this it'd be a lot easier but singly linked lists with only one external pointer and nothing counting items inserted requirement has me wracking my brain with little coming out but guesswork at this point.
Was This Post Helpful? 0
  • +
  • -

#6 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8315
  • View blog
  • Posts: 31,836
  • Joined: 06-March 08

Re: circular linked list queue issue

Posted 05 December 2010 - 08:33 PM

Have a look there
http://www.dreaminco...ng-comparables/
at post #10

just two posts away from yours. Do you have the same teacher ?
Was This Post Helpful? 0
  • +
  • -

#7 somewierdguy  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 05-December 10

Re: circular linked list queue issue

Posted 05 December 2010 - 08:56 PM

No, because he's using a circular array for some other problem. I'm expressly required to use a circular linked list with a single variable, rear, that I have to link the front too without any form of iterative counting.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1