File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Java in General and the fly likes Creating a Circular LinkedList Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of OCM Java EE 6 Enterprise Architect Exam Guide this week in the OCMJEA forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Creating a Circular LinkedList" Watch "Creating a Circular LinkedList" New topic
Author

Creating a Circular LinkedList

Sam Thompson
Ranch Hand

Joined: Jul 05, 2011
Posts: 93
    
    1
Hi everyone:

I am just wondering if some of you can give me some tips and pointers as how to develop a circular linkedlist. I know it may seem simple, but I am not very familiar as to how to construct it.

Also, since I am going to be using the circular linkedlist for a repetitive poker game simulation, I am also wondering how you can store data (names, scores, bets, wages, etc.) into each space or node?

Any help would be greatly appreciated.

If you want or need more information as to how my project applies, check out the links below:

http://www.coderanch.com/t/592825/java/java/Do-while-loop-index
http://www.coderanch.com/t/592416/java/java/Method-not-working-or-operating

Thanks in advance everyone!

S.T.
Kemal Sokolovic
Bartender

Joined: Jun 19, 2010
Posts: 825
    
    5

You'll first need to implement a class that will represent each node in your structure. That class will keep the value of each node, as well as references to previous and next element (I suppose it's doubly linked list) of the current one, methods for accessing them, etc.:

Then, when you start coding your LinkedList, you'll have to declare an element usually referred to as sentinel or null object; this element will actually represent both start and end of your list. The next node of sentinel is actually your first element, and the previous node of sentinel is the last element in your list.

Afterwards, it's the matter of implementing necessary methods, iterator for traversing the list, etc. But this is the basic idea.


The quieter you are, the more you are able to hear.
Sam Thompson
Ranch Hand

Joined: Jul 05, 2011
Posts: 93
    
    1
For each player there will be multiple variables stored with data.

How do I store this exactly in the doubly linked list? How should the methods be coded?

S.T.
Kemal Sokolovic
Bartender

Joined: Jun 19, 2010
Posts: 825
    
    5

For the first one, instead of having

in your ListNode class, you'll have:

where you implement Player class to store all the data you want to have for each player (that's one possible solution).

How should the methods be coded?

Well, this is too general, I can't provide entire solution for you, because that's not how things work here. You need to show you are actually doing something.
Try with implementing your List interface, with just a few methods to begin with, and try to implement them in your own LinkedList. Note that you can also use java.util.List interface.

When implementing methods for inserting or deleting value from list, you'll need to update those previous and next reference each time. Try drawing list on a paper (with arrows showing references), and then draw what would happen if value is added to or deleted from list. When you get what happens there, try to implement it and come back if you stuck somewhere.
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11256
    
  16

Sam Thompson wrote:For each player there will be multiple variables stored with data.

How do I store this exactly in the doubly linked list? How should the methods be coded?

S.T.

you define a player class. something like


You then define you linked list to hold Players.


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Sam Thompson
Ranch Hand

Joined: Jul 05, 2011
Posts: 93
    
    1
Kemal (et al):

Here is what I have so far:



Sam Thompson
Ranch Hand

Joined: Jul 05, 2011
Posts: 93
    
    1
Fred:

Could you describe what methods I would need to make the list a doubly linked one exactly?

What code?

Thanks

SAM

PS: I am still learning about this kind of data structure; it's still unfamiliar territory to me.
Kemal Sokolovic
Bartender

Joined: Jun 19, 2010
Posts: 825
    
    5

If you want to implement your own datastructure (circular LinkedList) for the program you need, the design of classes should be changed. As I can see, there are some things that should not be in PlayerNode class, nor PlayerLink class is necessary.

Try it this way (just talking about datastructure now, once you have it done, other parts are specific for your program logic).

Define class Player as following:


Then, as basic part for your LinkedList implementation, you can define a ListNode class. It represents each node of the list, as well as that sentinel (both head and tail):


Suppose you declared List interface to support just some basic operations (you can extend it further if necessary):


Now, that you have your own node class (to keep player's data and that is suitable for LinkedList), you can write code representing actual datastructure:


This is what the basic structure should look like. Once you complete the List interface with all the methods that you need, you should just provide iterator for your linked list to easily traverse over elements (you can implement it as inner class of your LinkedList class). When you have that, data structure is completed as you want it to look like, and ready to be used in your program.

Edit: Wow, this came out to be a very long post! Sorry for writing single line comments in places where I should put documentation comments; oversight I made in speed.
Sam Thompson
Ranch Hand

Joined: Jul 05, 2011
Posts: 93
    
    1
Kemal (and Fred):

Thanks for the guidance so far. I will try to develop the code based on your suggestions.

Once I have some of it done, I will post it to see if it is done correctly.

One more thing, you need an Iterator for a LinkedList right, to go through each node?
How do you set that up?

Again, I apologize for the naivete.

S.T.

PS: Don't worry if your posts are long, the more the better. And the more that will help me get this done and designed more efficiently.
PS (2): If this helps, here is my PokerPlayer class thus far:



I am guessing from here you would change the ArrayList to a LinkedList, right? The main class for where objects PokerPlayer are used is PokerGenerator, and I posted the link to find it at the beginning of the post.

Thanks so much for your help and for your help in advance guys!

S.T.
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11256
    
  16

so a couple of things...

1) a linked list really has nothing to do specifically with java. It is a concept. It is one of many data structures you will learn about in any CS curriculum.
2) a circular linked list is really not much different from a 'normal' linked list. you just build a normal linked list, then have the last node point to the first, and the first point to the last (if it is a double linked list.
3) the linked list should contain Node objects. Those node object should contain Player objects.
4) The Node class should have methods to move to the next node and the previous node.
5) The concept of a linked list basically builds in the iteration.

