5
\$\begingroup\$

Are there any memory leaks in this linklist implementation.Also is the implementation correct?Can the time complexity be optimized?

#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;

struct node
{
int n;
node* point;
};

node* first=NULL;

void search(int n);
void insert(int n);
void del(int n);
void print();

void menu()
{
int s,n;
cout<<"Enter 1 to Search"<<endl;
cout<<"Enter 2 to Insert"<<endl;
cout<<"Enter 3 to Delete"<<endl;
cout<<"Enter 4 to Print"<<endl;
cout<<"Enter 5 to Exit"<<endl;

cin>>s;

switch(s)
{
    case 1: cout<<"Enter number to Search: ";
            cin>>n;
            search(n);
            break;

    case 2: cout<<"Enter number to Insert: ";
            cin>>n;
            insert(n);
            break;

    case 3: cout<<"Enter number to Delete: ";
            cin>>n;
            del(n);
            break;

    case 4: print();
            break;

    case 5: exit(0);

    default: cout<<"Wrong Input"<<endl<<endl<<endl;
}       
}

int main()
{
cout<<"Welcome to Linked List"<<endl;
while(1)
    menu();
}   

void search(int n)
{
node* ptr=first;

while(ptr!=NULL)
{
    if(ptr->n==n)
    {
        cout<<endl<<n<<" Found!"<<endl<<endl<<endl;
        return;
    }
    else
        ptr=ptr->point;

}

cout<<endl<<n<<" Not Found!"<<endl<<endl<<endl;
return;
}

void insert(int n)
{
node* prev=NULL;
node* next=first;

if(first!=NULL and first->n>n)
{
    first=new node;
    first->n=n;
    first->point=next;
    cout<<endl<<endl;
    return;
}

while(next!=NULL)
{
    if(next->n>n)
    {
        prev->point=new node;
        (prev->point)->n=n;
        (prev->point)->point=next;
        cout<<endl<<endl;
        return;
    }
    else
    {
        prev=next;
        next=next->point;
    }
}
    if(prev==NULL)
    {
        first=new node;
        first->n=n;
        first->point=NULL;
    }
    else
    {
        prev->point=new node;
        (prev->point)->n=n;
        (prev->point)->point=NULL;

    }
    cout<<endl<<endl;
    return;

}

void print()
{
node* next=first;

while(next!=NULL)
{
    cout<<next->n<<" ";
    next=next->point;
}
cout<<endl<<endl<<endl;
return;
}

void del(int n)
{
node* prev=NULL;
node* next=first;

while(next!=NULL)
{
    if(next->n==n)
    {
        if(prev!=NULL)
        {
            prev->point=next->point;
            delete next;
        }
        else
        {
            first=next->point;
            delete next;
        }
        cout<<n<<" Deleted!";
        cout<<endl<<endl;
        return;
    }
    else
    {
        prev=next;
        next=next->point;
    }
}       

cout<<"Number not in list"<<endl<<endl<<endl;
return;
}
\$\endgroup\$
  • 4
    \$\begingroup\$ Welcome to Code Review! It looks like you're unsure whether this code works. Please see the How To Ask section of the FAQ. Questions about whether code works or not are not in the scope of this site. \$\endgroup\$ – user1118321 Nov 25 '15 at 15:20
  • 1
    \$\begingroup\$ Try using valgrind if you're not on Windows. \$\endgroup\$ – nanny Nov 25 '15 at 15:40
  • 2
    \$\begingroup\$ First comment is that this is C not C++ \$\endgroup\$ – Martin York Nov 25 '15 at 20:56
  • 1
    \$\begingroup\$ Code compiles and seems to work as expected. Voting to re-open. \$\endgroup\$ – Martin York Nov 25 '15 at 21:01
  • \$\begingroup\$ @LokiAstari This is C++....I've just included the cstdlib and cstdio for the exit function to work. \$\endgroup\$ – CodeMaxx Nov 26 '15 at 7:57
11
\$\begingroup\$

It does not appear to be leaking memory (except on exit). However, there are a number of things you can do to improve this code.

Fix the formatting

