C++

Forum

 
 
Linked list recursion exercise

Icyblizz (9)
Exercise :
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?

My question is what it actually means to add/remove elements recursively?
It means that user can just insert/remove a piece of data and only that data can be added or removed, or it means if the user inputs a x number then the list should add/remove x number of that specific data type?

My implementation as it stands works with inserting/removing a single piece of data of a specific type.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
 
#include <iostream>
#include <iomanip>
#include <cstdlib>

template < typename T >
struct list
{

    list();
    void insert( T num );
    void remove( T num );
    void print();

private :

    void print( list *l );
    void insert( list *l, T num );
    void remove( list *l, T num );
    list *next;
    list *head;
    T id;

};

template < typename T >
list<T>::list() : next(), head(), id()
{ }

template < typename T >
void list<T>::insert( T num )
{
    if( !head )
    {
        head = new list;
        head->id = num;
        head->next = NULL;
    }
    else
        insert( head, num );
}

template < typename T >
void list<T>::insert( list *l, T num )
{
    if( l->next )
    {
        insert( l->next, num );
    }
    else
    {
        l->next = new list;
        l->next->id = num;
        l->next->next = NULL;
    }
}

template < typename T >
void list<T>::remove( T num )
{
    if( !head )
        return;
    else
    {
        if( !head->next && head->id == num )
        {
            delete head;
            head = NULL;
            return;
        }
        remove( head, num );
    }
}

template < typename T >
void list<T>::remove( list *l, T num )
{
    if( !l->next && l->id != num )
    {
        return;
    } //guard against invalid input
    if( l->next->id == num )
    {
        list *dst = l->next;
        list *nxt = dst->next;
        l->next = nxt;
        dst->next = NULL;
        delete dst;
    }
    else
        remove( l->next, num );
}

template < typename T >
void list<T>::print( )
{
    system("cls");
    std::cout<<"\n\n";
    if( head )
    {
        std::cout<<std::setw(10)<<head->id;
        if( head->next )
            print( head->next );
    }
    else
        std::cout<<std::setw(20)<<"List is empty";
    std::cout<<"\n\n";
    system("pause");
}

template < typename T >
void list<T>::print( list *l )
{
    std::cout<<std::setw(10)<<l->id;
    if( l->next )
        print( l->next );
}

//methods can be called in main

int main()
{
     list<short> *l = new list<short>();
     /*
     methods here
     l->insert(1);
     l->remove(1);
     l->print();
     */
     return 0;
}
Last edited on
ne555 (10692)
instructions unclear, do what you want.
You should differentiate the list from a node/cell of that list

> list<short> *l = new list<short>();
¿why?
http://www.cplusplus.com/forum/general/138037/#msg731921
Icyblizz (9)
@ne555

Seemed like a good way to practice my dynamic allocation,
guess I'll be using list<int> l; from now on.

Thank you for pointing it out!
Topic archived. No new replies allowed.