PDA

View Full Version : Linked lists in Java




CANEHDN
Jul 6, 2006, 02:26 PM
I need help with some homework. I need to create a linked list of all file names in a directory that end with .class. Can anyone help?



savar
Jul 6, 2006, 02:54 PM
I need help with some homework. I need to create a linked list of all file names in a directory that end with .class. Can anyone help?

Do you know what a linked list is? If you understand the concept, the code comes naturally. A linked of file names makes no sense to me, which makes me think you or your teacher doesn't know what they are. Maybe post more details?

Off the top of my head:
edit: insert code tags
class LinkedList {
class Node {
int data;
Node next;
Node(Node next) {
this.next=next;
}
Node getNext() {
return next;
}
}

Node start;
}

CANEHDN
Jul 6, 2006, 03:02 PM
I have to create a linked list of all the file names in a directory ending in .class. For example: There is a directory with 5 files: 1.class, 2.class, through 5.class. I need to create a linked list that has each of those files names. I hope this makes sense. Thanks

jsw
Jul 6, 2006, 03:53 PM
This app takes the file path (where the class files are) as the first argument.

This is about as reduced as it can be, mainly because it'll force you to pretty it up. I print the names just so you can verify that it works. There is no error checking, etc. - just a proof of concept. I assume you're using Java 5.

I also assume you can use all of the Java classes, including LinkedList.


import java.io.*;
import java.util.*;

public class ClassFileLister
{
public static void main(String[] args)
{
for (String name : new LinkedList<String>(Arrays.asList((new File(args[0])).list(new FilenameFilter() {
public boolean accept(File directory, String name)
{ return (name.endsWith(".class")); } }))))
{
System.out.println(name);
}
}
}


Edit: OK, if you're not sure how to use linked lists, that was probably too extreme. Here's a simplified version of exactly the same logic (again with no comments or error checking):

import java.io.*;
import java.util.*;

public class ClassFileLister
{
static class ClassFilenameFilter implements FilenameFilter
{
public boolean accept(File directory,
String name)
{
return (name.endsWith(".class"));
}
}
public static void main(String[] args)
{
String desiredPath = args.length > 0 ? args[0] : ".";
File desiredPathFile = new File(desiredPath);
String[] classFileNameList = desiredPathFile.list(new ClassFilenameFilter());

LinkedList<String> classFileList = new LinkedList<String>(Arrays.asList(classFileNameList));

for (String name : classFileList)
{
System.out.println(name);
}
}
}

CANEHDN
Jul 6, 2006, 04:20 PM
Freakin' awesome. Works great. Thanks a bunch.

aquanutz
Jul 7, 2006, 12:15 AM
I just hope you now know what linked lists really are. Especially if you are a CS major...

CANEHDN
Jul 7, 2006, 09:45 AM
I know what they are. This is card game program we're writing and each card has to be written as it's own class. It's a pretty big project.

savar
Jul 7, 2006, 11:14 AM
I know what they are. This is card game program we're writing and each card has to be written as it's own class. It's a pretty big project.

Yikes, each card is its own class? Was this your decision or the teacher's?

rand0m3r
Jul 8, 2006, 09:44 AM
maybe he meant each card is an object.

bousozoku
Jul 8, 2006, 10:14 AM
maybe he meant each card is an object.

I'd hope each one would be an object since it would make more sense to draw from one basic card class or four basic card suits.

SilentPanda
Jul 8, 2006, 11:35 AM
Speaking of playing cards and Java....

http://java.sun.com/j2se/1.5.0/docs/guide/language/enums.html

savar
Jul 8, 2006, 03:26 PM
maybe he meant each card is an object.

Yeah, but then the next sentence was, "It's a pretty big project." It certainly would be if you tried to write 52 classes just to data model a deck of playing cards.

CANEHDN
Jul 10, 2006, 04:13 PM
Have you guys ever heard of Munchkin? We're writing a networking game of that. We decided to make each card it's own class because of the all the different things each card can do. We figured it would be easier to do it that way.