Code that has poor formatting is hard to read, understand, and maintain. For that reason, you should strive to have nicely formatted code. In this case, that means fixing indentation and inserting whitespace. For instance, instead of this:

cout<<"Number not in list"<<endl<<endl<<endl;

write this:

cout << "Number not in list" << endl << endl << endl;

Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid.

Separate I/O from core routines

It's often better to have input and output operation in a single place (or a few select places) rather than having them scattered in several places. For this reason, I'd recommend having the search, insert and del routines simply be responsible for their corresponding linked list function and not print anything. Printing can be done instead in the calling routine if needed.

Use object orientation

Because you're writing in C++, it would make sense to have the methods that operate on a class (such as node) be member functions rather than separate functions. Objects and classes are one of the main strengths of C++ and something you should learn soon if you haven't already. Encapsulate related code in objects where it makes sense to do so.

Eliminate global variables

Eliminating global variables will make your code more readable and maintainable, both of which are important characteristics of well-written code. Global variables introduce messy linkages that are difficult to spot and error-prone. Global variables can be altered by literally any code, making it difficult to understand how they're being used, and making it all too easy to inadvertently create an inconsistent state. See "how bad are global variables?" for more. The variable first should instead be passed explicitly to each routine that needs it, or you can use an object as mentioned in the previous suggestion.

Return something useful from functions

All of your functions currently return void, but the code could be improved by making some of them return a bool indicating success or failure. For instance, del could return false if the number is not in the list or true if it was found and deleted.

Use nullptr rather than NULL

Modern C++ uses nullptr rather than NULL. See this answer for why and how it's useful.

Use for instead of while where appropriate

In almost every place in the code that uses a while loop, it would be much more idiomatic C++ if a for loop were used instead. For example, the print routine is currently this:

void print()
{
    node *next = first;

    while (next != NULL) {
        cout << next->n << " ";
        next = next->point;
    }
    cout << endl << endl << endl;
    return;
}

It would be better written like this:

void print(node *head)
{
    for ( ; head != nullptr; head = head->point) {
        std::cout << head->n << " ";
    }
    std::cout << "\n\n\n";
}

Note that the head parameter is being passed in rather than using a global variable, and that the namespace is explicitly used. Also, note that I've used the string literal "\n\n\n" instead of three repetitions of std::endl. This is more efficient because it doesn't force the buffer to be flushed repeatedly. Finally, I've removed the return because it is not needed for a void function.

Rethink the interface

It would be simpler and more logical for the search routine to return a pointer to the node or nullptr if it is not found. Here's one way to write it:

node* search(node *head, int n)
{
    for ( ; head != nullptr && head->n != n; head = head->point ) {
    }
    return head;
}

Sanitize user input

Right now, if the user inputs anything that is not a number, the program stays in a loop forever. Instead of extracting an int, get a std::string and use std::stoi() to convert it to an integer.

Use helper routines

Right now, there is a lot of code duplication. The search, insert and delete routines all search for the node first. If you extracted this code into a helper routine to find the node before a match, returning a node *, you could reuse searchPrev within insert and delete instead of duplicating it in every function:

node* searchPrev(node *head, int n)
{
    for ( ; head && head->point && head->point->n < n; head = head->point ) {
    }
    return head;
}
\$\endgroup\$
  • \$\begingroup\$ People have told me earlier to avoid global variable and pass them as arguments to each function but isn't using global variable much less tedious especially when I have multiple classes and functions in one class operate on objects of other classes too.Can you provide me some examples where using global variables makes the program error prone? \$\endgroup\$ – CodeMaxx Nov 26 '15 at 8:08
  • \$\begingroup\$ I've added a bit more about why one should avoid using global variables. \$\endgroup\$ – Edward Nov 26 '15 at 13:02
4
\$\begingroup\$

While your code doesn't leak right now, it will leak as soon as you replace int as a value type with a more complex or generic object type. Then for example in lines like this:

first->n=n;

exceptions can occur and you will leak memory. This is subtle and difficult to get right. Therefore always* use smart pointers to express ownership, in this case std::unique_ptr.

*: unless absolutely necessary and you know what you are doing.

Otherwise follow the advise of Edward which is much more immediate.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.