0

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:

#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:

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

2
Contributors
1
Reply
9
Views
9 Years
Discussion Span
Last Post by Narue
0

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:

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:

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.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.