This week's giveaway is in the Android forum.
We're giving away four copies of Android Security Essentials Live Lessons and have Godfrey Nolan on-line!
See this thread for details.
The moose likes Beginning Java and the fly likes Linked List Insertion and Deletion help Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Android Security Essentials Live Lessons this week in the Android forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Linked List Insertion and Deletion help" Watch "Linked List Insertion and Deletion help" New topic
Author

Linked List Insertion and Deletion help

Alex Ba
Ranch Hand

Joined: Oct 14, 2009
Posts: 35


That's what I have currently. Because it needs to be a doubly linked list, do I need to add in a previous pointer to the .next node? Something like:



Because in the insertion, the previous pointer is always null, which makes sense because it's adding to the integer to the first part of the list. I'm confused because then wouldn't the next value have a previous pointer of null?


Also, I was provided a delete method which isn't working. So I'm writing my own. What I have:



But when I try to use the method that I wrote, I get a nullpointer exception. Are there any obvious problems with my delete method?
Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4167
    
  21

Alex Ba wrote:
That's what I have currently. Because it needs to be a doubly linked list, do I need to add in a previous pointer to the .next node? Something like:



Because in the insertion, the previous pointer is always null, which makes sense because it's adding to the integer to the first part of the list. I'm confused because then wouldn't the next value have a previous pointer of null?


What happens when you try?


Also, I was provided a delete method which isn't working. So I'm writing my own. What I have:



But when I try to use the method that I wrote, I get a nullpointer exception. Are there any obvious problems with my delete method?

Show us the null pointer exception - specifically, at what line does it occur? Ask yourself - what value on that line of code could be null? Then ask 'Why would it be null?' Then make sure that it isn't null when you need to use it.

My guess is the line that gives you the problem is

because you try to access the next field in previous, but you never assign anything to previous. So you should make sure previous is assigned somethng.

Also,

is wrong. You probably don't want to assign the current.previous to current.next. Think about what that actually does. You probably want to make the previous node's next field point to the current nodes' next, then make sure the next node's previous field points to the current node's previous one.


Steve
Alex Ba
Ranch Hand

Joined: Oct 14, 2009
Posts: 35
The exact error is:

Exception in thread "main" java.lang.NullPointerException
at lab3.Intcoll3.delete(Intcoll3.java:33)

and it was the



I switched it to

but I'm still getting the error.


I think I'm getting the error because my previous pointers are all wrong. I can't figure out why though. The doesn't error, but Im pretty sure that's wrong.
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18538
    
  40

Alex Ba wrote:
I think I'm getting the error because my previous pointers are all wrong. I can't figure out why though.


You never set any of your previous pointers. When you inserted them, you set them all to null.

Henry


Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4167
    
  21

Yeah, you have to stop thinking in terms of words (previous, next, current, etc...), it looks like they are confusing you (they are probably too abstract). Stop writing code. Sit down and draw boxes and arrows and show yourself what you want to do.

For example, let's say you had a linked list with 3 values in it: "First" "Second" and "Third". The list might look like this:


First.Next points to Second.
Second.Previous points to First, and Second.Next points to Third.
Third.Previous points to Second.

So let's say we want to remove Second from the list. First thing to do might be to move Third.Previous from pointing to Second, and make it point to First:


First.Next points to Second.
Second.Previous points to First, and Second.Next points to Third.
Third.Previous points to First.

Then you would need to make First.Next point to Third, rather than Second:

First.Next points to Third.
Second.Previous points to First and Second.Next points to Third.
This.Previous points to First.

Now nothing points to second so you can nullify its pointers and get rid of it.


Once you draw diagrams for what should happen in the three basic scenarios (when the node to delete is at the head, in the middle or at the tail) you should then go back and make code that interprets those diagrams.


/EDIT/
I reversed the positions of Next and Previous in the Diagrams because their positions were bothering me. They look much cleaner this way.
Alex Ba
Ranch Hand

Joined: Oct 14, 2009
Posts: 35
I got all that, but I don't understand the coding part. I went through multiple weeks of explaining the concepts behind linked lists, and roughly 30 seconds of code
Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4167
    
  21

