Author |
Topic: Linked List Node Deletion (Read 2616 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Linked List Node Deletion
« on: Apr 12th, 2003, 1:57pm » |
 Quote  Modify
|
You are given a pointer to the middle node in a singly linked list. Write a program that takes this pointer as input and deletes that node in the linked list, while maintaining the linked list structure.
Sources: Anwis Das and Sanjay Jeyakumar
|
| « Last Edit: Apr 13th, 2003, 6:19pm by william wu » |
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Linked List Node Deletion
« Reply #1 on: Apr 13th, 2003, 7:35am » |
Quote Modify
|
Is it a double linked list (links to parent and child)? What exactly is the implementation of the datastructure? What kind of links are used, pointers, references, array-indexes, other?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Pietro K.C.
Full Member
 
Gender:
Posts: 213
|
|
Re: Linked List Node Deletion
« Reply #2 on: Apr 13th, 2003, 9:12am » |
Quote Modify
|
I'm gonna do this in the high level, as I'm hardly any good with programming... I assume here that a node in a linked list, at the very least, contains some data and, separately, a pointer to the next node (in a different field if the node is a record, for instance). Thus, the operations allowed are checking the data and accessing the next node - which can be done a number of times, and gives us access to all successor nodes. I assume also that the last element of the list has a special value, NULL, as its pointer value. Now. Suppose you are given node G.
1. Check to see if G's successor is NULL; if so, this is the unitary list (as G is in the middle), and you can delete G, using free(G) then G = NULL or whatever;
2. If not, let H be the immediate successor of G;
3. Copy H's data into G, overwriting the previous data;
4. Copy H's successor information into G's successor information (for instance, if a node was a record and G and H were pointers, you could do G->next = H->next);
5. Delete H.
|
|
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
Stu G
Guest
|
|
Re: Linked List Node Deletion
« Reply #3 on: Apr 13th, 2003, 4:01pm » |
Quote Modify
 Remove
|
Assuming a doubly-linked list:
Each node has a pointer to the previous node (PREV) and the next item (NEXT).
The list is composed of NODE_1, NODE_2,..., NODE_A, NODE_B, NODE_C, ... where NODE_B is the node to delete.
First, we get pointers to the nodes before and after NODE_B:
NODE_A = NODE_B.PREV
NODE_C = NODE_B.NEXT
Next, we modify the pointers of these two nodes in order to exclude NODE_B from the list:
NODE_A.NEXT = NODE_C
NODE_C.PREV = NODE_A
Finally we delete NODE_B from memory.
|
|
IP Logged |
|
|
|
Googler
Guest
|
|
Re: Linked List Node Deletion
« Reply #5 on: Apr 16th, 2003, 11:44am » |
Quote Modify
Remove
|
Instead of deleting the current list element, copy over the next element's data, and update it's "next" pointer to next->next, therefore removing the next element in the list, but overriding this element's data with the next element's data, and preserving the list structure.
|
|
IP Logged |
|
|
|
elemental
Newbie
Posts: 1
|
|
Re: Linked List Node Deletion
« Reply #6 on: Apr 24th, 2003, 6:54am » |
Quote Modify
|
The above idea would work, but it wouldn't be very efficient in terms of memory since you'd lose a node's worth of memory each time you did that.
What would work a bit better would be a recursive function to do this.
void *move_node_up(void *node)
{
if(node->next == NULL)
return node;
else
{
node->data = node->next->data;
node->next = node->next->next;
node->next = move_node_up(node->next);
}
}
This has the advantage of freeing up the last node's worth of memory. yay!
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Linked List Node Deletion
« Reply #7 on: Apr 24th, 2003, 8:06am » |
Quote Modify
|
that is very inefficient in terms of time..
It would be better if you could simply move the data from the last node directly to the one you're deleting, and adjucting connections accordingly.
If you have a double linked list it's easy, but that's not the case. Knowing the location of the last two nodes would also help, but I don't know if we can assume to have that knowledge either (though it much easier to keep track of then every parent-node).
So suppose you're at node i the next node is j, and the last two nodes are x and y (just travel down the connection to find them).
copy j to i, copy y to j, connect x to j, delete y
You can save a lot on copying data (and thus time) this way.
Without the extra administration mentioned earlier it may be to much of a bother to do it right though..
The obvious problem is that you don't really need the last x,y of the list, but rather the consecutive x,y of which the y is has the highest(/lowest) index into memory. Which changes every time you apply this method.
(Of course if you have the extra administration it's very easy to keep track)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Linked List Node Deletion
« Reply #8 on: Apr 30th, 2003, 2:37pm » |
Quote Modify
|
towr,
I'm not sure what you're saying, but moving data from the last node to the current node would change the order of the list, right?
Instead, you could move the data from the next node into the current node, direct the current node to the next next node, and delete what was the next node. Easy!
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Linked List Node Deletion
« Reply #9 on: May 1st, 2003, 12:07am » |
Quote Modify
|
Yes, but the new idea was to delete the node in such a matter that all the other nodes are still in a consecutive block of memory, without holes in it. So you want to free up a node at the beginning or end, leaving the block with nodes in it as a whole.
The order of the nodes in the block doesn't matter as long as they are connected properly, and my algorithm uses that to free up the last node worth of memory in the block, without loosing any information except the node you're deleting.
Maybe I should make a drawing.. (but not now)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
S. Owen
Full Member
Gender:
Posts: 221
|
|
Re: Linked List Node Deletion
« Reply #10 on: May 26th, 2003, 6:59am » |
Quote Modify
|
It's a linked list... who knows where the nodes are allocated? It is not usually contiguous anyway.
The central problem is that there is some node somewhere with a pointer to the node that is being deleted, and there is no way to find that node and change the pointer. So, you have to copy data from the next node into the current one. And so on.
I don't see another way to do it... I'd almost say it's provable for the reason above.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Linked List Node Deletion
« Reply #11 on: May 26th, 2003, 8:38am » |
Quote Modify
|
If you made the linked list yourself (which is almost always the case), you can have much more information to make dealing with it more efficient..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ChachaChoudryWanaB
Newbie
Duh
Posts: 1
|
|
Re: Linked List Node Deletion
« Reply #12 on: Jun 11th, 2003, 5:12pm » |
Quote Modify
|
Here is a O(1) solution unless node to be deleted is last node (in this case it is a O(n) solution).
void DeleteThisNode(Node* pNode, Node *pHead)
{
// Chedk if this pointer valid
if( (pNode == NULL) || (pHead == NULL) )
{
return;
}
// Check if this the last node in the list
if(pNode->Next != NULL)
{
// Copy data from next node
Node *pTemp = pNode->Next;
pNode->Data = pTemp->Data;
// Delete next node
pNode->Next = pTemp->Next;
// Free memory
free(pTemp);
}
else
{
// Traverse till last node
Node* pTemp = pHead;
while(pTemp->Next != NULL)
{
pTemp = pTemp->Next;
}
// Delete last node
Node* pLast = pTemp->Next;
pTemp->Next = NULL;
// Free memory
free(pLast);
}
}
|
|
IP Logged |
|
|
|
Birbal-Second
Newbie
Posts: 2
|
|
Re: Linked List Node Deletion
« Reply #13 on: Jan 17th, 2004, 6:30pm » |
Quote Modify
|
Head of list is not given here.
The solution to copy contents of next node to present node and then to link the node with next-to-next node is good solution. We can keep record of orphan node and then free its memory.
But only problem is what if the node is last node in list. What can be done then? Any ideas?
|
|
IP Logged |
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
   
Gender:
Posts: 767
|
|
Re: Linked List Node Deletion
« Reply #14 on: Jan 17th, 2004, 10:57pm » |
Quote Modify
|
on Jan 17th, 2004, 6:30pm, Birbal-Second wrote:But only problem is what if the node is last node in list. What can be done then? Any ideas?
|
|
Since this node is the middle node, delete the node and leave it at that. If it is both middle and end, it is a list with one element. You know it is the last element if the pointer to the next node is NULL, which is standard for a linked list.
If it has two elements, the middle node is the first node, and the proposed algorithm works. So the only special case is when the pointer to the next element is NULL, which adds almost no complexity to the algorithm, keeping it at O(1).
My reasoning is that you find the middle node by dividing the number of nodes by 2, integer arithmetic.
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
Birbal-Second
Newbie
Posts: 2
|
|
Re: Linked List Node Deletion
« Reply #15 on: Jan 18th, 2004, 2:43pm » |
Quote Modify
|
May be I could not understand the answer. We do not have access to list head, and so we can not find total number of nodes and divide that by two to get middle node. The question is as follows:
There is a singly linked list of unknown length. You are given a pointer to any node in that list. Write program for that.
Now if the node is any node other than the last node, the proposed algo works. (copy contents of next node to the node to be deleted. Set its next pointer to next to next node. And finally free up the memory of x-next node.)
Question is.. what if the node given is last node? I can find out if it is last by confirming whether its next node is NULL or not. I can now set this node NULL as well to do our task. But in that case, we are not freeing up the memory. If we do so before assigning it NULL, the memory segment can not be tracked.. I hope I am clear in describing the problem. Please correct me if I made any mistake. Thanks.
|
|
IP Logged |
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
Gender:
Posts: 767
|
|
Re: Linked List Node Deletion
« Reply #16 on: Jan 18th, 2004, 11:54pm » |
Quote Modify
|
on Jan 18th, 2004, 2:43pm, Birbal-Second wrote:| May be I could not understand the answer. We do not have access to list head, and so we can not find total number of nodes and divide that by two to get middle node. |
|
That is irrelevant. According to the question: "You are given a pointer to the middle node in a singly linked list." We don't need to calculate the middle node, that is already done. Think about it this way -- we are writing a function, and the input is the middle node. It is given to us by the calling function, so we don't need to calculate it.
Either way, given that the last node has a NULL "next node" pointer, whether or not this is the first or any other node is irrelevant. All we care about is whether it is the last node or not, and we can figure this out from the information given. Best of all, in either case, deletion is done in O(1) time.
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
Harish SS
Guest
|
|
Re: Linked List Node Deletion
« Reply #17 on: Feb 3rd, 2004, 12:34am » |
Quote Modify
Remove
|
All that one has to do is this. I hope we know the node structure!?
temp = mid->p_next_;
memmove(mid, mid->p_next_, sizeof(st_node) );
Free (temp);
OR
temp = mid->p_next_;
memcpy(mid, mid->p_next_, sizeof(st_node) );
Free (temp);
|
|
IP Logged |
|
|
|
Corleone
Newbie
Posts: 3
|
|
Re: Linked List Node Deletion
« Reply #18 on: Feb 15th, 2004, 1:08pm » |
Quote Modify
|
void deletenode(nodeptr n)
{
nodeptr tmp;
tmp = n->next;
n->data = n->next->data;
n->next = n->next->next;
free(tmp);
}
Ofcourse, you have to check if n->next is NULL, which is not the middle node and the last node and this would not work in that case.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Linked List Node Deletion
« Reply #19 on: May 22nd, 2004, 10:27am » |
Quote Modify
|
on Jun 11th, 2003, 5:12pm, ChachaChoudryWanaB wrote:Here is a O(1) solution unless node to be deleted is last node (in this case it is a O(n) solution).
[...]
// Traverse till last node
Node* pTemp = pHead;
while(pTemp->Next != NULL)
{
pTemp = pTemp->Next;
}
// Delete last node
Node* pLast = pTemp->Next;
pTemp->Next = NULL;
// Free memory
free(pLast);
[...]
} |
|
I don't think it works. After the while(){}, pTemp->Next is guaranteed to be NULL. So pLast is always NULL.
I think what you intended is
while(pTemp->Next != pNode){
pTemp = pTemp->Next;
}
Then you would free and unlink the wanted node pNode.
But it still doesn't address the situation where the node to remove is the first and only node. In that case, you have to NULL the list head pointer. But since you pass it by value, there is no way to do that.
|
|
IP Logged |
|
|
|
Birbal-Second1
Guest
|
|
Re: Linked List Node Deletion
« Reply #20 on: Jun 14th, 2004, 2:31pm » |
Quote Modify
Remove
|
In that case, u can pass head of the pointer using a double pointer.
Node* head;
call function as func(&head);
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Linked List Node Deletion
« Reply #21 on: Jun 14th, 2004, 4:39pm » |
Quote Modify
|
Yes. What I meant is that there is no way to do that with the signature:
void DeleteThisNode(Node* pNode, Node *pHead)
Note that once you are using pointer-to-pointer, you can simplify the loop:
void DeleteThisNode(Node* pNode, Node** ppHead){
if( !pNode || !ppHead ) return;
while( *ppHead && *ppHead != pNode ){
ppHead = &((*ppHead)->next);
}
if( *ppHead ){
*ppHead = pNode->next;
free(pNode);
}
}
|
|
IP Logged |
|
|
|
Vikash Kodati
Guest
|
|
Re: Linked List Node Deletion
« Reply #22 on: Nov 3rd, 2004, 1:41pm » |
Quote Modify
Remove
|
Hi All:
Many of you proposed O(1) solutions except for the case when the node to be deleted in the last one in the list.
Without loss of generality, we can add a last node which represents NULL but is not the actual NULL is reality. This way we can avoid the boundary condition checks and the code you guyz proposed would work for all cases.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print