File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Beginning Java and the fly likes Circular Queue Linked List using LinkedList api without adding or removing nodes? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Circular Queue Linked List using LinkedList api without adding or removing nodes?" Watch "Circular Queue Linked List using LinkedList api without adding or removing nodes?" New topic
Author

Circular Queue Linked List using LinkedList api without adding or removing nodes?

John Meehan
Greenhorn

Joined: Oct 28, 2011
Posts: 12

I've got a programming assignment where I have to create a circular queue linked list and I'd like to use the LinkedList api. The problem is my professor says "Note that dequeue something just means remove the data not the node." Yet everything I've seen with the LinkedList api has nodes being added or removed in tandem with the data. If I had my way I'd just make a counter with the max size of the queue and not add more data when you get past that, but I'm certain that's not in the spirit of the assignment.

Is there a way to keep x number of nodes in the queue and just manipulate the elements on those nodes using the LinkedList api, or will I have to write my own?

Thanks for the help.
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18127
    
    8

This circular queue has a fixed number of nodes, if I'm not mistaken. So yes, if that's the case then removing nodes would be the wrong thing to do.

In that case I would make "remove the data from the node" mean "get the data from the node and replace it by null". That would mean you couldn't put null values into your queue, but probably that isn't a problem.
John Meehan
Greenhorn

Joined: Oct 28, 2011
Posts: 12

I figured that's what I'd have to do. Is it possible with the LinkedList API though? Methods like LinkedList.add and LinkedList.remove add and remove the node as well as the data.
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18127
    
    8

Sure it is, have a look at the documentation and you'll see there's a "set" method. (Didn't find the docs? Didn't know there were docs? Follow the link here: LinkedList <== yes, that's a link.)
John Meehan
Greenhorn

Joined: Oct 28, 2011
Posts: 12

Thanks for that.

An additional question though... Is it just me or is this an awful way to use a linked list? Circular queues make sense for arrays, but for linked lists it just seems silly.
Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 3947
    
  17

John Meehan wrote:Thanks for that.

An additional question though... Is it just me or is this an awful way to use a linked list? Circular queues make sense for arrays, but for linked lists it just seems silly.


I agree. You would have to write your own add()/poll() methods anyway, and the set() method you need to use would be less efficient than direct-access in an array. If you are writing your own wrapper - mind-as-well do it using an efficient backing store.


Steve
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18127
    
    8

I have to say, I don't really know what a "circular queue linked list" is. It isn't one of the standard data structures, or rather, its name looks like a couple of them mashed together somehow. Perhaps it would be better to describe the features this queue/list thing is supposed to have.
John Meehan
Greenhorn

Joined: Oct 28, 2011
Posts: 12

Sorry for the confusion, I should have said it's a circular queue implemented with linked lists.

A Circular queue is more easily explained with an array. With a regular queue in an array, if you remove an element from the start you have to shift all the remaining elements one to the left (decrement the indices). With a circular queue, you have two pointers, one for the head and one for the tail. Instead of the data moving, you move the pointers to the new start or new end when you add or remove an element from the queue. It's called "circular" because the pointers are able to wrap around the ends of the array when you add or remove data. It lets you use an array for a queue with constant-time dequeue methods instead of n-time, since you only have to shift one pointer instead of all the elements in the array.

There's a decent wiki explanation with pictures: http://en.wikipedia.org/wiki/Circular_queue#How_it_works

With linked lists, it would make sense to have a queue where the front and the end points to the same sentinel node, so queuing and de-queuing is just a matter of putting new nodes on one side of the queue and removing them from the other side. But for some strange reason my professor wants something that looks like the array version instead. And my code just looks like moose droppings.
Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 3947
    
  17

It is very confusing. A linked list is really only good at allowing growing data storage without incurring a cost of growth. A circular queue is usually a fixed size collection, so no worries about cost of growth. If you need a queue that can grow (i.e. has the benefits of a linked list) you don't really have a circular queue. Unless you want a growing collection that lets you add to the tail, remove from the head, and iterate in circle?? That doesn't seem like a likely scenario though... If it was, I would probably leave the LinkedList implementation in place and write a CircularIterator instead...
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7053
    
  16

John Meehan wrote:There's a decent wiki explanation with pictures: http://en.wikipedia.org/wiki/Circular_queue#How_it_works
With linked lists, it would make sense to have a queue where the front and the end points to the same sentinel node, so queuing and de-queuing is just a matter of putting new nodes on one side of the queue and removing them from the other side.

Fine, but I doubt you'll have much joy basing it on LinkedList because it hides Nodes from you.

Furthermore, that class's implementation may be overkill since it is doubly-linked, whereas an LL-ring-based queue only really needs a forward pointer (oddly enough, I've been working on that very thing myself recently ).

