Deleting any node from a singly linked list

Expand Post »

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:

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:

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.

Similar Threads

DemonSpeeding

Reputation Points: 10

Solved Threads: 0

Light Poster

Offline

31 posts
since Oct 2007

Permalink

Dec 6th, 2007

Re: Deleting any node from a singly linked list

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:

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:

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.

Narue

Administrator

Reputation Points: 6442

Solved Threads: 1393

Bad Cop

Offline

11,807 posts
since Sep 2004

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C++ Forum Timeline: 'Grocery Counter' using Classes

Next Thread in C++ Forum Timeline: How to represent a space and a tab?

DaniWeb Message

Cancel Changes

User Name
Password