Linked List "remove" method trouble in java.

[VigilanteCS]

Hi, I've started to learn Linked Lists in Java and I'm having trouble with the remove method. All I want it to do is remove an element from the list. The add method just adds a node to the end, and the insert method add the element in numerical order to the list.

Thanks for any help!

 

[lansalot]

Do you usually ask people to do your homework? Seems a bit off to me...

 

[VigilanteCS]

Did I say it was homework? I'm just asking for help getting this working because I can't figure this out.

 

[Kilrsat]

Why are you initializing the list if its empty? delete() is creating a node, seems strange to me.

As for why it doesn't work:

node ppt;
node ptr;
while(item > ptr.getElement())
{
ppt = ptr;
ptr = ptr.getNext();
}

You'll notice that neither ppt nor ptr are ever assigned values. This should be throwing a null pointer exception if you try to run it (may not even compile, my memory is a little sketchy on if the compiler will throw an error about ppt and ptr never being assigned values) or the code you posted isn't the code you're using.

 

[VigilanteCS]

I'm not using java's built in linked list features, I'm trying to make everything on my own. And I know that I'm not actually assigning the nodes any value, but I'm just confused on how to go about doing all of this.

I know that I need to reassign the pointers, and then delete the element. I know i have to check to see if the element is greater than the tail and less than the head, or if it is equal to the head. I'm just not sure how to implement all of this.

BTW...This class is using methods from the other class "node" i made. It has
setNext() , sets the next node
getElement(), gets the element in a node
getNext() . sets the next node

Also, why do I need to assign a value when I'm trying to remove it, Kilsrat?

 

[kamper]

First, I'd like to help but some of that code just makes no sense and I'd rather see pointed questions than just plain telling you how to do it.

But I'd like to make some comments:
-start class names with upper case
-realize that assigning a "new node()" to "head" and then assigning something else to it is a complete waste
-name boolean returning functions as questions if they don't actually do anything. By the name I would assume that emptyList() actually removes everything from your list. The way it's implemented right now, it should be called isListEmpty() or isEmptyList().

 

[VigilanteCS]

Originally posted by: kamper
First, I'd like to help but some of that code just makes no sense and I'd rather see pointed questions than just plain telling you how to do it.

But I'd like to make some comments:
-start class names with upper case
-realize that assigning a "new node()" to "head" and then assigning something else to it is a complete waste
-name boolean returning functions as questions if they don't actually do anything. By the name I would assume that emptyList() actually removes everything from your list. The way it's implemented right now, it should be called isListEmpty() or isEmptyList().

