TransWikia.com

Singly linked List Find max,min

Stack Overflow Asked by Lizzar_00 on November 4, 2021

**This is a singly linked list and the professor wants me 2 find max min from define limit of singly list list ( similar 2 find array but use singly linked list instead ) however when i want 2 remove the number in singly linked list even if i’m not finish with it it get struck here is my code thank you for the contribution i’m a newbie and i don’t know many things just a university student. and the number before menu is how many numbers that singly linked list can hold **

# include<bits/stdc++.h>
using namespace std;
class Node
{
public:
    int n; 
    Node*next;
};
bool isEmpty(Node*head)
{
    if (head==NULL)return true;
    else return false;
}
char menu()
{
    char choice;
    cout<<"Menun";
    cout<<"1.Add an item.n";
    cout<<"2.Remove an item.n";
    cout<<"3.Show The List.n";
    cout<<"4.Exit.n";
    cin>>choice;
    return choice;
}
void insert(Node*&head,Node*&last,int n) 
{
    Node*node = new Node(); // allocate memory 2 node let node be an abstract data
    node->n = n; // define data in the new node as new data (saving data define in there)
    node->next = NULL; // Let next of the new node as head
    head = node; // let pointer name head point new node
    last = node;
}
void append(Node*&head,Node*&last,int n)
{ 
    if(isEmpty(head)) insert(head,last,n);
    else
    {  
    Node*node = new Node(); // allocate memory 2 node let node be abstract data
    node->n = n; // define data in the new node as new data (saving data define in there)
    node->next = NULL; // This new node is going to be the last node, so make next of it as NULL
    last->next = node; // Change the next of last node
    last = node;
    }
}
void remove(Node*&head,Node*&last)
{
    if(isEmpty(head))cout<<"The List is Empty.n";
    else if (head==last)
    {
        delete head;
        head == NULL;
        last == NULL;
    }
    else
    {
        Node *node=head;
        head =head->next;
        delete node;
    }
}
void print(Node*node) // Function Prints Content of the singly linked list
{ 
    if(isEmpty(node))cout<<"The list is emptyn";
    else
    {
    cout << "The List contains: n";
    while (node!= NULL) 
    { 
        cout<<node->n<<endl; 
        node = node->next; 
    }
    }
} 
int main()
{
    Node* head = NULL; // Start with empty List
    Node* last = NULL;
    char choice;int i,n,x;
    cin>>x;
    for(i=0;i<x;i++)
    {
    choice = menu();
    switch(choice)
    {
        case '1': cout<<"Please enter a number: ";
                  cin>>n;
                  append(head,last,n);
                  break;
        case '2': remove(head,last);
                  break;
        case '3': print(head);
                  break;
        default: cout<< "System exitn";
    } 
    } while(choice!='4'); return 0;
}

**Reality Output :
3 ( This is the number of data that singly-linked list can hold)
Menu

  1. Add an item.
  2. Remove an item.
  3. Show the List.
  4. Exit.
    1
    Please enter a number: 22
    Menu
  5. Add an item.
  6. Remove an item
  7. Show The List.
  8. Exit.
    1
    Please enter a number: 12
    Menu
  9. Add an item.
  10. Remove an item
  11. Show The List.
  12. Exit.
    2
  • ( THE CURSOR COULDN’T DO ANYTHING ONLY BLINK ON THE BLANK BLACK OUTPUT)
    Expected Output
    3
    Menu
  1. Add an item.
  2. Remove an item.
  3. Show the List.
  4. Exit.
    1
    Please enter a number: 22
    Menu
  5. Add an item.
  6. Remove an item
  7. Show The List.
  8. Exit.
    1
    Please enter a number: 12
    Menu
  9. Add an item.
  10. Remove an item
  11. Show The List.
  12. Exit.
    2
    Menu
  13. Add an item.
  14. Remove an item
  15. Show The List.
  16. Exit.
    3
    The List contains
    12
    Menu
  17. Add an item.
  18. Remove an item
  19. Show The List.
  20. Exit.
    1
    Please enter a number: 22
    Menu
  21. Add an item.
  22. Remove an item
  23. Show The List.
  24. Exit.
    1
    Please enter a number: 34
    Menu
  25. Add an item.
  26. Remove an item
  27. Show The List.
  28. Exit.
    3
    The List contains
    12
    22
    34
    Max = 34 Min = 12

P.S. I’M THANK U EVERYONE WHO COMES ANSWER ON THIS QUESTION BECAUSE I TRY WITH THIS QUESTION FOR 2 DAYS
THIS 1 IS HEAVY FOR ME

2 Answers

For starters there is no great sense to declare the class Node

class Node
{
public:
    int n; 
    Node*next;
};

making all its data members public and then define stand-alone functions instead of defining class member functions.

