Member Avatar for low1988

I have little knowledge about this algorithm method .I try to coding the part of the InsertAfter() method to insert the data after a specific location.It seems not working .

#include <iostream>
#include <string>
#include <conio.h>

using namespace std;

class Node {
	public:
   	double data; 	// data
	Node* next; 	// pointer to next
};

class List {
	public:
		List(void) 
        { head = NULL;
        cout <<"Head value is "<<head<<endl; } // constructor
		~List(void); // destructor
		bool IsEmpty() { return head == NULL; }

		Node* InsertNode( double x);
	    int FindNode(double x);
		int DeleteNode(double x);
		void DisplayList(void);
		Node* InsertAfter(double,double);

  	 private:
		Node* head;
};

Node* List::InsertAfter(double x,double y)
{
    Node* prevNode = NULL;
	Node* currNode = head;
	while (currNode && currNode->data != x) 
    {
		prevNode = currNode;
		currNode = currNode->next;
		}
	if (currNode) 
    {
		if (prevNode)
         {
		Node* newNode = new Node;
		newNode->data = y;}
        }}
   
List::~List(void) {
	Node* currNode = head, *nextNode = NULL;
	while (currNode != NULL) {
		nextNode = currNode->next;
		// destroy the current node
		delete currNode;
		currNode = nextNode;
	}
}


Node* List::InsertNode(double x) {
	int currIndex = 0;
	cout <<"currIndex is "<<currIndex<<endl;
	Node* currNode = head;
	Node* prevNode = NULL;
	cout <<"The x value is "<<x<<endl;
	cout <<"CurrNode value is :"<<currNode<<endl;
	cout <<"PrevNode value is :"<<prevNode<<endl;
	
	while (currNode && x > currNode->data) {
          cout <<"currNode->data is "<<currNode->data<<endl;
        prevNode = currNode;
        cout <<"PrevNode value is :"<<prevNode<<endl;
        currNode = currNode->next;
        cout <<"CurrNode value is :"<<currNode<<endl;
		currIndex++;
	}

   	Node* newNode = new Node;
   	cout<<"New node is created the address is "<<newNode<<endl;
	newNode->data = x;
	cout <<"newNode->data :"<<newNode->data<<endl;
	if (currIndex == 0) {
		newNode->next = head;
		cout <<" newNode->next value is head = "<<newNode->next<<endl;
		
		head = newNode;
		cout <<"The head value is newNode address"<<head<<endl<<endl;
		
  	 } else {
		newNode->next = prevNode->next;
		cout<<"newNode->next is "<<newNode->next<<endl;
		prevNode ->next = newNode;
		cout <<"prevNode->next is "<<prevNode ->next;
   	}
  
return newNode;
}

int List::FindNode(double x) {
	Node* currNode = head;
	int currIndex = 1;
	while (currNode && currNode->data != x) {
		currNode = currNode->next;
		currIndex++;
	}
	if (currNode)
		return currIndex;
	else
		return 0;
}

int List::DeleteNode(double x) {
	Node* prevNode = NULL;
	Node* currNode = head;
	int currIndex = 1;
	while (currNode && currNode->data != x) {
		prevNode = currNode;
		currNode = currNode->next;
		currIndex++;
	}
	if (currNode) {
		if (prevNode) {
			prevNode->next = currNode->next;
			delete currNode;
		} 
        if(!currNode)
        {
			head = currNode->next;
			delete currNode;
		}
		return currIndex;
   	}
	return 0;
}




void List::DisplayList()
{
	int num = 0;
	Node* currNode = head;
	while (currNode != NULL) {
		cout << currNode->data << ", ";
		currNode = currNode->next;
		num++;
	}
	cout << "\nNumber of nodes in the list: " << num << endl;
}

int main()
{
	List list;
   int number;
   list.InsertNode(2);
   list.InsertNode(7);
   cout<<endl<<endl;
   list.DisplayList();
   list.InsertAfter(2,6);
   list.DisplayList();
   
   getch();
	return 0;
}

The final should be 2 ,6, 7 as i expected ,but it is not in contrast.Anyway to deal with it ?

  • 2 Contributors
  • 1 Reply
  • 122 Views
  • 11 Hours Discussion Span
  • Latest Post Latest Post by Tom Gunn

Dani AI

Generated

— the root cause is that your InsertAfter never links the newly created node into the list, and there are a couple of edge-case bugs elsewhere. pointed this out and gave the right idea: find the target node, create a new node, point the new node at the old successor, then point the target at the new node. Also decide what you want to happen when the list is empty or the target value is not found (fail, append, or insert as single node).

A compact, robust InsertAfter that handles empty list and "target not found = append" looks like this:

Node* List::InsertAfter(double target, double value)
{
    if (!head) {
        Node* n = new Node;
        n->data = value;
        n->next = nullptr;
        head = n;
        return n;
    }

    Node* curr = head;
    while (curr && curr->data != target)
        curr = curr->next;

    if (!curr) {                     // target not found -> append
        Node* tail = head;
        while (tail->next) tail = tail->next;
        Node* n = new Node;
        n->data = value;
        n->next = nullptr;
        tail->next = n;
        return n;
    }

    Node* n = new Node;
    n->data = value;
    n->next = curr->next;
    curr->next = n;
    return n;
}

Also fix DeleteNode: the test for removing the head should check whether prev is null — not curr. Example:

if (!prev) head = curr->next; else prev->next = curr->next;
delete curr;

Quick debugging tips: print node data (not addresses) when tracing, initialize head to nullptr in the constructor, give Node a constructor that sets next to nullptr to avoid uninitialized pointers, and run the program under Valgrind or your platform’s memory checker to catch leaks or invalid frees. For modern C++ prefer nullptr over NULL. For reference reading, see cppreference’s forward_list overview and a step‑by‑step insertion example on GeeksforGeeks: forward_list (cppreference) and Linked List — Inserting a node (GeeksforGeeks).

Member Avatar for Tom Gunn

One problem is that you never actually insert the node in that method. :) Another thing I noticed is that you do not handle edge cases. What happens if you call InsertAfter() on an empty list or the search fails? Inserting to an empty list can be a special case, and then you do not need to check currNode for NULL in the loop. If the node is not in the list, you can check currNode->next for NULL and use that to stop the loop. That way the next insertion will be at the end.

The last problem is that your algorithm is too complex. A previous node pointer is appropriate for an insert before operation, but with insert after you only need the current pointer:

if (IsEmpty())
{
    // special case: insert to empty list
    newNode->next = NULL;
    head = newNode;
}
else
{
    Node* currNode = head;

    while (currNode->next && currNode->data != x) 
    {
        currNode = currNode->next;
    }

    newNode->next = currNode->next;
    currNode->next = newNode;
}

It helps to draw the structure of the list as you fiddle with it. Visualizing data structures makes them easier to write code for. :)

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.