Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
?
Solved

Loop to add data to a list

Posted on 2003-03-16
13
Medium Priority
?
257 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
  • 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
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
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

Upgrade your Question Security!

Your question, your audience. Choose who sees your identity—and your question—with question security.

Question has a verified solution.

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

What is C++ STL?: STL stands for Standard Template Library and is a part of standard C++ libraries. It contains many useful data structures (containers) and algorithms, which can spare you a lot of the time. Today we will look at the STL Vector. …
This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why t…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

564 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