Why is this C++ linked list program terminating?

Question

Summary Report

Thanks for all the helpful feedback. cin.clear() was very helfpul; so was the remark about setting next to NULL. But the final problem (as diagnosed in the comments) was that I was using Ctrl+D to escape, and cin >> k wasn't handling this correctly. When I added k > 0 into the while condition (see updated code) and escaped with a negative number, it all started working.

---

I hate to post large amounts of code, but I don't think I can trim this any further. The point is that my program works the first go-around, but not the second. (Skip to main to see what I mean.)

#include <iostream>
using namespace std;

struct ListNode {
  int data;
  ListNode* next;
};

void print_list(ListNode* node) {
  cout << node->data << endl;
  while ((node = node->next) != NULL) {
    cout << node->data << endl;
  }
}

ListNode* read_list() {
  ListNode *head, *tail;
  int k;

  head = NULL;
  while ((cin >> k) && k > 0) {
       if (head == NULL) {
          head = tail = new ListNode;
       } else {
          tail->next = new ListNode;
          tail = tail->next;
       }
       tail->data = k;
       tail->next = NULL;
  }
  return head;
}

int main() {
  ListNode *list1, *list2;

  list1 = read_list();
  print_list(list1);    // Works

  list2 = read_list();
  print_list(list2);    // Does not work!

  return 0;
}

And then here is the output:

Press ENTER or type command to continue
1
3
5
7
List1
1
3
5
7
List2

Command terminated

Do you see how it terminates before printing List2? (The first four lines are from stdin. See main.) What is going wrong here? I don't understand why the same logic would work the first time, but not the second.

Perhaps it's because I am not freeing the memory for the first linked list?

Answer 1

There are multiple problems with this code.

1. You forgot to set next to NULL on the last element. This will cause a crash for any non-empty list.

2. You need std::cin.clear() before reading from it again. The EOF flag is "sticky".

3. The print_list() function doesn't handle empty lists. This will crash for any empty list.

Any one of these problems will cause your program to terminate or crash, so you have to fix all of them. Note how one error makes the program crash for empty lists, and a different error causes a crash for non-empty lists -- between the two of them, the program crashes for all lists. Well, if you're lucky, at least. If you're unlucky it might not crash.

Here's a list of tools that would have automatically caught errors #1 and #3:

• GDB (run gdb ./a.out instead of ./a.out, remember to compile with -g)
• Mudflap (compile with -fmudflap -lmudflap)
• Valgrind (run valgrind ./a.out instead of ./a.out)
• Clang static analyzer

So, you should be using at least one of those four tools. I like to use all four on the same project.

Answer 2

You should call cin.clear() after the first read_list() . The reason can be found here.

The following code works well:

#include <iostream>                                                                                                                    
using namespace std;

struct ListNode {
  int data;
  ListNode* next;
};

void print_list(ListNode* node) {
  cout << node->data << endl;
  while ((node = node->next) != NULL) {
    cout << node->data << endl;
  }
}

ListNode* read_list() {
  ListNode *head, *tail;
  int k;

  head = NULL;
  while (cin >> k) {
       if (head == NULL) {
          head = tail = new ListNode;
       } else {
          tail->next = new ListNode;
          tail = tail->next;
       }
       tail->data = k;
       tail->next = NULL;
  }
  return head;
}

int main() {
  ListNode *list1, *list2;

  list1 = read_list();
  print_list(list1);
  cin.clear(); // ADD this line 

  list2 = read_list();
  print_list(list2);

  return 0;
}

The problem is caused by the cin in the second read_list() function call. The first read_list(), print_list() works well.

However, according to the debugger, no ListNode is created after return from the read_list(), the list2 is 0x0, that is NULL, which cause the second print_list() segmentation fault.

The reason why the 2nd read_list return NULL is because the while loop does not run. the value of statement cin >> k is false.

Additionally

The above answer is wrong. The problem is still there if simply modifying the read_list function like the following.

ListNode* read_list() {
  ListNode *head, *tail;
  int k;

  head = NULL;
  while (cin >> k) {
       if (head == NULL) {
          head = tail = new ListNode;
       } else {
          tail->next = new ListNode;
          tail = tail->next;
       }
       tail->data = k;
       tail->next = NULL;
  }
  return head;
}

Answer 3

head = NULL;
while (cin >> k) {
   if (head == NULL) {
      head = tail = new ListNode;
   } else {

I hope you see the problem. First you set the head to null and then check whether its null or not.

Try something like this:

ListNode* readList(ListNode* head)
{
    int data;
    cin >> data;

    ListNode* nNode = new ListNode;
    nNode->data = data;
    nNode->next = 0;

    if (head == null)
    {
        head = nNode;
    }
    else
    {
        ListNode* tail = head;
        while (tail->next != 0)
        {
            tail = tail->next;
        }
        tail->next = nNode;
    }

    return head;
}

Or something like this. Its been quite some time since I last created linkedlist.

Answer 4

Modify the way you printing the list:

void print_list(ListNode* node)
{
    while (node)
    {
        cout << node->data << endl;
        node = node->next;
    }
}

reset cin before second read_list:

cin.clear();
cin.ignore(numeric_limits<streamsize>::max(), '\n');

The program crashed will solve.