Sign in to follow this  

Would this linked list work?

This topic is 3629 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I know there are tons of stuff out there explaining linked lists and stuff but I wrote this one off the top of my head and just to make sure I understand them I did not want to compare to a working one, rather get some input. Mainly want to make sure this code: 1) Has no memory leaks 2) Follows proper programming practices/industry standards 3) Not doing anything unnecessary Header:
#pragma once

#include <string>

struct MenuItem {
	std::string menuText;
	int xPos;
	int yPos;
	MenuItem* next;
	static MenuItem* head;
};

class Menu {
private:
	MenuItem* m_pMenuItems;
public:
	Menu();
	~Menu();

	void addMenuItem(std::string menuText, int xPos, int yPos);
};


Source:
#include "Menu.h"

MenuItem* MenuItem::head = 0;

Menu::Menu() {
	m_pMenuItems = NULL;
}

Menu::~Menu() {
	// clean up the linked list
	MenuItem* temp;

	temp = m_pMenuItems->head;
	while(temp) {
		m_pMenuItems = temp->next;
		delete temp;
		temp = m_pMenuItems;
	}
}

void Menu::addMenuItem(std::string menuText, int xPos, int yPos) {
	// check and make sure we have a menu item
	if(m_pMenuItems) {
		// if it does exist we just need to create a new MenuItem and set it to the head
		MenuItem* temp;

		// create a new MenuItem
		temp = new MenuItem();
		temp->menuText = menuText;
		temp->xPos = xPos;
		temp->yPos = yPos;

		// set the next to the current head and then reset the head to the last created
		temp->next = m_pMenuItems->head;
		m_pMenuItems->head = temp;
	} else {
		// otherwise we need to create a menu
		m_pMenuItems = new MenuItem();

		// assign the values
		m_pMenuItems->menuText = menuText;
		m_pMenuItems->xPos = xPos;
		m_pMenuItems->yPos = yPos;

		// set the head to itself since it is the only one
		m_pMenuItems->head = m_pMenuItems;
	}
}


Share this post


Link to post
Share on other sites
Your use of a static head pointer is completely broken if you ever want to create more than one menu at a time. To answer your questions, aside from that issue:

1) There is at least one memory leak: if when creating a new menu item, assignment of menuText throws an exception, you will leak the new menu item.
2) No. Existing practice would be to use an existing container like std::list.
3) Unnecessarily implements a linked list.

Share this post


Link to post
Share on other sites
1. Make sure that it's exception safe. I don't believe it is, but I'm not sure. If it's not, exceptions could cause you to leak memory.
2. #pragma once is MS VC++ only. You should use ifndef guards instead. They are more idiomatic and portable. Adding an item to a list generally adds it to the end of the list, not the top, but that's not real important.
3. Well, other than that you could be using std::list instead and not have to write *any* of this code, you're addMenuItem function is repetitive. If you look at it, it does the exact same either way the if() goes. If the original head is null, then setting the new head's next to the original head won't do anything (it was already null).

Share this post


Link to post
Share on other sites
Thank you for the speedy reply. I see your point about not being able to create more than one menu. Overlooked that since I was designing this for a specific purpose but the whole reason I wanted a linked list in the first place is because I am trying to design this with extreme flexibility so point taken!

As far as the memory leak, when would menuText throw an exception and how would you properly handle that? I think I understood you right that if the menuText threw an exception it would leak the newly created MenuItem but I am unsure as to why. So I guess how would it leak and how would you fix that? Just for knowledge - I was unaware there was a container for linked lists in the STL - guess I need to review what it has to offer a little more.

Either way, thank you for your help.

Share this post


Link to post
Share on other sites
Assignment of a std::string can fail if there's an out of memory situation, or sometimes in a heap corruption situation (though in that case, newing the menu item should probably not work).

Also, I just noticed you take a std::string by value in your addMenuItem() function. You should probably use a const reference instead.

Share this post


Link to post
Share on other sites
It depends on the data type. Passing a single char by const reference instead of by value would be pretty pointless. Basically anything bigger than a double or with a non-trivial copy constructor should be passed by const reference instead of by value.

Share this post


Link to post
Share on other sites
Ahh, makes sense. I could probably ask a zillion more questions but would you happen to know a good book that goes over all of these programming practices and standards? I pick up concepts very well and documentation pretty much can get me along with knowing the code but where I am falling short is the standards I think, hard to know everything from day 1, heh.

Share this post


Link to post
Share on other sites
Quote:
Original post by Nabren
Ahh, makes sense. I could probably ask a zillion more questions but would you happen to know a good book that goes over all of these programming practices and standards?


The C++ FAQ Lite is pretty much required reading. It covers some good practice stuff, as well as other stuff.

It's not a book though, and is not really comprehensive.

Share this post


Link to post
Share on other sites
For books, you might want to try "Effective C++", "More Effective C++" and "Effective STL" by Scott Meyers, "C++ Gotchas" and "C++ Common Knowledge" by Dewhurst and "Exception C++", "More Exceptional C++" and "C++ Coding Standards" by Herb Sutter (and the last with Andrei Alexandrescu).

Share this post


Link to post
Share on other sites
I would like to add to this, that building your own Linked List for the sake of understanding how it works on the inside(And frankly, every programmer should know how his containers work on the inside for a better understanding of when you use which).

If you implement a LinkedList just because you need a container to store things, then you're probably doing things wrong. But, if you're just learning, go for it.

Toolmaker

Share this post


Link to post
Share on other sites

This topic is 3629 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this