The class Node should be an internal class of the class List that contains two pointers to the beginning and the end of the list because you are trying to define a two-sided singly-linked list.

Something like

class List
{
private:
    struct Node
    {
        int value;
        Node *next;
    } *head = nullptr, *tail = nullptr;

public:
    List() = default;
    List( const List & ) = delete;
    List & operator =( const List & ) = delete;
    
    void push_front( int value )
    {
        head = new Node { value, head };
        if ( !tail ) tail = head;
    }
    
    void push_back( int value )
    {
        Node *new_node = new Node { value, nullptr };
        
        if ( tail )
        {
            tail = tail->next = new_node;
        }
        else
        {
            head = tail = new_node;
        }
    }
    
    bool empty() const { return head == nullptr; }
    
    void pop_front()
    {
        if ( head )
        {
            delete std::exchange( head, head->next );
            if ( !head ) tail = nullptr;
        }
    }

    // and so on.
};

The function insert as it is written also does not make sense because it ignores the fact that the list can contain already nodes due to these statements.

node->next = NULL; // Let next of the new node as head
head = node; // let pointer name head point new node
last = node;

It would be better to write a function named like push_front that could be defined like

void push_front( Node * &head, Node * &last, int n ) 
{
    head = new Node { n, head };

    if ( !last )
    {
        last = head;
    }
}

It is better to rename the function append as push_back. The function can look like

void push_back( Node * &head, Node * &last, int n )
{ 
    if ( isEmpty( head ) ) 
    {
        push_front( head, last, n );
    }
    else
    {
        last = last->next = new Node { n, nullptr };  
    }
}

The function remove behaves as a function pop_front. So rename it The function shall not output any message. It is the user of the function should decide whether to output any message. The function has several bugs.

For starters it uses the comparison operator instead of the assignment operator

    head == NULL;
    last == NULL;

If the list contains only one node that is deleted then the function forgets to set the pointer last to nullptr.

else
{
    Node *node=head;
    head =head->next;
    delete node;
}

The function can be defined the following way

bool pop_front( Node * &head, Node * &last )
{
    bool success = not isEmpty( head );

    if ( success )
    {
        Node *node = head;
        head = head->next;
   
        delete node;

        if ( !head ) last = head;
    }

    return success;
}

In main this construction

for(i=0;i<x;i++)
{
    //...
} while(choice!='4'); return 0;

is incorrect. There is no any sense to use the for loop Use the do while loop like

do
{
    //...
} while(choice!='4'); 

return 0;

The statement under the label default does not make sense

default: cout<< "System exitn"

It is better to write for example

default: 
    cout<< "Incorrect choice. Try again.n";
    break;

Answered by Vlad from Moscow on November 4, 2021

First error

    delete head;
    head == NULL;
    last == NULL;

should be

    delete head;
    head = NULL;
    last = NULL;

Use == for comparison, use = for assignment.

Your compiler really should warn you that a statement like head == NULL; achieves nothing. So either you need to pay attention to the wanrings that you compiler is giving (you should change your code until there are no compiler warnings) or if the compiler isn't warning you then you aren't using your compiler correctly. All compilers have options that cause them to give warnings for dubious code like this. If your compiler isn't warning you about this kind of code then you should take the time to find out how to make it so it does. Better to do that than waste two days trying to fix problems that the compiler could have told you about.

Second error has nothing to do with lists. Your loops in main are incorrect. You can see these better if you indent your code correctly. You should always do this, it saves time. Here's your code indented correctly.

cin>>x;
for(i=0;i<x;i++)
{
    choice = menu();
    switch(choice)
    {
    case '1': 
        cout<<"Please enter a number: ";
        cin>>n;
        append(head,last,n);
        break;
    case '2':
        remove(head,last);
        break;
    case '3':
        print(head);
        break;
    default:
        cout<< "System exitn";
    } 
}
while(choice!='4');

Now look at that while loop at the end. It looks like it is ending the for loop above, but there's no such thing as a for ... while loop. Instead that's a completely separate loop to the preceding for loop. It just loops for ever (because choice does not equal '4' and the loop never changes anything). That's why your code seems to freeze. Here's what your code should look like.

do
{
    choice = menu();
    switch(choice)
    {
    case '1': 
        cout<<"Please enter a number: ";
        cin>>n;
        append(head,last,n);
        break;
    case '2':
        remove(head,last);
        break;
    case '3':
        print(head);
        break;
    default:
        cout<< "System exitn";
    } 
}
while(choice!='4');

I changed the two loops (for followed by while) into one do ... while loop and I got rid of the x variable which served no purpose. I guess you meant to write a do ... while loop all along but got confused about the syntax.

Overall the code is pretty good. You seem to understand pointers better than many newbies. The second error in particular was quite unusual and hard to spot. You should probably look into learning how to use a debugger. Bugs like this are easy to find with a debugger.

Answered by john on November 4, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP