Thread: Linked list recursion exercise Chapter 16 problem 3

  1. #1
    Registered User
    Join Date
    Jun 2017
    Posts
    2

    Linked list recursion exercise Chapter 16 problem 3

    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.


    Code:
    #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;
    }

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,736
    A recursive removal looks something like this
    Code:
    // empty list
    if ( head == NULL ) return NULL;
    
    if ( head->something == something ) {
      // current head node is the one to delete, so delete it
      // and return the tail
      tail = head->next;
      delete head;
      return tail;
    } else {
      // recurse: try and remove from the sub-list starting
      // at the next node.
      head->next = remove(head->next,something);
      return head;
    }
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Jun 2017
    Posts
    2
    If I understand your code snipped correctly, it still removes one and only one element from the list at a time, so that's what the exercise requested.
    I've seen some implementations where the elements were removed recursively from the start of something to the end and it made me wonder what was the correct approach to tackle this exercise.
    Thank you for clearing it up!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 1
    Last Post: 04-19-2016, 06:55 AM
  2. Jumping into C++ Chapter 14, exercise 6.
    By CppProgrammer88 in forum C++ Programming
    Replies: 5
    Last Post: 04-12-2016, 07:27 PM
  3. Alex's exercise Chapter 6 Ex3
    By Valentas in forum C++ Programming
    Replies: 3
    Last Post: 01-25-2013, 10:55 AM

Tags for this Thread