Public Group

# Looking for Help/Examples for Linked Lists (C++)

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

## Recommended Posts

#include <iostream>
#include <string>

using namespace std;

enum { kIsSmaller, kIsLarger, kIsSame};

class Player
{
public:
int CT;
string name;
Player(string name):myCT(CT){};
~Player(){}
int Compare(const Player&);
void Show() { cout << name << ": " << myCT << endl; }
private:
int myCT;
};

int Player::Compare(const Player & theOtherPlayer)
{
if (myCT < theOtherPlayer.myCT)
return kIsSmaller;
if (myCT > theOtherPlayer.myCT)
return kIsLarger;
else
return kIsSame;
}

class Node;
class TailNode;
class InternalNode;

class Node
{
public:
Node(){}
virtual ~Node(){}
virtual Node * Insert(Player * thePlayer)=0;
virtual void Show() = 0;
private:
};

class InternalNode: public Node
{
public:
InternalNode(Player * thePlayer, Node * next);
virtual ~InternalNode(){ delete myNext; delete myPlayer; }
virtual Node * Insert(Player * thePlayer);
virtual void Show()
{ myPlayer->Show(); myNext->Show(); }

private:
Player * myPlayer;
Node * myNext;
};

InternalNode::InternalNode(Player * thePlayer, Node * next):
myPlayer(thePlayer),myNext(next)
{
}

Node * InternalNode::Insert(Player * thePlayer)
{

int result = myPlayer->Compare(*thePlayer);

switch(result)
{
case kIsSame:
case kIsLarger:
{
InternalNode * playerNode =
new InternalNode(thePlayer, this);
return playerNode;
}

case kIsSmaller:
myNext = myNext->Insert(thePlayer);
return this;
}
return this;
}

class TailNode : public Node
{
public:
TailNode(){}
virtual ~TailNode(){}
virtual Node * Insert(Player * thePlayer);
virtual void Show() { }
private:
};

Node * TailNode::Insert(Player * thePlayer)
{
InternalNode * playerNode = new InternalNode(thePlayer, this);
return playerNode;
}

{
public:
virtual ~HeadNode() { delete myNext; }
virtual Node * Insert(Player * thePlayer);
virtual void Show() { myNext->Show(); }
private:
Node * myNext;
};

{
myNext = new TailNode;
}

{
myNext = myNext->Insert(thePlayer);
return this;
}

{
public:
void Insert(Player * thePlayer);
private:
};

{
}

{
}

int main()
{
Player * pPlayer;
int CT;
string name;

for (;;)
{
cout << "What Name?: ";
cin >> name;
cout << "What CT? (0 to stop): ";
cin >> CT;
if (!CT)
break;
pPlayer = new Player(name);
ll.Insert(pPlayer);
}

ll.ShowAll();
return 0;
}

Thank you for your time, I appreciate and look forward to your input!

##### Share on other sites

To that end, I would highly recommend you use an STL container instead of trying to build a linked list. It's faster, safer and very thouroughly tested.

Depending on what you're specifically trying to do, you're probably looking for std::vector or std::list. STL is somewhat intimidating at first but believe me it will save you a great deal of headaches later on down the line and will actually reduce the amount of code you write. Using an STL solution in your case could reduce your entire code from what it is to just a few lines in your main() function.

In the particular case of using a linked-list type solution, you won't need to bother too much with iterators (a virtual nightmare until you get used to them).

##### Share on other sites
[NINJA'D][disturbed]

Hullo.

[Removed]Blech. Got that all wrong. Need sleep...

Also, while I've not used C++ in forever, I think most people suggest using the Standard Template Library(STL) for stuff like this. According to this site, they have a nifty doubly linked list template container thingy. It also seems to have a sort method(you'll hafta scroll down the page a bit) that'll sort the list based on the overloaded < operator. It'd probably be safer/better/easier to use this and just overload the < operator.

Hope I helped!

##### Share on other sites
I remember touching upon STL containers briefly while I was learning C++, but there wasn't a lot of detail given. My original draft for the project actually used a vector instead of Linked List, but the only way I could figure out how to sort it was from smallest to largest. (I made a mistake within my actual program, and it's supposed to display from largest to smallest, but again, that's a fairly easy mix up to remedy.)

I did however take a brief look at the sites both of you linked, and it may be just what I'm looking for. Unfortunately, my brain has just about melted from an overload of work today, so I will check them out tomorrow when I'm refreshed and see if that was just the ticket I needed to solve my problem. Thank you for your quick replies.

##### Share on other sites
First off: the "STL" is no more. It's the standard library of C++ now, and to ignore it is no more reasonable than to ignore the standard library of any other language. You wouldn't try to write C code without strlen() et. al. would you? So don't try to use C++ without standard library containers.

Quote:
 Original post by PaladinJohnbut the only way I could figure out how to sort it was from smallest to largest.

The standard library separates "algorithms" from containers. Sorting can be done with any container. However, lists need special handling because of how they're constructed (there is no direct random access, which makes some sorting techniques unuseful).

To change the sorting order, you can specify a comparison operation as the third parameter to std::sort(). If your container holds instances of your own class or struct which has a "natural sorting order", you can specify that by implementing operator< for the class or struct. If you want to sort the instance naturally from largest to smallest, then do both: implement operator<, and then use 'std::greater' as the sort order. (std::greater is actually a function. To specify your own comparison operations, you can either write functions, or overload operator() for some other class and pass an instance.)

