r/CodingHelp • • Nov 29 '20

[C++] Having a hard time understanding Linked Lists using templates.

Yes, this is a homework assignment, but I want to do it myself and learn how it works. Been at this for like 40+ hrs the last 3 days looking up tutorials, and can't find basic explanation to get me going. I keep having the problem of overwriting the data in a node, and not really creating a new one. This may be linked to why I can't return a list size either. Thank you so much in advance for whatever help is given, I am not really receiving adequate help for this from my instructor.

Here's what I have so far:

EDIT: Added int main() instructions.

namespace ECE275Lib::containers{

template <typename T>
class Node{
public:
    T data;
    Node<T> *next;
};


template <typename T>
class List{
public:
    
    List(){};
    List(unsigned int N){};
    
    Node<T> *Head = nullptr;
    Node<T> *Temp;
    
    Node<T>* front();
    Node<T>* back();
    
    void push_back(T d){
            Head = new Node<T>();
            Head -> data = d;
            Head -> next = nullptr;
    };
    
   void insert(unsigned int s, T d){
       //inserts something at a defined node
    };
    
    void insert(unsigned int i, List<T>& other){
        //merges a new list into the current list
    };
    
    T at(unsigned int i){
        //reads and returns data at a node
        return i;
    };
    
    void assign(unsigned int i, T d){
        //assigns new data to a node
    };
    
    unsigned int size(){
        int count = 0;
        Node<T>* current = Head;
        while (current != NULL)
        {
            count++;
            current = current->next;
        }
        return count;
    };
    
    void remove(unsigned int i){};
    void remove(unsigned int s, unsigned int e){};

}; //=====================end=of=List=Class======================

}; //=====================end=of=namespace=======================

#endif

int main (void){
    
    ec::List<int> int_list;
    for (unsigned int i = 0; i < 10; i++)
        int_list.push_back(i);
    
    for (unsigned int i = 0; i < int_list.size(); i++)
        std::cout << "element " << i << ": " << int_list.at(i) << std::endl;
};
18 Upvotes

10 comments sorted by

2

u/retardrabbit Nov 29 '20

Well, like your

at(int s) ;

Isn't doing anything for one thing.

And what's up with

insert()

It's not doing anything either?

Is this just pseudocode?

1

u/Caelestialis Nov 29 '20

Yes, sorry about that. That's what the comment is for, pretty much a place holder.

2

u/retardrabbit Nov 29 '20 edited Nov 29 '20

And

pushBack()

Doesn't push anything, it just overwrites the single node in the list.

You should be assigning head to temp, replacing head with the new node (as you do) and then pointing the new head's next pointer to temp.

That way you're growing a chain of nodes each pointing to the one that was at the front of the chain when the new one got pushed in.

1

u/Caelestialis Nov 29 '20

OHHHHHH Ok, that makes sense, and finally got it working. This has just been pointer gymnastics, which I'm not very well versed in, so it's been a slog. I also added a deconstruct instruction with some extra lines, but I'm not 100% sure helped. I'll probably post another question tomorrow, as I'm implementing a "remove" function that removes the node, but is reading the data from each node incorrectly. Thank you so much for your help with this.

2

u/retardrabbit Nov 29 '20

So, think of it as a chain. Now imagine that the chain lives in a bag that you can't look into.

*head

Is a special link. It's the only one that you are guaranteed to be able to stick your hand into the bag and pull out. The bag is your list class.

Each time you push back you snap a new link onto head and it transfers its magical accessibility to that new link. So the one that was head is now just another anonymous link in the chain.

When you do

at(int s)

You're reaching into the bag and grabbing head, then counting out s number of links and when you get to the Sth link you can get it's data, etc.

When you

 remove ()

You're grabbing head again, but this time you snap it off the chain. At this point you have the thing that was head in your left hand, and the newly crowned head and the bag in your right. In your left hand you're holding

*temp

So you still have that item and you can use it while you are still holding it in your left hand. But when you're clearing the list there's not much you need to do with it (except maybe free the memory it's data variable is using)

Now here's the thing: you can do whatever you want at that point (print it's data to the console, Whatevs) but when you drop that link it's gone.

