my dog learned polymorphism*
The moose likes Beginning Java and the fly likes Circular Linked List Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Circular Linked List" Watch "Circular Linked List" New topic
Author

Circular Linked List

Ayukawa Madoka
Greenhorn

Joined: Feb 28, 2004
Posts: 27
i had no idea how to do this, can anyone help me?
1) Declare a class CircularList which contains the proper data structure which support the implementation of the circular linked list. Each node in the linked list contain only integer element. [3 marks]
2) Implement the method showDetail, which serves the purpose of displaying all the data above circular linked list. [5 marks]
3) Add to your class another method passMark, that takes an integer pass parameter. The method should return the number of nodes with values above the pass value. [5 marks]


hello everyone i'm new here.
Ayukawa Madoka
Greenhorn

Joined: Feb 28, 2004
Posts: 27
first of all, how do implement a circular linked list?
Stefan Wagner
Ranch Hand

Joined: Jun 02, 2003
Posts: 1923

Shall this be a ringbuffer - like the clock, where it starts from the beginning after reaching the end: '..., 10, 11, 12, 1, 2, ...'?
Is the size of this circular list known in advance, or shall it be possible to in- and decrease it's size?


http://home.arcor.de/hirnstrom/bewerbung
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
Circular operations often involve modulo arithmetic. The % operator gives you the mod or remainder of a division. So if I have a 5-slot list indexed 0-4 and I'm pointing at index 4, the "next" should be index 0. Mod is perfect:
index = ( index + 1 ) % 5;
5/5 has no remainder, so the index goes to 0.
Now, I'm talking about index, so you might be thinking ... array? If your circular list is of fixed size, an arry would be a fine implementation. Circular lists or buffers are usually fixed size, maybe configurable when you create it. Give you any ideas?
BTW: I get crazy trying to do mod on negatives. How would you go backward from 0 to 4 without going negative? That is, avoid this at index 0 (or any other):
index = ( index - 1 ) % 5;


A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi
Ayukawa Madoka
Greenhorn

Joined: Feb 28, 2004
Posts: 27
Shall this be a ringbuffer - like the clock, where it starts from the beginning after reaching the end: '..., 10, 11, 12, 1, 2, ...'?

Yes that's right, the next reference of the list's last node references the first node, instead of null.

Is the size of this circular list known in advance, or shall it be possible to in- and decrease it's size?
Now, I'm talking about index, so you might be thinking ... array? If your circular list is of fixed size, an arry would be a fine implementation.

since the question does not mention whether they want it to be fixed or expandable, so to make it a good program lets implement it as a reference-base list (expandable) . any suggestions?
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Circular Linked List
 
Similar Threads
Cycle graph
BST problem (Online waiting)
please help me on Generics!!!!
List.toArray() method
removal of elements in linkedlist of java