wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Linked List Node Deletion
        
(Message started by: william wu on Apr 12^th, 2003, 1:57pm)

Title: Linked List Node Deletion
Post by william wu on Apr 12^th, 2003, 1:57pm

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

Title: Re: Linked List Node Deletion
Post by towr on Apr 13^th, 2003, 7:35am

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?

Title: Re: Linked List Node Deletion
Post by Pietro K.C. on Apr 13^th, 2003, 9:12am

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.
[hide]

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.[/hide]

Title: Re: Linked List Node Deletion
Post by Stu G on Apr 13^th, 2003, 4:01pm

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.

Title: Re: Linked List Node Deletion
Post by william wu on Apr 13^th, 2003, 6:20pm

Sorry, I forgot to mention that the linked list is a singly linked list.

Title: Re: Linked List Node Deletion
Post by Googler on Apr 16^th, 2003, 11:44am

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.

Title: Re: Linked List Node Deletion
Post by elemental on Apr 24^th, 2003, 6:54am

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!

Title: Re: Linked List Node Deletion
Post by towr on Apr 24^th, 2003, 8:06am

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)

Title: Re: Linked List Node Deletion
Post by James Fingas on Apr 30^th, 2003, 2:37pm

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!

Title: Re: Linked List Node Deletion
Post by towr on May 1^st, 2003, 12:07am

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)

Title: Re: Linked List Node Deletion
Post by S. Owen on May 26^th, 2003, 6:59am

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.

Title: Re: Linked List Node Deletion
Post by towr on May 26^th, 2003, 8:38am

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..

Title: Re: Linked List Node Deletion
Post by ChachaChoudryWanaB on Jun 11^th, 2003, 5:12pm

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);
}
}

Title: Re: Linked List Node Deletion
Post by Birbal-Second on Jan 17^th, 2004, 6:30pm

;D
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?

Title: Re: Linked List Node Deletion
Post by John_Gaughan on Jan 17^th, 2004, 10:57pm

on 01/17/04 at 18:30:31, 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.

Title: Re: Linked List Node Deletion
Post by Birbal-Second on Jan 18^th, 2004, 2:43pm

:-[

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.

Title: Re: Linked List Node Deletion
Post by John_Gaughan on Jan 18^th, 2004, 11:54pm

on 01/18/04 at 14:43:36, 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.

Title: Re: Linked List Node Deletion
Post by Harish SS on Feb 3^rd, 2004, 12:34am

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);

Title: Re: Linked List Node Deletion
Post by Corleone on Feb 15^th, 2004, 1:08pm

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.

Title: Re: Linked List Node Deletion
Post by grimbal on May 22^nd, 2004, 10:27am

on 06/11/03 at 17:12:35, 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.

Title: Re: Linked List Node Deletion
Post by Birbal-Second1 on Jun 14^th, 2004, 2:31pm

In that case, u can pass head of the pointer using a double pointer.

Node* head;

call function as func(&head);

Title: Re: Linked List Node Deletion
Post by Grimbal on Jun 14^th, 2004, 4:39pm

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);
}
}

Title: Re: Linked List Node Deletion
Post by Vikash Kodati on Nov 3^rd, 2004, 1:41pm

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.