Computer Science Canada remove an item from a linked list? |
| Author: | Bo0sT [ Sun Apr 12, 2009 9:49 am ] |
| Post subject: | remove an item from a linked list? |
I'm creating a linked list for my program, and i'v got everything working, but I can't figure out how to remove an item. I'v tried a few diffrent things and looked around the net, but still no luck. Can someone please explain how I would do this, I don't need any code, just how to go about it. I have 3 classes involved in my linked list. -Node, which contains the information that I want this list to store and a pointer to the next node -LinkedList, which manages the Node objects and links them together, it has a pointer to the first and last nodes and an int size -Debug, this is the main class with the entry point that I am using to test it. please help |
|
| Author: | wtd [ Sun Apr 12, 2009 9:59 am ] |
| Post subject: | RE:remove an item from a linked list? |
Let's say you have three nodes. We'll call them A, B and C. You want to remove B. What needs to change about all three in order to remove B from this linked list? |
|
| Author: | Bo0sT [ Sun Apr 12, 2009 12:36 pm ] | ||
| Post subject: | Re: remove an item from a linked list? | ||
I would need to make A point to C, but how would I code that? I'm thinking I would have a loop that loops through the list starting at the first node. I would do this by creating a temp node and initilising it as the first node, then make it assign itself to the next node each loop, like this:
and then I would have it check each loop if the counter is equal to the index of the node that I want to delete, and if it is, assign the next one to two over, skipping it. All that works, but the modified list is temp, I really don't want to have to return the list back to my program, i'd like the remove method to just delete something from the current list. So basically the problem is, how do I get first to point to the second element of temp, which would by this point be the last node if its list. |
|||
| Author: | matt271 [ Sun Apr 12, 2009 2:12 pm ] |
| Post subject: | Re: remove an item from a linked list? |
couldnt u just say something like A.link = A.link.link; ? now A points to what B used to point to, aka C. so now B is gone. |
|
| Author: | Bo0sT [ Mon Apr 13, 2009 9:00 pm ] |
| Post subject: | Re: remove an item from a linked list? |
matt271 @ Sun Apr 12, 2009 2:12 pm wrote: couldnt u just say something like A.link = A.link.link; ? now A points to what B used to point to, aka C. so now B is gone.
But what if you want to remove J, or something else further in the list? For example I can't have A.link.link.link.link and so on. |
|
| Author: | Tony [ Mon Apr 13, 2009 9:10 pm ] |
| Post subject: | RE:remove an item from a linked list? |
All you need is a Node that comes before J (lets call it I). If it's a doubly-linked list, you could simply do J.previous; Otherwise you'd have to start from the Head and look for I. |
|
| Author: | matt271 [ Mon Apr 13, 2009 9:38 pm ] |
| Post subject: | Re: remove an item from a linked list? |
a was a var. i didnt mean the first element. just the element before the one u want to remove. |
|
| Author: | riveryu [ Sun May 03, 2009 10:20 pm ] |
| Post subject: | Re: remove an item from a linked list? |
Your Node class should be static to LinkedList class. You only need a temp Node for iterating through the list I think. For your delete() method, consider linked list A ->B->C->D where A is the head of the list. Say you want to delete(C): 1. Use while loop, search from head up to the point where the current Node's next-> is C. Something like while(temp.next != C){ 2. The current node should be B at this point. Call it cur for short. 3. Set cur.next to C's next which is D or cur.next.next, now B points to D. Your done. Hope this helps. |
|