bousozoku
Jul 10, 2006, 04:48 PM
Have you guys ever heard of Munchkin? We're writing a networking game of that. We decided to make each card it's own class because of the all the different things each card can do. We figured it would be easier to do it that way.

I hope you're basing it on a single class and adding special behaviours from there.

SilentPanda
Jul 10, 2006, 05:13 PM
I own Munchkin and 3 or 4 expansions for it and also code in Java. If you're making each card its own class you're going about it in a terrible way. Set your classes up like the cards are set up... first make a treasure card class and a dungeon card class. Then bring those down into items, monsters etc... There are common properties between cards you just have to find them. Certain cards have a gold value, monsters have levels, etc... if you make a class for every card you might as well just scan them all in and have it display the images on your screen.

CANEHDN
Jul 10, 2006, 07:00 PM
We will be scanning every card and having the images display. We will also have door cards and treasure cards. But in order to have full effects from each card the best way to do it is each card have it's own class.

savar
Jul 10, 2006, 10:55 PM
We will be scanning every card and having the images display. We will also have door cards and treasure cards. But in order to have full effects from each card the best way to do it is each card have it's own class.

Hey man, I guarantee you that its not the best way. I took a look at the game and perused the rules quickly. 168 cards!?! 168 classes is a *huge* application, especially for some intro CS students.

The best way to do it would be to have a Card class, then subclass that to create the various types of Cards. Then I suggest that you define cards as data files which go into a particular directory, and your application reads them in and instantiates the right kind of Card subclass based on the data in the file. Each card can still have its own image and rules, etc. but this way you're removing the data from the application. What if you compile all 168 classes, then realize you made a typo -- one person in your group can't spell dungeon and you have to change 140 occurences of "dungoen" in 70 different classes, each one has to be recompiled. Do yourself a favor and put the game data into data files, not code files. It's a little more work on the front end but will save you hours of work on the back end and will pay for itself many times over. Not to mention it would knock the socks off of your teacher. You're working on a very ambitious project for a few novice developers, but if you nail the design you will have a very impressive program to show off at the end of it.

Just keep in mind, your main goal should be to minimize redundancy as much as is reasonably possible. Don't have 168 different classes if they all have something in common.

SilentPanda
Jul 10, 2006, 11:12 PM
Hey man, I guarantee you that its not the best way. I took a look at the game and perused the rules quickly. 168 cards!?! 168 classes is a *huge* application, especially for some intro CS students.

168 cards doesn't even include the expansions if he ends up wanting those.

But to the OP... seriously... listen to what others have said about not making 168 class files. If you spend even a day or two categorizing the cards and finding similar traits in them you will save weeks of coding. Heck one guy can put the various data bits into a data file while somebody else codes classes to interpret them.

You can have (for instance) a method for you card class to force a player to lose X items of Y size and Z whatever. Every single card can have a gold value attribute (-1 for cards with no value). Every card can have a level (-1 for cards with no level). A method to remove levels from a given player. A method to lose X cards from a given player... it goes on and on. Then if you decide to add the expansion packs it will be a snap as most of the code will have already been written.

Don't assign this batch of cards to this person and this other batch of cards to another person. Have somebody (or as a group) go through the cards and extract the logic and data. Then figure out what logic needs to be made into methods and with what parameters and separate those out to different people.

Although I suppose it's your time and you're free to use it as you wish. :D

CANEHDN
Jul 11, 2006, 10:05 AM
Our card class which all monsters will inherit from will have the similar traits such as level ups and downs but when it comes to the special things that a lot of cards have you have to do something else. This also makes it easier when adding new cards such as the expansions. You won't have to go and change code already written.

ChrisBrightwell
Jul 11, 2006, 10:33 AM
But to the OP... seriously... listen to what others have said about not making 168 class files. Agreed. A single "Card" interface (to be implemented a few times) and a good set of data will be much cleaner and much more educational than brute-forcing 160+ classes.

