patterncppModerate
Does my Linklist implementation have memory leaks?
Viewed 0 times
linklistmemorydoesimplementationleakshave
Problem
Are there any memory leaks in this linklist implementation.Also is the implementation correct?Can the time complexity be optimized?
#include
#include
#include
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>s;
switch(s)
{
case 1: cout>n;
search(n);
break;
case 2: cout>n;
insert(n);
break;
case 3: cout>n;
del(n);
break;
case 4: print();
break;
case 5: exit(0);
default: coutn==n)
{
coutpoint;
}
coutn>n)
{
first=new node;
first->n=n;
first->point=next;
coutn>n)
{
prev->point=new node;
(prev->point)->n=n;
(prev->point)->point=next;
coutpoint;
}
}
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;
}
coutnpoint;
}
coutn==n)
{
if(prev!=NULL)
{
prev->point=next->point;
delete next;
}
else
{
first=next->point;
delete next;
}
coutpoint;
}
}
cout<<"Number not in list"<<endl<<endl<<endl;
return;
}Solution
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:
write this:
Don't abuse
Putting
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
Use object orientation
Because you're writing in C++, it would make sense to have the methods that operate on a class (such as
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
Return something useful from functions
All of your functions currently return
Use
Modern C++ uses
Use
In almost every place in the code that uses a
It would be better written like this:
Note that the
Rethink the interface
It would be simpler and more logical for the
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
Use helper routines
Right now, there is a lot of code duplication. The
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 stdPutting
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 NULLModern C++ uses
nullptr rather than NULL. See this answer for why and how it's useful. Use
for instead of while where appropriateIn 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 n 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 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 point ) {
}
return head;
}Code Snippets
cout<<"Number not in list"<<endl<<endl<<endl;cout << "Number not in list" << endl << endl << endl;void print()
{
node *next = first;
while (next != NULL) {
cout << next->n << " ";
next = next->point;
}
cout << endl << endl << endl;
return;
}void print(node *head)
{
for ( ; head != nullptr; head = head->point) {
std::cout << head->n << " ";
}
std::cout << "\n\n\n";
}node* search(node *head, int n)
{
for ( ; head != nullptr && head->n != n; head = head->point ) {
}
return head;
}Context
StackExchange Code Review Q#111808, answer score: 11
Revisions (0)
No revisions yet.