11 Replies - 1817 Views - Last Post: 18 July 2012 - 08:51 AM Rate Topic: -----

#1 koldrakan  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 11
  • Joined: 16-April 09

Add node to linked list by user input

Posted 18 July 2012 - 02:27 AM

I am writing a program to handle a record collection using a double linked list (yes, it is an assignment). Now I am trying to add nodes to the list by user input. It basically works to add one node, but when I try to add another the program crashes. My own conclusion is that this is due to the naming, i.e. I try go give the nodes the same name, but I don't know how to name them dynamically. I have read about linked lists for hours on end, but I haven't found any solution.
Any hints or insights are greatly appreciated!

Here are parts of the code:

The struct:
struct CDNode
{
    int ID; //För att hålla koll på noderna

    CDNode *next;
    CDNode *prev;

    char titel[80];
    char artist[80];
    int speltid, antalspr;
};



The function to add a node, "laggtill":
void laggtill(CDNode *NewNode)
{
    if (Head == NULL && Tail == NULL) //Fallet tom lista
    {
        Head = NewNode;
        Tail = NewNode;
    }
    else  //Icke-tom
    {
        NewNode->prev = Tail;
        Tail->next = NewNode;

        Tail = NewNode;
    }
}



My feeble attempt of user input:
 case 'A':{
                CDNode *Node = new CDNode;
                Node->prev = NULL;
                Node->next = NULL;
                if (Head == NULL && Tail == NULL)
                {
                    Node->ID = 1;
                }
                //cout << Node->ID;
                else
                {
                    Node->ID = Node->prev->ID + 1;
                }

                cout << "Enter Title: ";
                char title[80];
                cin.getline(title, 80);
                strcpy(Node->titel, title);

                cout << endl << "Enter Artist: ";
                char Artist[80];
                cin.getline(Artist, 80);
                strcpy(Node->artist, Artist);

                cout << endl << "Enter Tracks: ";
                cin >> Node->antalspr;

                cout << endl << "Enter Length: ";
                cin >> Node->speltid;

                laggtill(Node);
                //Kolla Node->prev->ID if =0 etc...
                break;
                    }



Is This A Good Question/Topic? 0
  • +

Replies To: Add node to linked list by user input

#2 nuclearfroggy  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 82
  • View blog
  • Posts: 167
  • Joined: 04-August 08

Re: Add node to linked list by user input

Posted 18 July 2012 - 02:53 AM

First off, it helps if you post a complete, compilable program, because it means we can straight away get testing it. :)

Anyway, the problem is an exception being thrown here (line 12 of the user input code):
else
{
    Node->ID = Node->prev->ID + 1;
} 
This is because Node is newly allocated, and so Node->prev is NULL. Because Node->prev is NULL it's hopefully clear you can't access Node->prev->ID. Before you set Node->ID you need to find the right position for the new node and link it up. I'm guessing that you're adding the nodes to the end of the list, if so, it's fairly painless to update the links. I don't want to give too much away, but hopefully you can see the problem now.

If you still don't get it I can explain in more detail.
Was This Post Helpful? 1
  • +
  • -

#3 koldrakan  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 11
  • Joined: 16-April 09

Re: Add node to linked list by user input

Posted 18 July 2012 - 04:01 AM

Thank you for a very good answer! As I am fairly new to linked lists I didn't quite understand all of it, but I gave it a try :) I have edited my code so that the new node is added to the list before I try to set the ID. It still crashes though :)

As requested, here is the code, complete this time :)

#include <iostream>
#include <sstream>
#include <cstring>
#include <cstdlib>

using namespace std;

struct CDNode
{
    int ID; //För att hålla koll på noderna

    CDNode *next;
    CDNode *prev;

    char titel[80];
    char artist[80];
    int speltid, antalspr;
};

CDNode *Head = NULL;
CDNode *Tail = NULL;

