Thread: How to Add N number if nodes to a Linked List using iteration? (chap 16, exercise 3)

Hi,

I have a little program where you can add N number of nodes to a linked list, with values from 1 to N, and then it prints these values from 1 to N.

Then it asks you how much of the list you want to remove. You type in a number M, the program removes M nodes from the list, then it prints the all the numbers in the linked-list again.

Here's it:

Code:

#include <iostream>


using namespace std;


struct LinkedL
{
    int x;
    LinkedL* next;
};


// Adding using recursion

LinkedL* Add(LinkedL* head, int n, int o)
{
    LinkedL* node = new LinkedL;
    node->x = o-n+1;
    node->next = head;
    if(n > 1)
    {
        return Add(node, n-1, o);
    }
    else
    {
        return node;
    }
}


//the little help-function to add using iteration.

LinkedL* Add3(LinkedL* head, int n, int o)
{
    LinkedL* node = new LinkedL;
    node->x = o-n+1;
    node->next = head;
    return node;
}


// Adding to list using iteration

LinkedL* Add2(LinkedL* head, int n, int o)
{
    LinkedL* temp = NULL;
    do
    {
        head = Add3(head, n, o);
        n--;
    } while (n >= 1);
    return head;
}


// Printing the LinkedList using recursion

void print(LinkedL* head)
{
    LinkedL* cur = head;
    if(cur == NULL)
    {
        cout << "All nodes deleted.";
    }
    else
    {
        if(cur->next != NULL)
        {
            print(cur->next);
        }
        cout << cur->x << "\n";
    }
}


// Removing from list using recursion

LinkedL* removefromlist (LinkedL* head, LinkedL*cur, int m, int o)
{
    if (m > o)
    {
        m = o;
    }
    head = cur;
    cur = head->next;
    delete head;
    if (m > 1)
    {
        removefromlist(head, cur, m-1, o);
    }
    else
    {
        return cur;
    }
}


// Removing from list using iteration

LinkedL* removefromlist2 (LinkedL* head, LinkedL*cur, int m, int o)
{
    if (m > o)
    {
        m = o;
    }
    while (m >= 1)
    {
        head = cur;
        cur = head->next;
        delete head;
        m--;
    }
    return cur;


}


int main ()
{
    int n;
    cout << "Type in lenght of the list: ";
    cin >> n;
    LinkedL* head = NULL;
    int o = n;
    head = Add(head, n, o);
    print(head);


    int m;
    cout << "How much of the list from the last item you want to remove?";
    cin >> m;
    LinkedL* cur = head;
    head = removefromlist (head, cur, m, o);
    print(head);
    cin.ignore();
    cin.get();
}

The exercise 3 from chapter 16 is this: Write a recursive algorithm to remove elements from a linked list. Write a recursive algorithm to add elements into a linked list. Try writing the same algorithms using iteration. Do the recursive implementations or the iterative implementations feel more natural?

I can write algorithm for removing N elements from the linked list using both recursion and iteration. And I can write algorithm for adding N elements to a linked list using recursion and iteration too.

But adding N elements to a linked list, when writing the algorithm using iteration, I use two functions, where one is called inside the other. Add3 is used in Add2.

I wonder how can I write a function to add N nodes to a linked list using iteration, without calling to any other function?

Here's one of my attempts to write algorithm for adding N elements to a linked list using iteration;

Code:

LinkedL* Add2(LinkedL* head, int n, int o)
{
    LinkedL* temp = NULL;
    do
    {
        LinkedL* node = new LinkedL;
        node->x = o-n+1;
        node->next = head;
        head = node;
        n--;
    } while (n > 1);


    return temp;


}

When I run it, it only adds one node with node->x = 4.


I wonder how can I write a function to add N nodes to a linked list using iteration, without calling to any other function?