Well, my teacher likes us to keep our class names with lower case letters (don't know why). emptyList() just checks to see if the list is empty. All of it works except remove. I just need help on that.

 

[notfred]

when you delete a node:

node.previous.nextNode = node.nextNode; <--- that's really the gist of it.

 

[VigilanteCS]

Problem is that I don't have a previousNode() method to call, and my teacher wants us to use all of the if statements that I have in it now.

 

[notfred]

Originally posted by: VigilanteCS
Problem is that I don't have a previousNode() method to call, and my teacher wants us to use all of the if statements that I have in it now.

So you admit it's homework now.

Write a "previous" method for your class. Then you can call it.

 

[Kilrsat]

Originally posted by: notfred

Originally posted by: VigilanteCS
Problem is that I don't have a previousNode() method to call, and my teacher wants us to use all of the if statements that I have in it now.

So you admit it's homework now.

Write a "previous" method for your class. Then you can call it.

He's trying to implement delete in a singly-linked not a doubly-linked list. At least that's what it looks like. Delete in a single linked list is very inefficient since you need to make two passes through the list.

Basically you scan the list to find the element to delete, then you scan the list for the node that has node.getNext() = the node you found in the first scan. Then set the next node of the second node to the next node of the first node and you're done.

I still don't see why you're initializing a list if you try to delete an element though.

 

[notfred]

Just for fun, I spent 20 minutes writing my own java linked list. I haven't actually tested it, but it compiles and looks like it should work ok.

 

[VigilanteCS]

got my remove method working. Thanks for the help guys

 

[kamper]

Originally posted by: Kilrsat

Originally posted by: notfred

Originally posted by: VigilanteCS
Problem is that I don't have a previousNode() method to call, and my teacher wants us to use all of the if statements that I have in it now.

So you admit it's homework now.

Write a "previous" method for your class. Then you can call it.

He's trying to implement delete in a singly-linked not a doubly-linked list. At least that's what it looks like. Delete in a single linked list is very inefficient since you need to make two passes through the list.

Basically you scan the list to find the element to delete, then you scan the list for the node that has node.getNext() = the node you found in the first scan. Then set the next node of the second node to the next node of the first node and you're done.

I still don't see why you're initializing a list if you try to delete an element though.

Holy time to go back to datastructures or algorithms class! Traversing the list twice?
Just keep a trailing pointer one behind your scanning pointer.

 

[skace]

I just read this thread because linked lists rock, although I didn't know there was such a thing as a 'singly linked list'. I havn't gotten to use linked lists since college, since I don't ever do programming, but <3 them all the same.

 

[Zugzwang152]

Originally posted by: skace
I just read this thread because linked lists rock, although I didn't know there was such a thing as a 'singly linked list'. I havn't gotten to use linked lists since college, since I don't ever do programming, but <3 them all the same.

well they're retardedly useless except for illustrating concepts, as in a programming class. i went over Linked Lists in my intro and second-semester programming classes, both in Java.

 

[Crusty]

Originally posted by: Zugzwang152

Originally posted by: skace
I just read this thread because linked lists rock, although I didn't know there was such a thing as a 'singly linked list'. I havn't gotten to use linked lists since college, since I don't ever do programming, but <3 them all the same.

well they're retardedly useless except for illustrating concepts, as in a programming class. i went over Linked Lists in my intro and second-semester programming classes, both in Java.

I find LinkedLists quite usefull sometimes, especially when you are working with data that will only be traversed in order. When using Java and Iterators it hardly makes a difference what type of list storage you use, one of the great points of all the layers of abstraction in java.

List myList = new LinkedList();
Iterator myIterator = myList.getIterator();


Then just use myIterator to go through the list, this way you can change the type of myList without having to change code. LinkedList's are nice in the view of memory management

 

[kamper]

Originally posted by: MCrusty

Originally posted by: Zugzwang152

Originally posted by: skace
I just read this thread because linked lists rock, although I didn't know there was such a thing as a 'singly linked list'. I havn't gotten to use linked lists since college, since I don't ever do programming, but <3 them all the same.

well they're retardedly useless except for illustrating concepts, as in a programming class. i went over Linked Lists in my intro and second-semester programming classes, both in Java.

I find LinkedLists quite usefull sometimes, especially when you are working with data that will only be traversed in order. When using Java and Iterators it hardly makes a difference what type of list storage you use, one of the great points of all the layers of abstraction in java.

List myList = new LinkedList();
Iterator myIterator = myList.getIterator();


Then just use myIterator to go through the list, this way you can change the type of myList without having to change code. LinkedList's are nice in the view of memory management

I don't see the point in caring how data is stored in your List. LinkedLists use more memory than array based Lists like Vector or ArrayList (although it's probably a negligible difference) and are only faster in the very rare case that you know it always will be used in very specific ways. Given that performance is the only difference between a Linked and ArrayList and that LinkedList will only rarely be faster why bother.

If you're working in a language like plain c where arrays aren't so easy to use (not managed behind a List interface) then of course linked lists are important but I'd be tempted to just write my own array management library for reuse anyway, if I could.

 

[Bacardi151]

well working with linked list is much easier to implement certain algorithms. try writing something that uses a binary tree with an array.
it's very inefficient, algorithm-wise, because you'll have to resize the array at some point and put the values into the array again.