so, you would create your first Player object. You would add it to a Node. You then add that Node to your linked list. You then create your second Player. You add it to a new Node object, and then add that Node to your linked list. If the linked list is coded right, all the next and previous references get set automatically.

So you can then create a few Node references. Commonly, ones are built to point to the first and last, although in a circular one that concept doesn't make much sense. You do need SOME reference to SOME node, else the whole thing will get GC'd.

So, assuming you have your currentNode reference, you can do this:

currentNode = currentNode.nextNode();//or whatever the actual method name is.

This will 'move' your current node to the next one in the list. You can then access that node's Player object, and find out that player's name, bank balance, or whatever:

int currentBalance = currentNode.Player.getBalance();

I would probably have a dealer reference to a node, then another one named something like a currentPlayer. At the start of each hand, you would do something like

dealer = dealer.nextNode();// to set the next player as the current dealer;
currentPlayer = dealer.nextNode();//the person after the dealer is the next to act.

As each player bets, checks, raises or folds, you handle that setting whatever variables you need in both currentPlayer and possibly an int potSize. then you move currentPlayer to the next node:

currentPlayer = currentPlayer.nextNode();

and have that person act. You may need another reference to lastPlayerToRaise. Each time a player raises, you set this reference to the currentPlayer. The, eventually when you loop around and currentPlayer == lastPlayerToRaise, you know everyone is done betting...



You may realize that a poker game is NOT a simple thing to write. There is a LOT going on here, and you need to remember to compartmentalize different things. I would strongly suggest you forget about poker for a bit, and play with a simple linked list that maybe only stores an int. Play with it, moving around, adding and deleting nodes until you are comfortable with the data structure. Once you have a good feel for it, only THEN consider using it in your poker game.
Kemal Sokolovic
Bartender

Joined: Jun 19, 2010
Posts: 825
    
    5

By my opinion, in the context of LinkedList, iterator is not optional, since that's the way datastructure works - you traverse it using references (next and previous) between nodes and not indexes. If it's not used in that manner, than the whole concept of datastructure like this is a waste, you could as well use ArrayList or something else.

On the other hand, using iterator gives a lot advanteges.
Suppose you want to include or exclude some nodes based on the criteria you define (e.g. you just want to get those players that are still at poker table, and exclude those that are out of money). Using array-based iteration (loops that traverse the structure based on the index) you would need to hard-code the criteria and possibly repeat the same code more than once. Suddenly you feel like changing it - you need to modify it wherever it appears. With iterator you can accomplish this in a natural manner, hiding the datastructure that's under the hood. And by wrapping it, you can easily create a filtering one that will traverse only those values that satisfy your criteria (the example I mentioned before).

Anyway, it's a very powerful mechanism, and I would suggest you play with it for a while to grasp the idea. Once you complete your datastructure and test it, you can proceed with other parts of the program.
Sam Thompson
Ranch Hand

Joined: Jul 05, 2011
Posts: 93
    
    1
Kemal and Fred:

Thank you so much for your assistance with my project thus far.

Fred, I will play around with a simpler version of a doubly linked list. It would be best if I had a more detailed idea of how it would work.

I will try both of your suggestions and see where it takes me.

Thanks again!

SAM
Junilu Lacar
Bartender

Joined: Feb 26, 2001
Posts: 4458
    
    6

A few comments on form:

Don't get cute with names: betB4Flop is not symmetric with betAfterFlop. Prefer spelling it out so the reader doesn't have to do the mental translation from "betB4" to "betBefore": betBeforeFlop

There is no point in this method:

It might as well be written as the code below and there's no point in calling a method when all you are really returning is the parameter that you pass in:

This code is redundant:

All you really need is this:

All other methods that follow the same form can be changed similarly.

Junilu - [How to Ask Questions] [How to Answer Questions]
Sam Thompson
Ranch Hand

Joined: Jul 05, 2011
Posts: 93
    
    1
Junilu:

Thank you for the input regarding naming conventions. I have made considerable changes since I posted the code you saw. I don't call it betB4Flop anymore, now it is betPreFlop and betPostFlop. Should make sense.

As I kept writing and editing the main class (PokerGenerator), I have already deleted some methods that I thought were redundant. It is a slow process but it will be worth the effort in the end.

Thanks again.

S.T.
 
wood burning stoves
 
subject: Creating a Circular LinkedList