Also, your class constructor is broken: it uses the uninitialized public 'CT' to initialize the private 'myCT', and ignores the passed in 'name', leaving the instance's 'name' member empty. (And WTF is a "CT", anyway?)

// Don't 'use namespace std;' in headers. The file that #includes the header// has no way to undo it.class Player {  std::string name;  int value;  public:  // Pass instances of objects by const reference, in general.  Player(const std::string& name, int value): name(name), value(value) {}  // Don't bother writing and implementing empty destructors, unless they're virtual.  // For the comparison to work naturally with std::sort, you need it to be  // an operator overload. You don't need a 3-way comparison.  boolean operator<(const Player& p) { return value < p.value; }  // Use standard idioms for output.  friend ostream& operator<<(ostream& os, const Player& p) {    return os << p.name << ": " << p.value;  }};using namespace std;int main() {  vector<Player> players;  int value;  string name;  // If you're going to write an infinite loop, do it in a way that's  // more easily recognizable.  while (true) {    // Please note the techniques used here for robust input.    cout << "Give a name and a value, or invalid input to stop: "    if (!(cin >> name >> value)) { break; }    players.push_back(Player(name, value));    std::getline(std::cin, name); // consume the rest of the line.  }  sort(players.begin(), players.end());  // Look what else you can do with <algorithm>:  copy(players.begin(), players.end(), ostream_iterator<Player>(cout, "\n"));}

##### Share on other sites
Quote:
 If you want to sort the instance naturally from largest to smallest, then do both: implement operator<, and then use 'std::greater' as the sort order.

A minor correction: std::greater is a wrapper around operator>, which can be implemented in terms of <, but needs to be implemented.

#include <iostream>#include <list>#include <functional>#include <cstdlib>using namespace std;struct Test{    int n;    Test(int n): n(n) {}};bool operator< (const Test& a, const Test& b){    return a.n < b.n;}bool operator> (const Test& a, const Test& b){    return b < a;}typedef list<Test> Tests;void print(const Tests& tests){    for (Tests::const_iterator it = tests.begin(); it != tests.end(); ++it) {        std::cout << it->n << ' ';    }    std::cout << '\n';}int main(){    Tests tests;    for (int i = 0; i != 10; ++i) {        tests.push_back(Test(rand() % 128));    }    tests.sort();    print(tests);    tests.sort(greater<Test>());    print(tests);    return 0;}

##### Share on other sites
Quote:
 Original post by visitorwhich can be implemented in terms of <, but needs to be implemented.

Of course, it's possible to do that for all types via a template. Although I think one of the standard library headers provides such a template anyway. :)

##### Share on other sites
Thank you all for the wealth of information. I took a different approach to the program and I got further than before, but I still have a few bugs to work out. I'm going to attempt to see if I can fix it myself before asking for more help on the subject since I'm one of those people that learns from my mistakes, and then learning how not to make those mistakes again. XD

Quote:
 Original post by Zahlman(And WTF is a "CT", anyway?)

I should have added a note in the code itself, but CT stands for "Charge Time". I had it as CT for clarity's sake for myself, but I can see why it would raise a few eyebrows.

In a more advanced version of the program I will do in the future, I'll include the full basis for taking turns. Essentially, each "Clock Tick" adds a certain number based on each character's speed to their respective "Charge Time". When someone's number reaches 100+, it's their turn. After taking a turn, based on the action(s) they took during their turn they have a certain number subtracted from their current CT, and then the clock ticks back up. Clock Ticks are used to determine persistent effects that affect a character over a span of time.

Of course, while I have this all mapped out in Pseudo-code, I want to take it slow and add to the program bit by bit to make sure that I'm not only learning, but I don't overwhelm myself with too many elements too quickly. Also, I figure it will be easier for me to trouble shoot my program if I know all of the code that came before the new coding is good code.

##### Share on other sites
Quote:
 Although I think one of the standard library headers provides such a template anyway. :)

I have heard that Boost.Operators can be used to synthesize additional operators from a set of base operators. Which should look something like this. Given the presence of overloaded <, operators >, <= and >= are free.

#include <iostream>#include <list>#include <functional>#include <cstdlib>#include <boost/operators.hpp>using namespace std;struct Test: boost::less_than_comparable<Test>{    int n;    Test(int n): n(n) {}};bool operator< (const Test& a, const Test& b){    return a.n < b.n;}typedef list<Test> Tests;void print(const Tests& tests){    for (Tests::const_iterator it = tests.begin(); it != tests.end(); ++it) {        std::cout << it->n << ' ';    }    std::cout << '\n';}int main(){    Tests tests;    for (int i = 0; i != 10; ++i) {        tests.push_back(Test(rand() % 128));    }    tests.sort();    print(tests);    tests.sort(greater<Test>());    print(tests);    std::cout << (tests.front() <= tests.back()) << ' ' << (tests.front() >= tests.back()) << '\n';    return 0;}

##### Share on other sites
Well, you see, that's the thing. I was sure I remembered seeing something like that, but then I couldn't find it when I tried looking it up. x.x

• 40
• 12
• 10
• 10
• 9
• ### Forum Statistics

• Total Topics
631368
• Total Posts
2999595
×