bousozoku
Jul 11, 2006, 10:44 AM
Our card class which all monsters will inherit from will have the similar traits such as level ups and downs but when it comes to the special things that a lot of cards have you have to do something else. This also makes it easier when adding new cards such as the expansions. You won't have to go and change code already written.

As this is probably a one-off project and you'll never touch the code again, I can understand that you don't want to think too hard about it.

However, as many of us have learnt in many years, it's much easier to maintain code that has been properly designed. I believe that a lot of people end up re-working their base classes after a while because they find that they're consistently adding one attribute or another to almost all of their individual uses of it.

Then again, what project is more frequently maintained than a beginner's project?

SilentPanda
Jul 11, 2006, 10:46 AM
Then again, what project is more frequently maintained than a beginner's project?

There's nothing more fun than looking at code you wrote "in your early years" and remembering... "it took me 3 weeks to read in a text file?"

:)

CANEHDN
Jul 11, 2006, 01:16 PM
You're right on the fact that I'll never touch it again. But the "Captain" of the group probably will. He is the ultimate nerd and is thrilled to death about this project. Once this class is over, I'll post the final project, if it's complete. I'd like to get people's opinions on it. I do appreciate all the ideas and suggestions though.

Also we won't be adding every monster in the game just a few to make sure the code works. There wouldn't be enough time to do that. Even if we did everything in a card class there would be too much code to write with the amount of time we have.

I do have to write a shuffle() function for a linked list. Any suggestions on the best way to do that? The reason I'm asking the stuff on linked lists is I was never too good at the data structures stuff. Arrays I'm ok with. Any ideas would be great. Thanks

bousozoku
Jul 11, 2006, 01:28 PM
There's nothing more fun than looking at code you wrote "in your early years" and remembering... "it took me 3 weeks to read in a text file?"

:)

I remember waiting for the train and hearing students complaining about writing 500 lines of COBOL code and thinking to myself "what can you do with only 500 lines of COBOL?" :D

At the time, I was porting a screen design application built in C to another platform and it only had one comment in any of the files and it was completely useless as it only contained the function name of the function it preceded.

Poor design = waste of effort later.

jsw
Jul 11, 2006, 01:58 PM
Poor design = waste of effort later.
Not to mention that it's just offensively ugly. Good design, though, is beautiful.

CANEHDN
Jul 11, 2006, 02:24 PM
I do have to write a shuffle() function for the linked list. Any suggestions on the best way to do that? The reason I'm asking the stuff on linked lists is I was never too good at the data structures stuff. Arrays I'm ok with. Any ideas would be great. Thanks

GeeYouEye
Jul 11, 2006, 03:08 PM
I do have to write a shuffle() function for the linked list. Any suggestions on the best way to do that? The reason I'm asking the stuff on linked lists is I was never too good at the data structures stuff. Arrays I'm ok with. Any ideas would be great. Thanks
Put the list data into an array, shuffle it, and put it back in the list?

CANEHDN
Jul 11, 2006, 03:18 PM
Really? That seems a little messy.

SilentPanda
Jul 11, 2006, 03:23 PM
I do have to write a shuffle() function for a linked list. Any suggestions on the best way to do that? The reason I'm asking the stuff on linked lists is I was never too good at the data structures stuff. Arrays I'm ok with. Any ideas would be great. Thanks

Why write a shuffle function when it already exists?