void laggtill(CDNode *NewNode)
{
    if (Head == NULL && Tail == NULL) //Fallet tom lista
    {
        Head = NewNode;
        Tail = NewNode;
    }
    else  //Icke-tom
    {
        NewNode->prev = Tail;
        Tail->next = NewNode;

        Tail = NewNode;
    }
}
void raderaNod(int ID)
{
    CDNode *Temp = Head;

    if (Head == NULL)
    {
        return;
    }
    while (Temp != NULL && Temp->ID != ID)
    {
        Temp = Temp->next;
    }
    if (Temp == NULL)
    {
        return;
    }
    if (Head == Tail)
    {
        delete Head;

        Head = NULL;
        Tail = NULL;
    }
    else if (Temp == Head)
    {
        Head = Head->next;
        delete Temp;
    }
    else if (Head == Tail)
    {
        Temp->prev->next = NULL;
        Tail = Temp->prev;
        delete Temp;
    }
    else
    {
        Temp->prev->next = Temp->next;
        Temp->next->prev = Temp->prev;
        delete Temp;
    }
}
void printList()
{
    CDNode *Temp = Head;

    while (Temp != NULL)
    {
        cout << "------------------ Album " << Temp->ID << " --------------------";
        cout << "Title: " << Temp->titel << endl;
        cout << "Artist: " << Temp->artist << endl;
        cout << "Tracks: " << Temp->antalspr << endl;
        cout << "Play Time: " << Temp->speltid << endl;

        Temp = Temp->next;
    }
}
void dispmenu()
{
    cout << "Press \"L\" to load from file." << endl;
    cout << "Press \"S\" to save to file;" << endl;
    cout << "Press \"A\" to add an album." << endl;
    cout << "Press \"P\" to print the list." << endl;
    cout << "Press \"D\" to delete an album." << endl;
    cout << "Press \"Q\" to quit." << endl;
    cout << "Choice: ";
}

int main()
{
    int go = 1;
    while (go==1)
    {
        char choice;
       /* CDNode *Node = new CDNode;
        Node->prev = NULL;
        Node->next = NULL;
        Node->ID = 0;
        laggtill(Node);
    */
        cout << "Please make a choice: ";
        dispmenu();
        cin >> choice;

        switch (choice)
        {
            case 'l':
            case 'L':
                break;
            case 's':
            case 'S':
                break;
            case 'a':
            case 'A':{
                CDNode *Node = new CDNode;
                Node->prev = NULL;
                Node->next = NULL;

                cout << endl << "Enter Title: ";
                char title[80];
                cin.getline(title, 80);
                strcpy(Node->titel, title);

                cout << endl << "Enter Artist: ";
                char Artist[80];
                cin.getline(Artist, 80);
                strcpy(Node->artist, Artist);

                cout << endl << "Enter Tracks: ";
                cin >> Node->antalspr;

                cout << endl << "Enter Length: ";
                cin >> Node->speltid;
                laggtill(Node);
                if (Head == NULL && Tail == NULL)
                {
                    Node->ID = 1;
                }
                //cout << Node->ID;
                else
                {
                    Node->ID = Node->prev->ID + 1;
                }
                //Kolla Node->prev->ID if =0 etc...
                break;
                    }
            case 'p':
            case 'P':
                printList();
                break;

            case 'd':
            case 'D':
                int nod;
                cout << "Which album (number) would you like to delete?: ";
                cin >> nod;
                raderaNod(nod);
                break;

            case 'q':
            case 'Q':
                return 0;

            default:
                break;
        }
    }


 /*   CDNode *nodTest = new CDNode();
    nodTest->ID = 1;
    nodTest->next = NULL;
    nodTest->prev = NULL;

    CDNode *nodTest2 = new CDNode();
    nodTest2->ID = 2;
    nodTest2->next = NULL;
    nodTest2->prev = NULL;

    cout << "Enter Title: ";
    char title[80];
    cin.getline(title, 80);
    strcpy(nodTest->titel, title);

    cout << endl << "Enter Artist: ";
    char Artist[80];
    cin.getline(Artist, 80);
    strcpy(nodTest->artist, Artist);

    cout << endl << "Enter Tracks: ";
    cin >> nodTest->antalspr;

    cout << endl << "Enter Length: ";
    cin >> nodTest->speltid;

    laggtill(nodTest);

    printList();

*/
return 0;
}


