linked list problem (with insert)

Question

The problem appears with the insert function that I wrote. 3 conditions must work, I tested b/w 1 and 2, b/w 2 and 3 and as last element, they worked.

---

EDIT; It was my own problem. I did not realize I put MAXINPUT = 3 (instead of 4). I do appreciate all the efforts to help me becoming a better programmer, using more advance and more concise features of C++.

Basically, the problem has been solved.

---

(codes removed)

Since this is a homework I'd saved this. If you need this original code for reference, please contact me at [email protected]

I am always available via e-mail.

Answer 1

step one should be to make the list into an object instead of just keeping a bunch of pointers around in main(). you want an object called List that knows about it's own first (and maybe last) elements. it should also have methods like List.append() and List.insert().

your current code is nigh unreadable.

Answer 2

Use a std::list, unless this is homework, in which case it needs tagging as such.

Answer 3

Your code works fine on my machine (once the insert(()) statement is "filled in" properly as explained in the code comment). The insertion works in all positions.

---

Something else, though: I initially had a look at your insert function. I thought I'd give you a hint on how to make it a little shorter and easier to understand what's going on:

void insert(List *last)
{
    // create a new item and populate it:
    List* new_item = new List;
    populate(new_item);

    // insert it between 'last' and the item succeeding 'last':
    new_item->nextAddr = last->nextAddr;
    last->nextAddr = new_item;
}

This would be preferable because it first creates a new, separate item, prepare it for insertion, and only then, when this has worked successfully, will the function "mess" with the linked list. That is, the linked list is not affected except in the very last statement, making your function "safer". Contrast this with your version of insert, where you mix code for constructing the new item with the actual insertion. If something goes wrong inside this function, chances are far higher that the linked list is messed up, too.

(What's still missing btw. is a initial check whether the passed argument last is actually valid, ie. not a null pointer.)

---

P.S.: Of course you could just use a standard C++ std::list container instead of building your own linked list, but seeing that you tagged your question beginner, I assume you want to learn how it actually works.

Answer 4

In my experience, I have learned to start small and test, then build up. I'll guide you through these steps.

BTW, a linked list is a container of nodes. So we'll start with the node class first.

Minimally, a node must have a pointer to another node:

#include <iostream>
#include <cstdlib> // for EXIT_SUCCESS
#include <string>

using std::cout;
using std::endl;
using std::cerr;
using std::cin;
using std::string;

struct Node
{
  // Add a default constructor to set pointer to null.
  Node()
  : p_next(NULL)
  { ; }

  Node * p_next;
};

// And the testing framework
int main(void)
{
  Node *  p_list_start(NULL);

  // Allocate first node.
  p_list_start = new Node;

  // Test the allocation.
  // ALWAYS test dynamic allocation for success.
  if (!p_list_start)
  {
    cerr << "Error allocating memory for first node." << endl;
    return EXIT_FAILURE;
  }

  // Validate the constructor
  ASSERT(p_list_start->p_next == 0);

  // Announce to user that test is successful.
  cout << "Test successful." << endl;

  // Delete the allocated object.
  delete p_list_start;

  // Pause if necessary.
  cin.ignore(100000, '\n'); // Ignore input chars until limit of 100,000 or '\n'

  return EXIT_SUCCESS;
}

Compile, and run this simple test. Fix errors until it runs correctly.

Next, modify the tester to link two nodes:

int main(void) { Node * p_list_start(NULL); Node * p_node(NULL); // <-- This is a new statement for the 2nd node. //...

  // Validate the constructor
  ASSERT(p_list_start->p_next == 0);

  // Allocate a second node.
  p_node = new Node;
  if (!p_node)
  {
      cerr << "Error allocating memory for 2nd node." << endl;

      // Remember to delete the previously allocated objects here.
      delete p_list start;

      return EXIT_FAILURE;
  }

  // Link the first node to the second.
  p_list_start->Link_To(p_node);

  // Test the link
  ASSERT(p_list_start.p_next == &p_node);

  //...

  // Delete the allocated object(s)
  delete p_list_start;
  delete p_node;

  //...

}

Compile with the modifications.
It failed to compile, undefined method: Node::Link_To
Not to worry, this is expected. Show us the compiler is working. :-)

Add the Link_To method to the Node structure:

struct Node
{
  // ...
  void Link_To(const Node& n)
  {
     p_next = &n;
     return;
  }
  //...
};

Compile and run. Test should pass.

At this point the linking process has been validated. Onto adding content to the node.

Since the Node object has been tested, we don't want to touch it. So let's inherit from it to create a node with content:

struct Name_Node
: public Node  // Inherit from the tested object.
{      
    std::string  name;
    std::string  phone;
};

If you haven't learned inheritance yet, you can append to the existing node:

struct Node
{
  //...
  std::string  name;
  std::string  phone;
}

At this point you can add functions for setting and displaying content. Add the testing statements. Run and validate.

The next step would be to create two content nodes and link them together. As you build up, keep the testing code. Also, if stuff works you may want to put the functionality into separate functions.

For more information on this process, check out Test Driven Development.