Collections.shuffle (http://java.sun.com/j2se/1.5.0/docs/api/java/util/Collections.html#shuffle(java.util.List))

CANEHDN
Jul 11, 2006, 03:32 PM
That works perfectly. Who knew it could be that easy. I love, love it!! Thanks

Another thing. I know this is a stupid question but how do I add the image to show underneath my name?

SilentPanda
Jul 11, 2006, 03:52 PM
Another thing. I know this is a stupid question but how do I add the image to show underneath my name?

Post 417 more times. (http://guides.macrumors.com/Help:MacRumors_FAQ#I_can.27t_upload_an_avatar)

bousozoku
Jul 11, 2006, 03:54 PM
That works perfectly. Who knew it could be that easy. I love, love it!! Thanks

Another thing. I know this is a stupid question but how do I add the image to show underneath my name?

Perhaps, you should read the FAQ. (http://guides.macrumors.com/Help:MacRumors_FAQ) :)

CANEHDN
Jul 11, 2006, 06:32 PM
That would have been too easy.

jeremy.king
Jul 14, 2006, 08:03 AM
That would have been too easy.

So would be writing a handful of Card classes :eek:

As for shuffle - one algorithm I have seen is to randomly swap two cards a random large number of times (ie > 10000).

ChrisBrightwell
Jul 14, 2006, 09:24 AM
As for shuffle - one algorithm I have seen is to randomly swap two cards a random large number of times (ie > 10000).Getting a truly random number is pretty difficult.

SilentPanda
Jul 14, 2006, 09:25 AM
Getting a truly random number is pretty difficult.

I would hope that most of the programming world has accepted the lack of a "true" random number overall. Just use Collection.shuffle() and it'll do well enough. Keep in mind we're shuffling a deck of cards not doing cryptography.

jeremy.king
Jul 14, 2006, 09:51 AM
Getting a truly random number is pretty difficult.

Really?

http://www.thedailywtf.com/Images/200607/screenshot24ga.png

:eek:

Seeding with time is random enough for this purpose.

SilentPanda
Jul 14, 2006, 10:03 AM
Seeding with time is random enough for this purpose.

Have you ever:

A) Read the Bible?
B) Seen a monkey bang on a keyboard?

1st Brian 3:18 (New MacRumors Version) - "And when Adam asked the LORD about the randomness that was in the world the LORD replied, "This is a talent I cannot give to man but only to the monkeys. They shall have dominion over all random numbers and it will be for the benefit of man." Adam trusted in the LORD and gave a monkey a typewriter." *

* - This is largely believed to be the first instance of a monkey attempting to write Shakespeare. As Shakespeare had not been born yet it is believed that this passage in conjunction with 1st Brian 7:23 may hint that Shakespeare actually copied from a monkey and not the other way around.

ChrisBrightwell
Jul 14, 2006, 10:07 AM
Really?[/qoute]Yes, really. Every RNG we've seen at work (all Java-based) has developed "habits" that produce predictable numbers.

[quote]http://www.thedailywtf.com/Images/200607/screenshot24ga.pngI've seen a few variations of that. :) Regardless, that doesn't produce a "true" random ... esp in the 10,000+ range.

Seeding with time is random enough for this purpose.Fair enough ... I was just stating that a "true" random is incredibly difficult.

jeremy.king
Jul 14, 2006, 10:41 AM
Yes, really. Every RNG we've seen at work (all Java-based) has developed "habits" that produce predictable numbers.

I've seen a few variations of that. :) Regardless, that doesn't produce a "true" random ... esp in the 10,000+ range.

Fair enough ... I was just stating that a "true" random is incredibly difficult.


Lighten up...My post was meant to be humurous. Everyone should know generating a random number on a computer would require an algorithm, which would mean its not truly random - but deterministic. If you seed properly, you should not see patterns or habits. I would be interested to see what RNGs you are using.

CANEHDN
Jul 14, 2006, 04:25 PM
I just used the shuffle function. I'm not making it more difficult than it needs to be. You guys should play munchkin and think of it from a programming view. Separate classes for each card seems like the best option.

subl1me
Jul 14, 2006, 06:53 PM
you clearly don't have the correct grasp of Object Oriented technologies and design if you're still thinking that writing a separate class for each card is the best way to tackle your project..

........but you live and you learn.

SilentPanda
Jul 14, 2006, 10:51 PM
You guys should play munchkin and think of it from a programming view. Separate classes for each card seems like the best option.

I guess I'll say it again.

I *have* played Munchkin (the box with the expansions is within arms reach of me right now) and I do program. Making some generic classes and working your way down would in fact be easier.

Most likely (and I'm not trying to be insulting at all) you don't have enough programming experience to know that the path you are taking is by far the longer one. That being said, even if you don't get the project done at all you will learn just by working on it which is always good! So I do wish you the best of luck regardless of how you choose to go about it.

And as subl1me said... you live and learn. :)

ChrisBrightwell
Jul 14, 2006, 11:46 PM
Separate classes for each card seems like the best option.Either that or you're still not grasping the principles of inheretance and OOP.

MarkCollette
Jul 20, 2006, 04:21 PM
I do have to write a shuffle() function for the linked list. Any suggestions on the best way to do that? The reason I'm asking the stuff on linked lists is I was never too good at the data structures stuff. Arrays I'm ok with. Any ideas would be great. Thanks

Benchmarks show that linked lists are only better than vectors when dealing with many hundreds of thousands, or millions, of objects. And even then, you typically have to have a doubly linked list.

- Heap allocation can be expensive. A vector makes less and less heap allocations as it grows, whereas a linked list makes a constant number of allocations as it grows.

- Cache locality #1. A Java Object has at least 16 bytes of overhead. A typical linked list node, with one "next" pointer will take up 20 bytes (16 byte overhead + 4 byte next pointer), wasting 80% of memory. This will spread the real data over more pages, and reduce the CPU cache effectiveness.

- Cache locality #2. A vector will place all references adjacent to each other, meaning they're on the same page. A naive linked list node class will have each node allocated from the heap as the list is grown, which might result in each node residing on different pages. Of course the refered to data object can still be anywhere.

- Iteration. It's much faster to increment an index and dereference the next slot in an array than to follow a "next" pointer.


On the other hand, a linked list, for sufficiently large data sets, can be faster at head insertion, or inserting into the middle. But, if you're always inserting to the head, then you can simply use a vector backwards. And inserting to the middle still requires traversing to the middle for a linked list.

MarkCollette
Jul 20, 2006, 04:29 PM
Oh yeah, and typically people decide to do:

A. Have a datafile, and one Card class, with instances per datafile entry
B. Have a bazillion Card classes

based on whether or not you have to support completely new and unknown Cards entering the system at runtime. Which is quite unlikely. And even then, you can still do:

public interface Card {
...
}

// Make KnownCard instances for each definition in datafile
public class KnownCard implements Card {
...
}

Then your predefined Card objects don't take a million classes, and you can still allow dynamically made cards to enter the system via a class loader.

jeremy.king
Jul 20, 2006, 10:00 PM
Benchmarks show that linked lists are only better than vectors when dealing with many hundreds of thousands, or millions, of objects.

...

On the other hand, a linked list, for sufficiently large data sets, can be faster at head insertion, or inserting into the middle. But, if you're always inserting to the head, then you can simply use a vector backwards. And inserting to the middle still requires traversing to the middle for a linked list.

Vectors are synchronized. So unless he is running multiple threads and need to protect the collection, it should not be used. Arrays only make sense if the size is known beforehand. ArrayList would make the most sense to me for this purpose - functionally equivalent to Vector but NOT synchronized.

MarkCollette
Jul 21, 2006, 10:34 AM
Vectors are synchronized. So unless he is running multiple threads and need to protect the collection, it should not be used. Arrays only make sense if the size is known beforehand. ArrayList would make the most sense to me for this purpose - functionally equivalent to Vector but NOT synchronized.

True. But I was using the words like "vector" and "linked list" instead of "Vector" and "LinkedList" because I was talking about generic concepts, not specific classes.

Compile 'em all
Jul 21, 2006, 12:54 PM
:rolleyes: I would like to note that Vector has long been deprecated
and you should not use it unless you plan to run your program on
legacy VMs. Instead you should use java.util.Collections.synchronizedList.

ChrisBrightwell
Jul 21, 2006, 12:59 PM
I would like to note that Vector has long been deprecated.State your source.

Sun's documentation says nothing about java.util.Vector being deprecated:
http://java.sun.com/j2se/1.5.0/docs/api/java/util/Vector.html

Nor does the deprecated list mention java.util.Vector:
http://java.sun.com/j2se/1.5.0/docs/api/deprecated-list.html

MarkCollette
Jul 22, 2006, 05:51 AM
Again, I was talking about a vector concept, not the java.util.Vector class.

But, a couple points of rebuttal are in order, so show that Vector is not defunct :)