Was This Post Helpful? 0
  • +
  • -

#4 nuclearfroggy  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 82
  • View blog
  • Posts: 167
  • Joined: 04-August 08

Re: Add node to linked list by user input

Posted 18 July 2012 - 04:15 AM

Ah thanks, there's still the same issue with trying to access members of a null pointer. This is because if head and tail will never be NULL by the time you reach that if-else clause. You update head and tail before you get there now. However, the updating of the links is spot on.

Here in pseudocode (not real code, but showing the structure) would be a simpler way of doing things.
if tail is NULL: // if list is empty
    Node->id = 1
else:
    Node->id = Tail->id + 1
laggtill(Node) // now update links 


Hope this helps.

EDIT: Sorry to contradict myself from earlier. Another way of doing it would be link up the node and then check instead to see if the list contains one thing. ie. replace the if with
if (Head == Tail)
   Node->id = 1;

This will also work. Often with programming if you understand what's going on there's a lot of different solutions to the same problem. :)

This post has been edited by nuclearfroggy: 18 July 2012 - 04:20 AM

Was This Post Helpful? 1
  • +
  • -

#5 koldrakan  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 11
  • Joined: 16-April 09

Re: Add node to linked list by user input

Posted 18 July 2012 - 04:25 AM

This solved my problem, thank you! :)

I have one more question: when I try to add an album, the code
 cout << endl << "Enter Title: ";
                char title[80];
                cin.getline(title, 80);
                strcpy(Node->titel, title);


is supposed to read the title from cin. However, it does not take any input and jumps to "Enter Artist" instead. I have tried to use getline(cin,...) and cin <<, but it does not behave the way I want it to. It is strange, because I copied this code from another assignment where it worked just fine.
Was This Post Helpful? 0
  • +
  • -

#6 nuclearfroggy  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 82
  • View blog
  • Posts: 167
  • Joined: 04-August 08

Re: Add node to linked list by user input

Posted 18 July 2012 - 04:43 AM

Welcome to the slightly frustrating world of C++ console input. The reason for the problem is because "cin >>" will read the input but stops as soon as it reaches whitespace (spaces, newlines '\n', so on) and leave it there. So when you seemingly type in the character you've now left a '\n' (newline character) in the stream.

When you then call getline() the first thing it encounters is the newline. This tells it to stop, before it even read anything. But now the newline is discarded so the next getline() works okay.

The solution in this instance is probably to not mix cin and getline. You might as well use getline() for the single character as well. You could read the line into a buffer (just a string) and then only use the first non-whitespace character (use a for loop to go through the string and find it).

Characters left in the stream can be a nuisance. cin.ignore() is useful for getting rid of left over characters. You'll should include <limits> and then use cin.ignore(numeric_limits<streamsize>::max()) which basically makes sure there's no possibility of something being left in the stream.

I did a tutorial here that is a summary for all input methods. If you need a bit more of a reference try it.

Sorry if this seems like overkill for such a small thing. Console input in C++ is a bit inconsistent and confusing so I think it's better to clear up issues earlier.

EDIT: Also, since you're programming in C++ rather than C, I'd recommend looking at the string class.

This post has been edited by nuclearfroggy: 18 July 2012 - 04:52 AM

Was This Post Helpful? 3
  • +
  • -

#7 koldrakan  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 11
  • Joined: 16-April 09

Re: Add node to linked list by user input

Posted 18 July 2012 - 06:52 AM

Putting a "cin.ignore()" at the beginning of the "Add" case solved the problem! Thank you :)
Was This Post Helpful? 0
  • +
  • -

#8 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5643
  • View blog
  • Posts: 12,359
  • Joined: 16-October 07

Re: Add node to linked list by user input

Posted 18 July 2012 - 06:57 AM

Globals are bad.

Also, you'd have an easier time if your payload was separate from the node. e.g.
struct Data {
	char title[80], artist[80];
	int speltid, antalspr;
};