Alex Ba wrote:I got all that, but I don't understand the coding part. I went through multiple weeks of explaining the concepts behind linked lists, and roughly 30 seconds of code


Fine, you went through the exercises. Did you actually draw the cartoons?

1) You will have to fix your insert statement, as Henry pointed out and as you had asked about in the first post.

2) Once you do that, do the cartoons for the delete method. For each cartoon write ONE line of pseudo-code which performs the action.

3) Translate the pseudo-code into real code by giving it the support it needs (variable declarations, loops to find the proper node, etc...)
Alex Ba
Ranch Hand

Joined: Oct 14, 2009
Posts: 35
So is the insert method even correct for the next pointer?
Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4167
    
  21

Alex Ba wrote:So is the insert method even correct for the next pointer?


Yeah, you just missed the previous pointer. You already showed us how to fix that as well, so it just a matter of doing it. That prevents one possible NPE you would get when solving the delete() problem.

The reason I want to point you back to the cartoons and psuedocode is because you were getting farther from what you needed to do, and it seemed you weren't really following the changes you were making. Rather than un-tangle the logic after the fact, in these cases it is usually better to start over.
Alex Ba
Ranch Hand

Joined: Oct 14, 2009
Posts: 35
So I made a variable IntNode named current, and then at the end of the insert statement I did:

current = newnode.next;
current.previous = newnode;




Progress?
Alex Ba
Ranch Hand

Joined: Oct 14, 2009
Posts: 35
??
Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4167
    
  21

Not bad - show us the complete new method. Does it seem to work (ie, when you add things to the List can you traverse it in backwards order)?

What is the benefit of doing it this way (with the new declaration) versus using the method you showed us in the first post? What problem does it solve?

There is a problem with the code. What happens when you are adding the first element in the List and there is no newnode.next?
Alex Ba
Ranch Hand

Joined: Oct 14, 2009
Posts: 35


I'm not entirely sure if it works, as I haven't really tested it yet. And by doing it that way, the second item in the list is given a previous pointer, and already has a next pointer. And the problem, I should make it:


or something of that nature?
Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4167
    
  21

Alex Ba wrote:

I'm not entirely sure if it works, as I haven't really tested it yet.


Well, you should do that. But it looks okay to me.


And by doing it that way, the second item in the list is given a previous pointer, and already has a next pointer.


I was just wondering why you used the current reference, when you already had shown us:

which does the same thing. It isn't important, they both do the same, I was wondering if you had a reason for choosing one over the other is all.


And the problem, I should make it:


or something of that nature?

