• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

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

 
Greenhorn
Posts: 12
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Marshal
Posts: 28177
95
Eclipse IDE Firefox Browser MySQL Database
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 12
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Marshal
Posts: 28177
95
Eclipse IDE Firefox Browser MySQL Database
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 12
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Bartender
Posts: 4179
22
IntelliJ IDE Python Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
 
Paul Clapham
Marshal
Posts: 28177
95
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 12
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 4179
22
IntelliJ IDE Python Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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...
 
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
 
John Meehan
Greenhorn
Posts: 12
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
 
Bartender
Posts: 612
7
Mac OS X Python
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
     
    Don't get me started about those stupid light bulbs.
    reply
      Bookmark Topic Watch Topic
    • New Topic