DaniWeb Forum Index > Software Development > C++

C++ RSS

Deleting any node from a singly linked list

Please support our C++ advertiser: Intel Parallel Studio Home

•

Join Date: Oct 2007

Posts: 31

Reputation: DemonSpeeding is an unknown quantity at this point

Solved Threads: 0

DemonSpeeding DemonSpeeding is offline

Offline

Light Poster

Deleting any node from a singly linked list

Dec 6th, 2007

I believe what I have written at the moment is a singly linked list, and I can't figure out how to delete whatever node the user specifies, I've toyed around with it but I'm stumped.

Here's my specification file:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
#include<string>
using namespace std;
class Node
{
        Node *prev;
        Node *next;
        string data;
public:
        //Function Declarations
        void print(Node *&);
        void insertLast(Node *&);
        void delAny(Node *&);
};
#include<string>
using namespace std;
class Node
{
        Node *prev;
        Node *next;
        string data;
public:
        //Function Declarations
        void print(Node *&);
        void insertLast(Node *&);
        void delAny(Node *&);
};

And here's the implementation file:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
#include <iostream>
#include "linkedlist.h"
#include <string>
using namespace std;
 
void Node::print(Node *&temp)
{
        if(temp==NULL) {
                cout << "List is Empty " << endl;
        }
        else {
                Node *tmp=temp;
                while(tmp!=NULL)
                {
                        cout<<tmp->data<<endl;
                        tmp=tmp->next;
                }
        }
}
 
void Node::insertLast(Node *&temp)
{
        Node *newNode;
        newNode=new Node;
        if (temp==NULL)
        {
                cout<<"\nEnter Data :";
                cin>>newNode->data;
                newNode->next=temp;
                temp=newNode;
        }
        else
        {
                Node *curr;
                curr=temp;
                while(curr->next!=NULL)
                {
                        curr=curr->next;
}
                cout<<"\nEnter Data :";
                cin>>newNode->data;
                newNode->next=NULL;
                curr->next=newNode;
        }
}
 
void Node::delAny(Node *&temp) {
        Node *newNode;
        newNode=new Node;
        if(temp==NULL) {
                cout << "List is Empty " << endl;
        }
        else
        {
                cout<<"\nEnter Data :";
                cin>>newNode->data;
                newNode->next=temp;
                temp=newNode;
 
 
 
}
#include <iostream>
#include "linkedlist.h"
#include <string>
using namespace std;

void Node::print(Node *&temp)
{
        if(temp==NULL) {
                cout << "List is Empty " << endl;
        }
        else {
                Node *tmp=temp;
                while(tmp!=NULL)
                {
                        cout<<tmp->data<<endl;
                        tmp=tmp->next;
                }
        }
}

void Node::insertLast(Node *&temp)
{
        Node *newNode;
        newNode=new Node;
        if (temp==NULL)
        {
                cout<<"\nEnter Data :";
                cin>>newNode->data;
                newNode->next=temp;
                temp=newNode;
        }
        else
        {
                Node *curr;
                curr=temp;
                while(curr->next!=NULL)
                {
                        curr=curr->next;
}
                cout<<"\nEnter Data :";
                cin>>newNode->data;
                newNode->next=NULL;
                curr->next=newNode;
        }
}

void Node::delAny(Node *&temp) {
        Node *newNode;
        newNode=new Node;
        if(temp==NULL) {
                cout << "List is Empty " << endl;
        }
        else
        {
                cout<<"\nEnter Data :";
                cin>>newNode->data;
                newNode->next=temp;
                temp=newNode;



}

I'm not sure what to do with the function to get it to delete whatever the user enters from the list.

•

Join Date: Sep 2004

Posts: 7,696

Reputation: Narue has a reputation beyond repute

Solved Threads: 728

Narue

Offline

Code Goddess

Re: Deleting any node from a singly linked list

Dec 6th, 2007

To delete any node from a single linked list you have the average case and one edge case. The average case is easy: loop through the list until the next node is the node you're trying to delete, and set the current node's link to the link of the node you want to delete:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
while ( iter->next != 0 && iter->next->data != key )
  iter = iter->next;
 
if ( iter->next != 0 )
  iter->next = iter->next->next;
while ( iter->next != 0 && iter->next->data != key )
  iter = iter->next;

if ( iter->next != 0 )
  iter->next = iter->next->next;

This works for deleting every node except the first because there's no node that points to it. So you need to do reset the first node to point to its link:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
if ( head->data == key )
  head = head->next;
else {
  //...
 
  while ( iter->next != 0 && iter->next->data != key )
    iter = iter->next;
 
  if ( iter->next != 0 )
    iter->next = iter->next->next;
}
if ( head->data == key )
  head = head->next;
else {
  //...

  while ( iter->next != 0 && iter->next->data != key )
    iter = iter->next;

  if ( iter->next != 0 )
    iter->next = iter->next->next;
}

It really helps to draw this logic out on paper. What I like to do is simulate the logic with a handful of change.