CODEWITHSUNDEEP
c++algorithmlinked-listnodessingly-linked-list
A Phototactic Coder
A Phototactic Coder

Reputation: 343

How to remove intermediate node from a linked list

I have a singly linked list. If I want to delete an known element from this linked list, what can I do?

For example: Node* head; (44) Node* tail; (39)

linked list: 44 27 59 13 45 39 we want to delete 45 from it. and get: 44 27 59 13 39

I only figured out that delete first element from list(if element(need to be removed) is first element of the list). I got: head = head-> next;

How to remove intermediate node from list?

Upvotes: 1

Views: 1472

Answers (6)

Namnesh Rai
Namnesh Rai

Reputation: 1

You just have to analyse the problem first and know the changes required if we delete a particular node. let us suppose that we have the address of the node which is supposed to be deleted there can be 3 cases if the node is the 1st node or the last node or a middle node ie a minimum 2 nodes.

void deletenode(struct node **s,struct node *t){
    struct node *temp;
        if(*s==t)
        {
            *s=t->next;
            free(t);
        }
        else{
            temp=*s;
            while(temp->next!=t)
            {
                temp=temp->next;
            }
               temp->next=t->next;
               delete(t);
        }
        
}

Upvotes: 0

Vikram Bhat
Vikram Bhat

Reputation: 6246

This pseudo code might help you :-

void remove(int key) {
  Node* p  = head->next;
  Node*prev = head;
  while(p!=NULL) {

     if(p->data==key) {
        prev->next = p->next;
        free(p);
        break;           
     }
     prev = p;
     p = p->next;
  }
}

Upvotes: 1

Prince
Prince

Reputation: 20862

Think through the problem.

You need a loop to traverse all the nodes till you find the one you are looking for. Say you have Node* curr, prev both pointing to head.

while(curr != null)

For each node you need to check if the value matches or not with the node that you are looking for.

if (curr->value == node_you_are_looking_for->value)

If this is the matching node, delete this node. You have two pointers to update the links.

prev->next = curr->next;
prev = curr;
curr = curr->next;
prev->next = null;
delete(prev);

Else keep on traversing the list.

prev = curr;
curr= curr->next;

Then you can assemble all these steps and write a working program.

Upvotes: 0

Mobi
Mobi

Reputation: 645

13 will be pointing 45 as its next element, simple change its next element to 39. And free the 45 from memory, just to keep memory clean from trash.

Upvotes: 1

congusbongus
congusbongus

Reputation: 14622

First, find the element you want to delete. Don't forget to handle when the element doesn't exist:

Node* find(Node* head, int value) {
    do {
        if (head->value == value) return head;
        head = head->next;
    } while (head);
    return nullptr;
}

Then, you want to connect the previous node's next ptr to the next node. In a singly-linked list, you can track the previous node using a local variable. Don't forget to handle if the node you want to delete is the head (i.e. no previous node), or if the node is the tail (i.e. no next node):

Node *previous = nullptr;
do {
    if (head->value == value) {
        if (previous != nullptr) {
            previous->next = head->next;
        }
        if (head == tail) {
            tail = previous;
        }
        return;
    }
    previous = head;
    head = head->next;
} while (head);

Upvotes: 0

Jonathan Leffler
Jonathan Leffler

Reputation: 753675

Look at the value in the next node, if there is a value. If that is the value you're looking for, then the next node is the one to delete, so you make the current node's next element point to the next node's next element, after preserving a pointer to the next node so that you can delete it.

// Assuming head is a non-const reference variable (or a global variable) 
if (head == NULL)
    return;
if (head->value == wanted)
{
    head = head->next;
    return;
}
for (Node *curr = head; curr->next != NULL; curr = curr->next)
{
    if (curr->next->value == wanted)
    {
        Node *old = curr->next;
        curr->next = curr->next->next;
        delete old;
        return;
    }
}
return;  // Possibly after reporting that the value wanted was not found

Upvotes: 0

Related Questions