No need. The problem only occurs when the head == null. You put the code inside a block that only gets executed when head != null, so it is a non-issue. The code as you posted is fine (the reason I saw a possible problem was because, not seeing your code, I took "at the end of the insert" to mean at the end of the method - after the else statement, which would have been a mistake. But you didn't make that mistake).
Alex Ba
Ranch Hand

Joined: Oct 14, 2009
Posts: 35
So that insert method correctly sets up the next and previous pointers?
Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4167
    
  21

It looks good to me. But like I said, you should test it to be sure.

Tests can be simple. Put a few objects in, then iterate across them from head to tail, and tail to head and make sure they come out in the order you expect.
Alex Ba
Ranch Hand

Joined: Oct 14, 2009
Posts: 35
Previous isn't working at all. I can get it to print head to tail, but not tail to head.



That's my print method. If I entered 8 and then 7, it prints:

7
8

and, if I'm correct it should be

7
8
8
7
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18538
    
  40

Take a look at your first loop. It ends with current being null -- not current being at the tail node. You second loop assumes that the current point is at the last node, which is not true.

Henry
Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4167
    
  21

Looks to me like at the end of your first print loop you are 'After' the last element. It goes from 7 to 8, then from 8 to null, at which point it ends the while loop. Then you try to do it in reverse, but you check current.previous. Current at that point is null, so that code should give you a null pointer exception.

Do you have a reference to the tail of your list? If so, then use that. If not, it might be a nice thing to add. Or you will have to separately move to the end of the list.
Alex Ba
Ranch Hand

Joined: Oct 14, 2009
Posts: 35
So to code a tail pointer, I've attempted:


And then for the print method, I switched it to:



If you enter 9 then 8, it prints 8 then 9. I'm so damn confused.
Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4167
    
  21

Can you repost all your code again? I have lost track of what code is where. If I follow along with just the parts posted in this thread it would appear to me like when you insert, you never set newnode.next to anything...
Alex Ba
Ranch Hand

Joined: Oct 14, 2009
Posts: 35
Current = newnode.next doesn't set the next pointer of newnode to current?

This is the tentative insert method:

Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4167
    
  21

Alex Ba wrote:Current = newnode.next doesn't set the next pointer of newnode to current?


It doesn't set the next pointer of newnode to current, it sets current to the same value as newnode's next pointer. How does newnode's next pointer get any value? I presume it does somehow, because you were able to iterate forward and don't get null pointer exceptions when you do:

If you didn't assign something to newnode.next, then current = newnode.next would be null, and current.previous would throw an exception. Do you assign to the next pointer in the IntNode constructor?


This is the tentative insert method:

Alex Ba
Ranch Hand

Joined: Oct 14, 2009
Posts: 35
Insert Method



IntNode class:
Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4167
    
  21

Well, not exactly sure what you are doing, but when I use the code snippets you provide, put them together for a compilable class, I get a null pointer exception on the second insert for the reasons I described earlier. Here is the code I have:



Results:


So you are doing something different than what you are showing here. Not exactly sure. But it could be that your not compiling successfully, so when you run you are running the wrong code. Or you are running different code that you are compiling. Until you sort that out I can't really help you any further because I have no clue what code you are working with or what the behavior should be.
Alex Ba
Ranch Hand

Joined: Oct 14, 2009
Posts: 35
So here's the story. My compiler decided it wasn't going to run the edited version of the java file. It was going to run the file that I opened initially. For that I am kicking myself, as I've been editing and running it for the past 2 days, only to find the same output every damn time.

Anyway. I switched compilers and I got the nullpointerexception. Now I'm absolutely lost.
Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4167
    
  21

Alex Ba wrote:So here's the story. My compiler decided it wasn't going to run the edited version of the java file. It was going to run the file that I opened initially. For that I am kicking myself, as I've been editing and running it for the past 2 days, only to find the same output every damn time.

Anyway. I switched compilers and I got the nullpointerexception. Now I'm absolutely lost.


Bah... I hate when that happens. When you go changing things and nothing happens on your output, that is a good sign something is wrong and to re-assess you environment.

Anyway, you are not far away from a working insert code. I will let you play with it, but I had to add 1 line and change 1 other line from my posted code to get the insert method to work. I had to change 1 line for the print function to work properly, and that was it. So a total of 3 changes makes it functional both for insert and tests. I think all three lines have been brought up as problems in my last few posts.
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18538
    
  40

Alex Ba wrote:Anyway. I switched compilers and I got the nullpointerexception. Now I'm absolutely lost.


It may be a good idea to not use the compiler for a bit -- and use a sheet of paper and a pencil. Basically, you are trying to teach your program to connect the dots (or more precisely, connect the nodes) to form a linked list. It would be a good idea for you to be able to do it on paper first, using a drawing.

Once you understand what you are doing on paper -- meaning you can envision it -- then it should be easy to translate those instructions for your program to do it with references.

Henry
Alex Ba
Ranch Hand

Joined: Oct 14, 2009
Posts: 35
The concept part isn't the problem. I know that in a doubly linked list each node has a value, a pointer to the next node, and a pointer to the previous node. I know that when you add a new node, it is added to the head of the list. I know that the first node in the list has a previous value of null because it's the first, and I know that the last node in the list has a next value of null.

To the best of my knowledge, all of the above statements are correct. If that's true, the concepts aren't the problem. The code is the problem. In the class that this was assigned in, we spent 2 weeks drawing the pictures and going over concepts behind a linked list. The day they went over the code to program said list, I was out with the flu. Poor timing I guess but regardless, now I'm here.
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18538
    
  40

Alex Ba wrote:The concept part isn't the problem. I know that in a doubly linked list each node has a value, a pointer to the next node, and a pointer to the previous node. I know that when you add a new node, it is added to the head of the list. I know that the first node in the list has a previous value of null because it's the first, and I know that the last node in the list has a next value of null.


This is *not* enough. You need to be able to envision it being added as it is being added. You need to see how the different references change and how they change. And just connecting the dots is *not* enough. You need to be able to describe it to yourself, with references that you have -- meaning if you have nothing pointing to something, you can't connect to it, until you understand how to get to that something first.

This is what I mean by "envisioning". It is not about the pretty picture. Unless you can do it on paper, you won't be able to tell the computer to do it on the heap.

Henry
Alex Ba
Ranch Hand

Joined: Oct 14, 2009
Posts: 35


Seems as though it works. I don't really understand the newnode.next = head part, but it seems to work.

*edit* I LIED. You're setting your new node's next pointer to the OLD head, since it hadn't been changed yet. And after you're setting the next to the old head, you switch the head to the new newnode. In regards to Steve's post, I only added one line, but I didn't edit any others. I feel as though I've missed something.
Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4167
    
  21

Alex Ba wrote:
*edit* I LIED. You're setting your new node's next pointer to the OLD head, since it hadn't been changed yet. And after you're setting the next to the old head, you switch the head to the new newnode. In regards to Steve's post, I only added one line, but I didn't edit any others. I feel as though I've missed something.


Yeah, you got it. You also did make the one line edit I had mentioned. You changed:

to


So you added the newnode.next assignment where you needed it, and you changed the tail assignment. Now you are ready to test the print method. Test your connections both forward and backward to be sure.
Alex Ba
Ranch Hand

Joined: Oct 14, 2009
Posts: 35
I can't find the problem with my print statement.




The insert method:





Some of the syntax might be wrong, my compiler doesn't allow copying. Is there a mistake I'm not seeing?
Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4167
    
  21

Alex Ba wrote:I can't find the problem with my print statement.





What happens when:
1) There is only one element in the list (tail == head != null)
2) When you get to the first element in the list (i.e. the head, the last element iterated to)?
3) When the list is empty?
Alex Ba
Ranch Hand