- All programs I write a multi-threaded. True, one should use specific synchronization chokepoints, and not synchronise every little datastructure... But a lot of times, all that chokepoint does is add or remove items to/from a Vector (producer/consumer problems), so Vector still has some utility.

- A Vector will have less overhead than a synchronized List wrapping an unsynchronised List.

- Using a Vector gives the signature type that this is synchronised, whereas giving a List that happens to be synchronised does not have the same typing information. I don't mean some compiler thing, I mean that programmers can see at a glance that it's synchronised.

- Building on your point about old JVMs. Vector versus List is both a performance tradeoff and a compatibility tradeoff. Vector works everywhere and is a bit slower, and List works most places and is a bit faster. I will always take slower if it means that code can reach more people. Who knows what esoteric platform, with an old JVM, could benefit from running your app? I try to code to the lowest common denominator possible, because there's more profit in being able to sell to more people.

Compile 'em all
Jul 23, 2006, 05:32 AM
State your source.

Sun's documentation says nothing about java.util.Vector being deprecated:
http://java.sun.com/j2se/1.5.0/docs/api/java/util/Vector.html

Nor does the deprecated list mention java.util.Vector:
http://java.sun.com/j2se/1.5.0/docs/api/deprecated-list.html

You are right. Vector was moved and it now implements List. This was not
the case in JDK 1.1. Quoted from the Vector docs:
As of the Java 2 platform v1.2, this class has been retrofitted to
implement List, so that it becomes a part of Java's collection framework.
I still stand by my point though. If you need thread safety don't use Vector,
instead you should do:

