min and max element is list

[anup30]

thank you keskiverto and ne555 for the info.
for me its much simpler to write max_value() function in the struct to find max value, than linking *max_element() to my struct.

#include <iostream>
using namespace std;

struct st{
	int k=0;
	st *next= nullptr;
	int max_value(){		
		st *p=this, *q=this->next;
		int n= this->k;
		do{
			if(p->k >n)	n=p->k;	
			p=q;
			q=q->next;
		}while(p->next);
		return n;
	}	
};

int main(){
	int ar[5]={1,2,4,3,2};
	st *head= new st;
	st *temp= head;
	for(int i=0; i<5; i++){
		temp->k=ar[i];
		temp->next= new st;
		temp= temp->next;
	}
	
	temp=head;
	cout<< "all elements= ";
	do{
		cout<< temp->k << ", ";
		temp= temp->next;
	}while(temp->next);	
	cout << endl;	
	
	cout<< "max value= " << head->max_value() << endl;
		
	temp=head->next; 
	do{		
		delete head;
		head=temp;
		temp=temp->next;
	}while(temp);	
	delete head;
 	
return 0;
}

although the extra 1 element at the need to be fixed

[JLBorges]

#include <iostream>
#include <algorithm>

struct st {

    int k = 0;
    st *next = nullptr;

    int max_value() const {	// *** const

        if( next == nullptr ) return k ;
        else return( std::max( k, next->max_value() ) ) ;
    }

    void print() const {

        std::cout << k << ' ' ;
        if(next) next->print() ;
    }
};

int main() {

    // best to avoid dynamic memory allocation if possible
    // note: member next is default initialised to nullptr
    st ar[] = { {1}, {9}, {4}, {5}, {8}, {6}, {3}, {7}, {2} } ;
    const int N = sizeof(ar) / sizeof( ar[0] ) ;

    for( int i = 0; i<(N-1); ++i ) ar[i].next = ar+i+1 ; // link them up, in order

    for( int i = 0 ; i < N ; ++i ) {

        std::cout << "sequence  [ " ;
        ar[i].print() ;
        std::cout << "]  max: " << ar[i].max_value() << '\n' ;
    }
}

http://coliru.stacked-crooked.com/a/5191a662adaaf0a2

[anup30]

@_JLBorges, your ar variable is fixed size.
linked list is useless without dynamic memory(?).
in your code ar has 9 elements. they are like 9 heads comparing to my code. if we want to add more values we can add below any of the head by dynamic memory (then it will look like 2d array). but not on right side of last element, 2.

[JLBorges]

It was just the simplest code required to test the max_value() function.


> if we want to add more values

Technically, it is possible to add elements to the list, even if dynamic memory is not used.

For example:

#include <iostream>
#include <algorithm>
#include <memory>

struct st {

    int k = 0 ;
    st *next = nullptr ;

    int max_value() const {	// *** const

        if( next == nullptr ) return k ;
        else return( std::max( k, next->max_value() ) ) ;
    }

    void print() const {

        std::cout << k << ' ' ;
        if(next) next->print() ;
    }
};

int main() {

    // avoid dynamic memory allocation
    // note: member next is default initialised to nullptr
    st ar[] = { {1}, {9}, {4}, {5}, {8}, {6}, {3}, {7}, {2} } ;
    const int N = sizeof(ar) / sizeof( ar[0] ) ;

    for( int i = 0; i<(N-1); ++i ) ar[i].next = ar+i+1 ; // link them up, in order

    // add two new items, say -5 and -2, at the back
    st new_items[] { {-5}, {-2} } ;
    ar[N-1].next = new_items ;
    new_items[0].next = new_items + 1 ;

    // add a new items, say 12 at the front
    st first_item = { 12, ar } ;

    // remove the two items at ar[3] and ar[4] (5 and 8) from the middle
    ar[2].next = ar+5 ;

    for( st* ptr = &first_item ; ptr != nullptr ; ptr = ptr->next  ) {

        std::cout << "sequence ==  [ " ;
        ptr->print() ;
        std::cout << "]  max == " << ptr->max_value() << '\n' ;
    }
}

http://coliru.stacked-crooked.com/a/e2373dc551ad4dad

[anup30]

can we call your max_value() function at line 10-14 recursive? each call goes to max_value() function of its 'child'.

[JLBorges]

Yes. Both max_value() and print() are recursive.