Help with strings and linked lists

[trevormoon]

Hello all, I am having some trouble adding strings to a linked list program my professor gave us. For some reason the only thing that will work with the sll is ints. I figured out how to use the standard template library list function while using strings, but cannot figure out how to convert the other one. Also I have been reading about the stl list function and cannot find a member function for next that would allow me to compare two items in the linked list and was wondering if it even existed.

#include <iostream>
#include <stdlib.h>

using namespace std;

struct Node
  {
    int info;
    Node * next;
  };

Node *head=NULL, *p, *t;
void Insert_Left(Node * &head, Node *p)
  {
    if (!head)
      {
        //cout << p->info << ' ';
        head = p;
      }
    else
      {
        p->next = head;
        //cout << p->info << ' ';
        head = p;
      }
  }

Node * Remove_Left(Node *&root)
  {
    Node * p;
    p = root;
    if (root)
      {
        root = p->next;
      }
    return p;
  }

int empty()
  {
    return head == NULL;
  }


#if __INCLUDE_LEVEL__ < 1
int main()
  {
    int i;

    for (i = 0; i < 5; i++)
      {
        p = new Node;
        p->info = 5trree -0;
        p->next = NULL;
        Insert_Left(head, p);
      }
    cout << endl;

    t = head;
    while (t)
      {
        cout << t->info << ' ';
        t = t->next;
      }
    cout << endl;
  }

#endif

[o3hC5Di1]

Hi there,

Your linked list is made up of nodes:

struct Node
  {
    int info;
    Node * next;
  };

The value of each node is store in "info", which as you can see, is an int. So to make the linked list contain strings, that's what you'll need to adapt. Usually, this is done using templates, but I would rather not confuse you as this is more of an intermediate subject.

The STL list implementation is a doubly linked list, meaning it contains both "next" and "previous" pointers in order to iterate the list both in forward and in reverse order. Iterating STL containers is usually done using iterators, which act as an abstraction in order to have a uniform approach to access all STL containers.

Hope that helps, please do let us know if you have any further questions.

All the best,
NwN

[trevormoon]

Hi NwN thank you for the help. So are you saying with the current code I have it would be more trouble than it's worth to change the list to use strings? For the STL list here is the code I am working with now. I have an iterator t, with that can I use something like t = next? Also I am trying to read in strings from another file, sort and print them as they come in. The code I have come up with so far just gives me 30 lines of errors so I am not sure what I am doing wrong. I have been looking at the reference articles on the STl list on the site and haven't found anything that looks similar to what I am trying to accomplish.
Here is an example of the strings I am using this is just a few of them, there are 107 in total.
4rnighan - .
100 function. .
107t.=+=+ .
26ls or GOTO's.
79ibraries.=+=.
20acilities=+s.
67the first=+s.
24n the page, .
2ion to C - .
57efinitions. .

while(getline(indata,aline))
         {
           mylist.push_back(aline);
           mylist.sort();
           
          t = mylist.begin() + i;
          cout<< *t<<endl;
          i++;
         }

  #include<iostream>
#include <stdlib.h>
#include <list>
#include <string>
#include <fstream>
using namespace std;

int main()
  {
   list<string> mylist;
    string aline;
   list<string>::iterator t;
    ifstream indata;
    indata.open("packet.data");

    int i;
       while(getline(indata,aline))
         {
           mylist.push_back(aline);
           mylist.sort();
         }

  for(t=mylist.begin(); t!=mylist.end(); t++)
    {
      cout<< *t<<" "<<endl;
   }
return 0;
}

[o3hC5Di1]

Hi there,

To make your list work with strings, just change the type of info:

struct Node
  {
    int info;
    std::string info;
    Node * next;
  };

As a small remark on your STL-implementing code:

while(getline(indata,aline))
         {
           mylist.push_back(aline);
           mylist.sort(); 
         }

It's probably more efficient to fill the container first, then sort it.
You could also (since it's a linked list and insertion is cheap) do the following to keep it sorted:

#include <algorithm>
while(getline(indata,aline))
{
           mylist.insert(std::lower_bound(mylist.begin(), mylist.end(), aline), aline);
}

Since the implementation (ie the "next" pointer) is hidden in std::list, you cannot (and should not) access it directly. You don't need to anyway because you can pretty much get the same effect using t++.

Hope that helps.

All the best,
NwN

[trevormoon]

Hello again NwN thank you for helping me, this is my first time using points. What I am trying to do with this program is read in data, and print the data in order while the program is still reading the file. So for example I have some data say:

4t
2y
3d
1r
7h
9e

I want to read in the 4t, 2y, 3d, 1r, then print out 1r, 2y, 3d, 4t remove them from the list then read in the 7h, 9e etc. I cannot seem to figure out how to access the elements while they are being read in the while loop. So say I want to compare the string that has just been read in to see if its the 1r, I can't figure out the code on how to compare what has been inserted on the list to what is being read in.

Thank you again for your help,
Trevor T