But for some strange reason my professor wants something that looks like the array version instead. And my code just looks like moose droppings.

Well, that link appears to have an explanation of how to do that too. One nice thing about an array is that it's simple and fast - and furthermore, if it's size is a power of 2, you can use bit masking to get your "circular index", which is about as fast as it gets in Java. On the other hand, it's more prone to concurrency bottlenecks.

However, given his instruction that "dequeue something just means remove the data not the node" basically nixes the idea of a LL, since the whole point about them is that they're dynamic.

If you're interested, my (single-linked) LL-queue ended up with the concept of an "anchor" - a null node that logically sits between the last node and the first and originally simply points to itself. This allows "add first", "add last" and "remove first" ops that all work in O(1) time and require very little syncing; but "remove last" is such a pain that I haven't even bothered with it.

Winston

Isn't it funny how there's always time and money enough to do it WRONG?
Artlicles by Winston can be found here
John Meehan
Greenhorn

Joined: Oct 28, 2011
Posts: 12

Winston Gutkowski wrote:
Fine, but I doubt you'll have much joy basing it on LinkedList because it hides Nodes from you.


That was part of my frustration. I did actually find a way to do it with linked lists and doing element manipulation using LinkedList.set, but I had to initialize the array with this block:


Furthermore, that class's implementation may be overkill since it is doubly-linked, whereas an LL-ring-based queue only really needs a forward pointer (oddly enough, I've been working on that very thing myself recently ).


If you're using a singly-linked list, how do you add a to the end of the queue without traversing the entire list? Does your sentinel point to both ends simultaneously? Doesn't exactly make it a real singly-linked list then.

Well, that link appears to have an explanation of how to do that too. One nice thing about an array is that it's simple and fast - and furthermore, if it's size is a power of 2, you can use bit masking to get your "circular index", which is about as fast as it gets in Java. On the other hand, it's more prone to concurrency bottlenecks.


The only issue there is that there were two problems, one explicitly asking us to use arrays and one linked lists. So I had to do it with linked lists, and I had to do it without removing nodes, which is why the entire program was awkward.

Like I said I did eventually get it to work, but I'd never use this for anything reasonable ever.
Steve Fahlbusch
Bartender

Joined: Sep 18, 2000
Posts: 556
    
    7

I would hazard to say, this wound have been much simpler if you implemented your own double linked list rather then try to wrap up the LinkedList class provided.

But that is so with academic projects......The instructor is expecting you to jump through hoops so you get better learnt :-)

Glad you got your assignment complete, but more so that you also understanding the shortcomings so that you don't repeat them (if not forced to).

-steve
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7053
    
  16

John Meehan wrote:If you're using a singly-linked list, how do you add a to the end of the queue without traversing the entire list? Does your sentinel point to both ends simultaneously? Doesn't exactly make it a real singly-linked list then.

Nope. All you need is a bit of "node magic".

As you've worked out, one of the major problems with SLL's (for sake of argument, forward-linked) is that a remove or append would seem to need access to the "previous" (or last) Node. However, you can simulate an "add before" or "remove this node" by doing it logically:

addBefore(newValue)
  • Create a new Node that points to 'next' with a copy of this Node's value in it
  • Change this one's value to newValue
  • Finally, point this Node to the created Node

  • removeThis()
  • Copy 'next's value to this Node
  • Change this Node to point to the one after 'next'

  • Obviously, there's slightly more syncing involved to make sure that Iterators don't see values in an inconsistent state; but actually, having an anchor Node eliminates most of that - at least for addBefore() - because you can simply have them stop when next == anchor.

    Like I said I did eventually get it to work, but I'd never use this for anything reasonable ever.

    Well, well done. Personally, I think your prof's instructions have hamstrung you a bit for an LL solution (and I can't imagine that anyone would ever implement it that way); but, as Steve said, maybe he did it for instructional purposes.

    Winston
     
    I agree. Here's the link: http://aspose.com/file-tools
     
    subject: Circular Queue Linked List using LinkedList api without adding or removing nodes?
     
    Similar Threads
    Whak kind of array suits my needs better ?
    Hash Table, Hash Map, Linked List of objects
    about notify() and wait()
    Radix Sort
    Converting objects to char