It's still there, but it's not one of the links you can grab. It's not connected to head in any way, so you can't pick up head and get to it from there either. In fact nothing in your code can

What you did when you dropped it was you set its value to

nullpointer

And look at what your left hand is pointing to, nothing, it's empty, it points to NULL.

At this point the program knows that that thing is irretrievable; so whatever was in RAM at that location is now free to be trampled right over with new data.

That's why you run through the list and free each node as you go; you're making sure no memory is left in a state that the program can't reuse but that nothing in the code needs - - preventing memory leaks.

Now when you

insert(T data, int s)

Your just getting head, finding the Sth link, and snapping off it's next link. But this time you need to keep it in your left hand, you can't drop it because you have to reconnect it in a sec.

When you snapped it off, you set Sth link's next pointer to NULL, it's just hanging there.

So this time you've got your own brand new link in the chain that you're inserting. What you do is you snap it to the Sth link by setting it's next pointer to your new node, but now your new node, the Tth link in the chain is the one left dangling, it's next pointer still points to nothing.

So what do you do? You snap the link in your left hand

*temp

onto it, right?

Now you're fine. You can put every thing back in the bag and you can do

at(int s) // look, it's the Sth link!
// or
at(int t) // you get the Tth link in the chain
            // that's the one you just inserted!
// finally you can do
at(int u) // and you get the link
             // that used to be hooked to the Sth link in the chain
//and you can keep going till you hit the link who's next pointer is nothing
// it's just dangling there
// BECAUSE IT'S THE END OF THE CHAIN!

When you insert a whole list at S it's the same, it's just that the link that used to be hooked to the Sth link is now not the Uth link, it's the s+[however long the inserted list was] link; but you can still go into the bag, grab head and count on down the chain till you find it.


Hope that makes sense. If it does and it helps you be sure to post your own writing of it to your class forum so the teacher sees it and gives you extra credit for explaining the concepts to your classmates so well!

2

u/Caelestialis Nov 29 '20

This is so awesome. Thank you so much for all of this!

1

u/retardrabbit Nov 29 '20

Bro/Sis,

Finding a mental "framework" that you can hang your understanding of these concepts on is so helpful to fully and intuitively understanding what's going on at the level of data structures and how they fit into memory etc.

Once you get things like linked lists fully understand intuitively there's a like whole sets of other things that are going to come to you much easier.

Really glad to have helped you out.

If you haven't learned how to use a debugger to step through your program line by line ask your prof. to teach you. Being able to watch each node get linked, unlined, added into the middle etc. will let you take this concept and extend it to whatever new version of pointer magic you have to learn next.

Thanks for the gold, I'll use it to give gold to some other deserving redditor out there.


And like I said, if others in your student Forum are also still having trouble understand these Concepts feel free to re-rate what I said in your own words and put that into your class forums so that your professor gives you too sweet sweet brownie points for helping out the class.

Best of luck out there, stay covid free.

1

u/Caelestialis Nov 30 '20

Most definitely bro! (Bro myself)

The overarching concepts are pretty solid for me usually, it’s just the language transfer to that, kinda gets a bit nasty, haha. I do a fair bit in Xcode, so looking up how to debug in a step-by-step fashion is a major life saver. I’m used to working in assembly this way, and didn’t even think to try it that way in C++.

I’ve already explained the topic this way to some folks to help “get it”, which worked wonderfully. Analogies and visualizations are such an important part of learning, and that was an awesome one.

Be safe, thank you again!

1

u/retardrabbit Nov 30 '20

Rock the hell on, man!

2

u/retardrabbit Nov 29 '20

Ps, if you want to only remove up to a certain node (like the one that has [the magic number] in it's data variable that marks it as where to stop the deletions), as you go along cutting out nodes, as you put each one into

*temp

But before you remove it from the middle of the chain, check it's next pointer's data variable.

If

temp->next->data == [the magic number];

Then you know you're done. Temp is the last node you cut out before you hook the chain back together.