How can I use iteration instead of recursion to input values into a linked list?

Question

Ok so let's say we have a linked list of characters with a head pointer. How can I create a loop to enter a string of characters into the linked list? My problem is when I think of head and head->next and head->next->next . . . it only seems natural to use a recursive function to set the characters at each node.

Answer 1

It's trivial to do it with iteration. You would just start at head, and use a loop to iterate over the list by doing current = current->next, until you hit a NULL.

Basically something like:

node* n = head;
while (n) {
   // ... do something with n
   n = n->next;
}

Answer 2

Assuming your linked list already has enough space in it:

node *n = head;
char *input = "hello list";
int len = strlen(input);
for (int i=0;i<len;i++)
{
  n->data = input[i];
  n=n->next;
}

Otherwise you need to check each time for a null value before adding the data:

node *n = head;
char *input = "hello list";
int len = strlen(input);
for (int i=0;i<len;i++)
{
  if !(n)
  {
    break;
  }
  n->data = input[i];
  n=n->next;
}

Another solution would involve adding a new element when you hit the end:

node *n = head;
char *input = "hello list";
int len = strlen(input);
for (int i=0;i<len;i++)
{
  n->data = input[i];
  if (!n->next && i < len-1)
  {
    n->next = new Node;
  }
  n = n->next;
}

Answer 3

As you are using C++, then using std::list and an iterator would seem to be the way to go. Writing your own linked list is OK as a learning exercise, but please don't use such a thing in real code.

Answer 4

First, it depends on whether it's a doubly-linked list, or a singly linked list -- but it sounds like you're dealing with a singly-linked list.

With a singly linked list it's easiest to add nodes to the beginning of the list. If that works for you, something like:

node *head;    // head of the list

// insert node:
new_node->next = head;
head = new_node;

If you want to add to the end of the list, you walk through the list first:

// If the list is empty, just add the node at the head:
if (head == NULL) {  
   new_node->next = head;
   head = new_node;
}
else {
   // There's already data in the list, so walk to the end of the list:
   node *pos;
   for (pos=head; pos->next!=NULL; pos=pos->next)
     ;
  new_node->next = NULL;
  pos->next = new_node;
}

As a general rule, neither of these makes a lot of sense though. It's only really sensible to use a linked list when you plan on doing insertions and deletions somewhere in the middle of the list, and you normally save the position (i.e. a pointer to) where you're going to do the insertion or deletion.