Joined: Oct 14, 2009
Posts: 35


When there's only one item in the list and it's supposed to be deleted, it's not. And when there's 2 items in the list that are both supposed to be deleted, the first isn't and the second throws a nullpointerexception for the line. I don't understand why though.
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18538
    
  40

Alex Ba wrote:
And when there's 2 items in the list that are both supposed to be deleted, the first isn't and the second throws a nullpointerexception for the line. I don't understand why though.


Well, you declared a local variable, name previous, which you set to null, in the beginning of the method. This line, tries to dereference that null variable to access the "next" variable -- which will get you a NPE.

Henry
Alex Ba
Ranch Hand

Joined: Oct 14, 2009
Posts: 35
But I don't understand, you're setting current to head, and that means current doesn't have a previous value, so previous would be null, no?
Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4167
    
  21

Alex Ba wrote:But I don't understand, you're setting current to head, and that means current doesn't have a previous value, so previous would be null, no?


So what are you trying to accomplish. Again, you will get a LOT better mental picture if you draw with pen an paper then turn it into code.

I know I know, you have done it before. But I think you will benefit from doing it again. Don't be afraid to start again, with fresh code (for this method). Think more about what you want to accomplish and what you actually NEED to do. For example, you have this variable named previous. You never set it, yet you try to use it. You apparently don't know why you have that variable or know how it is used through the code. So why is it there?
 
Consider Paul's rocket mass heater.
 
subject: Linked List Insertion and Deletion help
 
Similar Threads
Linked List Sorting Problem
Linked List Sorting Problems
Reverse a Singly linked list in java
Linked List Help
Doubly Linked Lists