?
Solved

Loop to add data to a list

Posted on 2003-03-16
13
Medium Priority
?
253 Views
Last Modified: 2010-04-01
I have developed a add function but I am having trouble developing a loop to read characters in from a file to insert into a linked list. The following is my code for the insert function:

void List::Add(ItemType item) {
     InsertAfter(head, new Node(item, NULL));
};

void List::InsertAfter(Node* node, Node* newNode) {
     Node* afterNode = node->next;
     node->next = newNode;
     newNode->next = afterNode;
     size++;
};
0
Comment
Question by:lrl0106
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 8
  • 3
  • 2
13 Comments
 
LVL 4

Expert Comment

by:n_fortynine
ID: 8149845
It could very possibly be that you are passing in a new Node(item, NULL) which is a temporary variable that was created when Add() is called and then after the InsertAfter's call the program goes back to finish off the Add() and it'll (new Node) probably get destroyed so you don't have anything else for node->next to point to. Aliasing is evil if you know what I mean.

Could change your code to
InsertAfter() {
Node* afterNode = node->next;
node->next = newNode(newNode->item, afterNode);
++size;
}

I suggest that you change the name of the parameter item in Add() to something else, like newItem to avoid confusion with the item of your Node struct.
0
 
LVL 4

Expert Comment

by:n_fortynine
ID: 8149858
>>node->next = newNode(newNode->item, afterNode);
node->next = new Node(newNode->item, afterNode);

sorry =)
0
 
LVL 4

Expert Comment

by:n_fortynine
ID: 8149859
the parameters of InsertAfter are supposed to be the same
0
VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

 
LVL 4

Expert Comment

by:n_fortynine
ID: 8149896
your chosen implementation will add the file "backwards," does that matter to you?

for ex: o c t o b e r would become the list r e b o t c o???
0
 
LVL 4

Expert Comment

by:n_fortynine
ID: 8150254
>>InsertAfter() {
>>Node* afterNode = node->next;
>>node->next = newNode(newNode->item, afterNode);
>>++size;
>>}

void List::Add(ItemType newItem) {
    InsertAfter(head, new Node(newItem, NULL));
}

void List::InsertAfter(Node* node, Node* newNode) {
    Node* afterNode = node->next;
    node->next = new Node(newNode->item, afterNode);
    afterNode = NULL;
    size++;
}
0
 
LVL 12

Expert Comment

by:Salte
ID: 8150748
Your code seems ok to me.

No, the new node will NOT get destroyed. The temporary location is a temporary pointer to the node. The pointer is destroyed when the temporary variable isn't used any more but the object it is pointing to is not.

Your function will insert the new node after the given node (the node named 'node').

I believe your error is somewhere else. This function seem fine. n_fortynine is definitely on the wrong track. Don't listen to him/her.

Yes, aliasing can be evil but there's no aliasing problems in either of your functions. I believe the error is somewhere else.

Alf
0
 
LVL 12

Expert Comment

by:Salte
ID: 8150792
Also, the backwards issue is only an issue if you don't want it. If you want to use the list as a stack it is perfect.

If you want to make the list in the order the items are read from file you should probably change the List::Add() function to insert after 'tail' and also set tail.

void List::Add(ItemType item) {
    Node * n = new Node(item,NULL);
    InsertAfter(tail, n);
    tail = n;
};

A better way would be to do it in InsertAfter so that you did:

void List::Add(ItemType item) {
    InsertAfter(tail, new Node(item, NULL));
};

void List::InsertAfter(Node* node, Node* newNode) {
    Node* afterNode = node->next;
    node->next = newNode;
    newNode->next = afterNode;
    if (node == tail)
       tail = newNode;
    size++;
};

This require your list to have both a head and a tail pointer. If you are sure you have a head element the above code is fine, you simply initialize tail to point to the dummy head Node. Note then that the real first element is not head but head -> next.

Another solution is to not use a dummy head object in that case you need to do it like this:

void List::InsertFirst(Node * newNode)
{
   newNode -> next = head;
   if (tail == head)
      tail = newNode;
   head = newNode;
   size++;
}

And then have InsertAfter(Node * node, Node * newNode)
{
   if (node == NULL)
      InsertFirst(newNode);
   else {
      newNode -> next = node -> next;
      node -> next = newNode;
      if (tail == node)
         tail = newNode;
      size++;
   }
}

Then if head and tail are initialized to NULL an InsertAfter(tail,...) will cause the new node to be inserted at the beginning and both head and tail will be set to the new node. Next time when ou insertAfter(tail, ..) the tail will not be NULL and you insert the object after old tail and tail will be updated to point to the new node. If you later insert a node at the beginning by InsertAfter(NULL,...) it will only change head and not tail. If you later insert a node at the end by InsertAfter(tail,....) it will change tail but not head. If you insert a node in the middle of the list neither head nor tail will change.

Alf
0
 
LVL 4

Expert Comment

by:n_fortynine
ID: 8150796
Sorry, I didn't know. I thought that might have been the problem. Thanks for correcting me Salte =).
0
 
LVL 12

Expert Comment

by:Salte
ID: 8150849
Actually the opposite problem is often a source of memory leaks. People do things like:

int func(T * x);


....
int k = func(new T());

and if func doesn't save that pointer you have memory leaks because the temporary does not destroy the T object.

Alf
0
 

Author Comment

by:lrl0106
ID: 8152487
Thank you fo the advice. I re-arranged the code so that I am inserting to the end of the list but I still have the problem that I am not seeing the output of the list to the screen. My code is as follows:

//header
#include <cstddef>
#ifndef _CIRCLINKEDLISTaa_H
#define _CIRCLINKEDLISTaa_H
using namespace std;

class List {
public:
    // the type of object that the list will be store
    typedef char ItemType;
   
    // an empty linked-list is created
    List();
   
    // cleanup the list
    ~List();

    // add the element e to the head of the list
    void Add(ItemType e);

    // if found, return the cost (at least 1)
    // if not found, return -1
    int Find(ItemType item);
   
    // print out the whole list from head to tail
    void Print();

    // the size of the linked list
    int Size();

private:
    struct Node {
         ItemType item;
         Node* next;
         
         Node() { next = NULL; };
         Node(ItemType _item, Node* _next) { item = _item; next = _next; };
    };
   
    // insert newNode after node
    // (... -> node -> newNode -> ...)
    void InsertAfter(Node* node, Node* newNode);
   
    // delete node->next
    bool DeleteNextNode(Node* node);
   

    // head always points to a dummy head
    Node* head;
   
  // cur keeps track of where you are
  Node* cur;

  // points to the end of the list
  Node* tail;

    // the size of the list
    int size;
};

#endif

///implementation
#include <iostream>
#include "CIRCLINKEDLISTaa.h"

////////////////////////////////////////////////////////////////
// constructor and destructor
////////////////////////////////////////////////////////////////

List::List() {
    size = 0;
   
    // insert a dummy head,
    // the value does not mean anything
    head = new Node;
    head->next = head;
};

List::~List() {
    while(head->next != head) DeleteNextNode(head);
    delete head; // delete the dummy node
};
/*
void List::Add(ItemType newItem) {
    InsertAfter(head, new Node(newItem, NULL));
};
*/
void List::Add(ItemType item) {
   InsertAfter(tail, new Node(item, NULL));
};
////////////////////////////////////////////////////////////////
// size
////////////////////////////////////////////////////////////////
int List::Size() {
    return size;
};

////////////////////////////////////////////////////////////////
// print
////////////////////////////////////////////////////////////////

void List::Print() {
    Node* n = head->next; // points to the real first element
    cout << '<';
    while (n != head) {
         cout << n->item << ' ';
         n = n->next;
    };
    cout << "> size = " << Size() << endl;
};

////////////////////////////////////////////////////////////////
// find member function
////////////////////////////////////////////////////////////////

int List::Find(ItemType item) {
    Node* curr = head->next; // points to the real first element
    int cost = 1;
   
    while ((curr != head) && (curr->item != item)) {
         curr = curr->next; // advance to next element
         cost++;
    };
   
    if (curr == head) {
         // cannot find item in the list
         cost = -1;
    };
   
    return cost;
};

////////////////////////////////////////////////////////////////
// insert member functions
////////////////////////////////////////////////////////////////
/*
void List::InsertAfter(Node* node, Node* newNode) {
    Node* afterNode = node->next;
    node->next = new Node(newNode->item, afterNode);
    afterNode = NULL;
    size++;
};
*/
void List::InsertAfter(Node* node, Node* newNode) {
   Node* afterNode = node->next;
   node->next = newNode;
   newNode->next = afterNode;
   if (node == tail)
      tail = newNode;
   size++;
};
////////////////////////////////////////////////////////////////
// delete member functions
////////////////////////////////////////////////////////////////

bool List::DeleteNextNode(Node* node) {
    if (NULL == node || head == node->next) {
         // the head is the dummy node, and never delete it!
         return false; // nothing can be deleted
    };
   
    Node* nextNode = node->next;
    node->next = nextNode->next;
    delete nextNode;
    size--;
   
    return true;
};

//main
#include <string>
#include <iostream.h>
#include <fstream.h>
#include <stdlib.h>
#include "CIRCLINKEDLISTaa.H"

//using namespace std;

int main() {
  List list;

  //int skipnumber;
/////////////////////////////////////////

  //cout<<"Enter the skip number: ";
  //cin>>skipnumber;





//////////////////////////////////////////

  char* readfile = new char[80];
  cout<<"Enter the file name:";
  cin>>readfile;
  ifstream fin;
  fin.open(readfile);

  char ch;
  while(fin >> ch)
     list.Add(ch);

  list.Print();

////////////////////////////////////////////


  system("PAUSE");
  return(0);
}
0
 
LVL 4

Accepted Solution

by:
n_fortynine earned 160 total points
ID: 8152724
I think I helped out somebody else working on the same code and although this code works fine on my GCC compiler on UNIX, it gives output and everything, it somehow does not work on Dev-C++, which I do not see why (and I have Bloodshed 5 but do not know how to use it).
0
 

Author Comment

by:lrl0106
ID: 8166992
The problem was not he coe but the way that my computer generates text files. If I generate the file on my computer then I can not access it through my code. But if I create it else where, then up upload it to my machine then I am able to access it. Thank you for your help.
0
 
LVL 4

Expert Comment

by:n_fortynine
ID: 8167685
Erh, lrl0106 I think Salte actually has the answer to your initial question so you might consider giving him points? Just a suggestion =).
0

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

In days of old, returning something by value from a function in C++ was necessarily avoided because it would, invariably, involve one or even two copies of the object being created and potentially costly calls to a copy-constructor and destructor. A…
Many modern programming languages support the concept of a property -- a class member that combines characteristics of both a data member and a method.  These are sometimes called "smart fields" because you can add logic that is applied automaticall‚Ķ
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.
Suggested Courses

771 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question