permaculture playing cards
The moose likes Beginning Java and the fly likes linked list help! Big Moose Saloon
Register / Login

JavaRanch » Java Forums » Java » Beginning Java
Bookmark "linked list help!" Watch "linked list help!" New topic

linked list help!

Steve Ruzila

Joined: Feb 28, 2009
Posts: 3
I haven't touched Java in 2 years and I'm now required to do a data structures class...I wasn't very good with Java back then and now I'm very rusty so have some patience with me please. Sorry this is long but I wanted to make sure everyone knew what I am trying to do.

I have the command line based "interface" completed the main method is here.

Here's what I need to do:

Your program will be a simple address book. It will store names (used as keys) and addresses that are associated with the names. The program will present the user a menu with a choice of operations: add a name (and address), look up a name (displaying the associated address), update the address for a name, delete an entry, display all entries, and quit.
If the user chooses add the program prompts for a name. If the name already exists in the address book a message is displayed to that effect and no change is made. Otherwise the program asks for an associated address and the new entry is made. If the user chooses look up he or she is asked for a name. The program will look up the entry for that name and display the associated address. If the user chooses update he or she is asked for a name. The name is looked up and the address displayed. The user is then prompted for a new address which is accepted and stored in place of the old address. For delete the user is asked for a name and the entry for that name is removed from the address book. In any of these cases (other than insert) if the name given by the user is not found an appropriate message is displayed. If the user selects display all all of the names and addresses in the address book are displayed (the order is not important). The program continues displaying the menu and taking commands until the user chooses quit.
Names and addresses will occupy a single line (so all user input is taken using If the user enters a selection which is not in the menu the menu will be displayed again and the user is prompted again for a command. The names and addresses can be any strings -- your program need not check that they make any sense.

You will write (among other classes) a class Table which will store entries which are (key/value) pairs of Strings. You will need to write a Node class which will have (as private fields) a key String (used to identify the entry) and a value String (used to store some data associated with the key) and a next pointer used for linking. Table will have public methods:
+ • public boolean insert(String key, String value) Inserts a new entry to the table. If an entry already exists with the given key value make no insertion but return false.+
+ • public String lookUp(String key) Looks up the entry with the given key and returns the associated value. If no entry is found null is returned.+
+ • public boolean delete(String key) Deletes the entry with the given key. If no entry is found returns false.+
+ • public boolean update(String key, String newValue) Replaces the old value associated with with the given key with the newValue string.+
+ • public boolean markToStart() Sets the mark (see below) to the first item in the table. Returns false if the table is empty.+
+ • public boolean advanceMark() Moves the mark to the next item in the table. If there is no next item (e.g. at the end of the list) returns false.+
+ • public String keyAtMark() Returns the key stored in the item at the current mark.+
+ • public String valueAtMark() Returns the value stored in the item at the current mark.+
Table will keep a linked list of Nodes. Each entry (from the methods listed above) will be stored in an instance of Node stored in this linked list. The list is maintained in no particular order, but no two Nodes in the list can have the same key field.
Table will also have a (private) field, mark, which is a reference to Node. This field is modified or used by the markToStart, advanceMark, keyAtMark, and valueAtMark methods. Together these methods can be used to traverse the list and read the contents of all the entries in the table.
You may add any more methods you need to the Table class but they must be private. The only public methods are those listed above. All instance fields in all classes in your program will be private.
You will notice that this Table class is not specifically an address book but just stores and operates on pairs of strings. You will implement your address book as an instance of Table and will implement the address book operations, listed at the beginning of this page, using public methods of Table.

So here's what my problem is....
What goes into the Node class?
What else goes into the Table class?
Is there some other class I need?
I have an AddressBook class that has the command line based interface and I'm using a switch statement for that.
Each class is in a separate file.

I really DO want to figure this out on my own but seem to have hit wall. Lack of sleep maybe.....I just can't seem to get through this.
Thank is advance,

Campbell Ritchie

Joined: Oct 13, 2005
Posts: 45277
Welcome to JavaRanch

If you are having difficulty because you are tired, do something different. Relax, drink some beer, and get some sleep. It is surprising how much easier things will look when you are actually awake.

We don't give out answers to that sort of question, but are willing to help. You have given a detailed submission which is obviously a course assignment. I was rather surprised to see a linked list suggested as the best data structure for an address book. (See this Java Tutorials section.) It is however obviously an assignment about how to design a linked list.

You will have to decide what goes in a Node; it actually tells you in what you have copied what to put in it.

You are doing it the wrong way round. Don't start with the main method, but with the Node class. Put your name and address in a Node, and set up a class with a main method which allows you to enter names and addresses and retrieve them. Then put the Nodes into a data Structure, which will be a linked list. If you can't implement a "MyLinkedList<Node>" class try a MyLinkedList which has int values first, then enhance that class to support Nodes.

See how far you get like that, and good luck with the assignment
Steve Ruzila

Joined: Feb 28, 2009
Posts: 3
Yep, it is an assignment. I've been around and around on this and just can't seem to wrap my mind around it. I have a complete interface (command line based), an AddressBook class. I have (what I believe) is a complete Node class. The part that is hanging me up are all the methods the assignment lists as requirements. I've been reading through multiple books, multiple web sites but I'm just not sure how to do some of the methods nor how to get all three to play nice together.

I have them as two separate files...should they be one file? Here is the code for the Table and Node classes that I've spent all day cobbling together from a billion examples...

[edit]Add code tags. CR[/edit]
Steve Ruzila

Joined: Feb 28, 2009
Posts: 3
Wouldn't this link be more what I need?

But my problem...if you want to call it how do I "map" the methods my assignment asks for to the methods that are in the LinkedList class?


PS- please don't do my home work for me....just point me in the right direction and give good explanations and examples.
Henry Wong

Joined: Sep 28, 2004
Posts: 20366

Steve Ruzila wrote:Wouldn't this link be more what I need?

If I read your original question correctly, you mentioned that you were taking a "data structures" class. This class is designed to teach you how to design and implement data structures -- including the linked list. I think that it is safe to assume that you are *not* allowed to use the built-in linked list collection to implement your linked list data structure.


"cobbling together from examples" is not a good way to learn data structures. You should actually write them from stratch. Anyway, I would recommend that you reread the sections in your textbook about linked list -- you really need to understand the theory first. And there is *no* way to learn the theory from "cobbling".


Campbell Ritchie

Joined: Oct 13, 2005
Posts: 45277
I have only had a few seconds to look at your code (by the way, it is much easier to read if you use the CODE button) and it seems very weird that you have Node as an inner class inside Table. That is almost certainly a mistake.

Get the Node class working on its own, just adding and altering and deleting names and addresses, then put it together to make a Linked List. You don't want to map methods of java.util.LinkedList to your application; you want methods in your Node class which can be used by those methods in Table or whatever.
I agree. Here's the link:
subject: linked list help!
It's not a secret anymore!