aspose file tools*
The moose likes Beginning Java and the fly likes Reversing a doubly linked list Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Reversing a doubly linked list" Watch "Reversing a doubly linked list" New topic
Author

Reversing a doubly linked list

Luke Stamper
Ranch Hand

Joined: Jun 19, 2011
Posts: 64
I've been asked to make some modifications to a linked list.

1) make it doubly linked.
2) Add a copy constructor
3) Add a clone method
4) Replace outputList with toString
5) Code an iterator method
6) Keep track of the tail and add a method outputBackwards to prove the list is doubly linked.

I pretty much have everything covered except for #6. I'm having trouble with this. Can anyone provide some assistance? Thanks in advance.

Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Luke Stamper wrote:6) Keep track of the tail and add a method outputBackwards to prove the list is doubly linked.

I pretty much have everything covered except for #6. I'm having trouble with this. Can anyone provide some assistance? Thanks in advance.


So what problems are you having? You have a head element and know how to iterate forward, right? If so, then you know how to create a tail element and iterate backward.
Luke Stamper
Ranch Hand

Joined: Jun 19, 2011
Posts: 64
You would think that...but I am getting confused iterating backwards.
Luke Stamper
Ranch Hand

Joined: Jun 19, 2011
Posts: 64
Do I have to do everything the same with the tail as I did with the head? Every method?
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Luke Stamper wrote:Do I have to do everything the same with the tail as I did with the head? Every method?


Well, no, I wouldn't say that. Certainly just don't blindly copy and paste everywhere you see "head". The point is, you understand how the head is used, what it means, and you understand how to iterate from the front using head. Right? I mean, you wrote this code yourself, yes?

So, given that understanding, you need to ask yourself, what does a "tail" variable mean? How do I set it, and when do I update it? How can I use it to iterate backwards? All the while, using head as an example (but not as the source for a pure mechanical duplication).

You should at least be able to give it a try, and as a more specific question if you get stuck.
Luke Stamper
Ranch Hand

Joined: Jun 19, 2011
Posts: 64
So my outputBackwards and insertAfter methods aren't working.

And yes, this is my code. I wrote it with the help of my java tutor.


Luke Stamper
Ranch Hand

Joined: Jun 19, 2011
Posts: 64
Does anything about those two methods look correct?
Luke Stamper
Ranch Hand

Joined: Jun 19, 2011
Posts: 64
So it appears my outputBackwards method doesn't outputBackwards at all, it just outputs the list as is. Can anyone tell me why that is?

Also, i've gotten rid of the insertAfter method.
Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4181
    
  21

When I do these sorts of things it always helps me to visualize what I need to do. I usually do it with pencil and paper, so I can redraw lines where needed. For example, I might start with something like this:



That would be my starting point, so I would use that the re-work where all my variables should point as I proceed.

The next thing to do is get a clear understanding of the requirements. What exactly is outputBackwards supposed to do? Is it supposed to reverse the direction of the list in-place? Is it supposed to return a new list with the order reversed? Or is it simply supposed to print the list like the toString() method, but backwards? You have to be clear on that before you do anything else.

Finally, you have this line as the first line in yur outputBackwards method:


Looking at the picture above, can you see why that will always end the method before any other work is done?


Steve
Luke Stamper
Ranch Hand

Joined: Jun 19, 2011
Posts: 64
It will always be null.

This is all I know about what I have to do....keep track of the tail and add a method outputBackwards to prove the list is doubly linked.
Luke Stamper
Ranch Hand

Joined: Jun 19, 2011
Posts: 64
This still prints it in order. Ugh.

Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4181
    
  21

Did you do the pencil/paper redrawing?

I got this after following the instructions you wrote line for line:



@edit: Last image had TAIL pointing to wrong spot.
Luke Stamper
Ranch Hand

Joined: Jun 19, 2011
Posts: 64
I don't see why this method isn't working? I start at the tail, then display data until start of list moving to each link.

Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4181
    
  21

i modified your TwoWayNode class to add the displayLink() method since you didn't show it:



I used your last posted outputBackwards() method:

And I changed your demo main method to remove unneeded tests (for this particular scenario):




The key point in the output is between the "Reversing the list" line and the "List now contains:" line. Notice there is nothing there. Why would you get no output there if displayLink() method gets called and it prints the link value?
Luke Stamper
Ranch Hand

Joined: Jun 19, 2011
Posts: 64
I don't have the link value anywhere.

I am not instructing my program to print the correct thing.
Luke Stamper
Ranch Hand

Joined: Jun 19, 2011
Posts: 64
I have to pass the current data item into the print output to print the current item and then each additional item.
Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4181
    
  21

Luke Stamper wrote:I don't have the link value anywhere.

You do have the value (item), because you can print it both before and after the 'reversal'

I am not instructing my program to print the correct thing.

That is close. in the code I posted it does tell it to print the item. But no items show up in the output... hmmm... maybe the displayLink() method never gets called. Why would the displayLink() method never get called? Looking at your outputBackwards() method, you have this:


Why would current.displayLink() never get called? Not even once?
Luke Stamper
Ranch Hand

Joined: Jun 19, 2011
Posts: 64
I've been staring at this for way too long.

It's not the loop. The tail is not null so it should go through the loop and print.

There is something wrong with the displayLink method. Something with the passing of arguments?
Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4181
    
  21

Luke Stamper wrote:...The tail is not null...


Incorrect. When do you set the tail? Not in addToStart(), and addToStart() is the base for all your object inserts.
Luke Stamper
Ranch Hand

Joined: Jun 19, 2011
Posts: 64
So I need to add the tail to addToStart?
Luke Stamper
Ranch Hand

Joined: Jun 19, 2011
Posts: 64
I figured since I have TwoWayNode tail = current, that sets the current node to the tail, meaning the tail is not null.
Luke Stamper
Ranch Hand

Joined: Jun 19, 2011
Posts: 64
I chaned my addToStart method to include the tail.

Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4181
    
  21

Almost there. Use pencil and paper to see where things point after one, two, three positions get added to the list this way. The final code for this method will be simpler than what you have, as far as the tail is concerned. For example, ask yourself: When do you have to worry about the tail when all you are doing is adding to the start of the list?
Luke Stamper
Ranch Hand

Joined: Jun 19, 2011
Posts: 64
I think I have a better handle on my doublylinked list now...although I am experiencing a few errors still...

I am not sure if I should use the list or iterator before outputBackwards in linkedlist3demo class.

Am I on the right track with my outputBackwards method?

--------------------Configuration: <Default>--------------------
G:\Object Java\LinkedList3.java:217: error: ';' expected
return T position;
^
G:\Object Java\LinkedList3.java:217: error: not a statement
return T position;
^
G:\Object Java\LinkedList3.java:217: error: cannot find symbol
return T position;
^
symbol: variable T
location: class LinkedList3<T>
where T is a type-variable:
T extends Object declared in class LinkedList3
Note: Some input files use unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
3 errors

Process completed.

Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4181
    
  21

A few things:

1) the line you are having problems with is this:

Does that line look correct to you? For example, in the public boolean deleteHeadNode() method you return a boolean. Do you use this code?



2) The type of the return for the outputBackwards() method is T. T is the type of the item stored in a node. You are trying to return the position object, which is of type TwoWayNode, not of type T.

3) Does it make sense to return anything from the outputBackwards() method? If so, what should you return? The position as you are trying to do - which will be null by nature of the while() loop ending?
Luke Stamper
Ranch Hand

Joined: Jun 19, 2011
Posts: 64
How about this?




Do I also have to add something to actually print the nodes in the displayItem() method?

Such as...

Luke Stamper
Ranch Hand

Joined: Jun 19, 2011
Posts: 64
Well, I don't think one can fully understand doublylinked lists until they force themselves to understand them until they 'actually' understand them.

In any case, for anyone following this entirely too long of a thread, here is my working code



 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Reversing a doubly linked list