struct CDNode {
	int ID;
	Data data;
	CDNode *prev, *next;
	CDNode(int id, const Data &d, CDNode *p) : ID(id), data(d), prev(p), next(NULL) { }
};

struct List {
	CDNode *head, *tail;
	int lastId;
	List() : lastId(0), data(d), prev(NULL), next(NULL) { }
};


bool isEmpty(const List &list) { return list.head==NULL; }

void laggtill(List &list, const Data &data) {
	if (isEmpty(list)) {
		list.head = list.tail = new CDNode(++list.lastId, data, NULL);
	} else {
		list.tail = new CDNode(++list.lastId, data, list.tail);
		list.tail->prev->next = list.tail;
	}
}

//...
// put this in a function!
case 'A':{
	Data data;
    cout << endl << "Enter Title: ";
    cin.getline(data.title, sizeof(data.title)-1);

    cout << endl << "Enter Artist: ";
    cin.getline(data.artist, sizeof(data.artist)-1);

    cout << endl << "Enter Tracks: ";
    cin >> data.antalspr;

    cout << endl << "Enter Length: ";
    cin >> data.speltid;
    laggtill(list, data);
    break;



Hope this helps.
Was This Post Helpful? 0
  • +
  • -

#9 vividexstance  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 630
  • View blog
  • Posts: 2,107
  • Joined: 31-December 10

Re: Add node to linked list by user input

Posted 18 July 2012 - 07:58 AM

baavgai you have almost 4,000 posts, yet you still just give people code instead of explaining things in English or pseudo-code.

Also, in the code you posted, where are the nodes deallocated? I see you're dynamically allocating nodes on lines 24 and 26 but nowhere do you delete any of the nodes.

This post has been edited by vividexstance: 18 July 2012 - 07:58 AM

Was This Post Helpful? 0
  • +
  • -

#10 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5643
  • View blog
  • Posts: 12,359
  • Joined: 16-October 07

Re: Add node to linked list by user input

Posted 18 July 2012 - 08:17 AM

The code is nothing beyond what's already present. The change I offered was passing a List instance as opposed to using a global variable and using a payload. I also introduced constructors.

I could talk around what I'd like to show, but that would be confusing and probably counter productive. I don't feel I've given an answer or offered a solution the OP didn't already have. I'd think after 1000 posts you'd understand this. :P

View Postvividexstance, on 18 July 2012 - 10:58 AM, said:

Also, in the code you posted, where are the nodes deallocated?


As I tell the new kids, it's only partial code. The list object is neither constructed to destroyed in the example given.
Was This Post Helpful? 0
  • +
  • -

#11 vividexstance  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 630
  • View blog
  • Posts: 2,107
  • Joined: 31-December 10

Re: Add node to linked list by user input

Posted 18 July 2012 - 08:22 AM

I can be sarcastic too but I'm not going to be. I only posted because I see you do this sort of thing all the time and it goes against what is stated in the rules. Sometimes you put a lot of comments in the code, and I usually don't mind this. But when you really don't offer much of an explanation it's not really helping the OP. Why not just explain or give a suggestion in play old English and if code is really necessary, how about an example that can explain the problem and solution but that's not really related to the OP's original code?

This post has been edited by vividexstance: 18 July 2012 - 08:22 AM

Was This Post Helpful? 0
  • +
  • -

#12 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5643
  • View blog
  • Posts: 12,359
  • Joined: 16-October 07

Re: Add node to linked list by user input

Posted 18 July 2012 - 08:51 AM

Code is an explanation...

Posts are personal. The OP reveals their level of understanding, consciously or not, in what they offer. I do attempt to work with that. I post code littered with comments when I feel it will benefit the OP. In most cases, I try to post code slightly more advanced than the OP in hope it will show them something or inspire them to ask more questions.

I am sorry that my style of help doesn't conform to your standards. Please feel free to offer your own. Perhaps as an alternative to criticizing the help of others. Particularly when it has nothing to do with the OP's question.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1