ArrayList alist = new ArrayList();
List MyList = new java.util.Collections.synchronizedList(alist);

You can find more info here (http://mindprod.com/jgloss/vector.html) and here (http://www.velocityreviews.com/forums/t132806-arraylist-vs-vector.html).


I will always take slower if it means that code can reach more people. Who
knows what esoteric platform, with an old JVM, could benefit from running
your app? I try to code to the lowest common denominator possible,
because there's more profit in being able to sell to more people.

Totally agree, but only when doing client-side programming :D

dunc85
Jul 23, 2006, 04:52 PM
Interesting. When I completed my undergraduate Degree, in the first year we had to do similar stuff as this. However, we had to write our own stuff from scratch - i.e. we had to write our own implementation of a LinkedList, or the Shuffle method, rather than using those supplied by the Java API.

At the time, we saw it as a slightly pointless exercise of reinventing the wheel, but reading this post makes me realise it was totally worthwhile.

bousozoku
Jul 23, 2006, 07:38 PM
Interesting. When I completed my undergraduate Degree, in the first year we had to do similar stuff as this. However, we had to write our own stuff from scratch - i.e. we had to write our own implementation of a LinkedList, or the Shuffle method, rather than using those supplied by the Java API.

At the time, we saw it as a slightly pointless exercise of reinventing the wheel, but reading this post makes me realise it was totally worthwhile.

The thing is that you should be able to implement such a structure with any language, even if you have to modify it because the language doesn't implement some functionality.

Once you understand the why and how of things, you can use the supplied constructs with confidence, and in new and interesting ways.