Simple implementation of a list of links in C ++

Question

I participate in programming in my first C ++ class, and recently we looked at linked lists, and we were given the task of implementing a simple one. I encoded everything, but my function is pop_back() , which fusses to return a pointer to a Node that needs to be removed in Main() . There is no Node removal in a valid function. So my question is:

Could you help me point me in the right direction for my pop_back() function? Also, if you notice anything else that I'm doing wrong, let me know.

In addition, this linked list is designed to work with strings. In this case, the list of products, so that one line for the number of elements (1,2) and one line for the type of element. (Milk, eggs, etc.)

Below I have included an implementation of the List and Node classes, so you can get an idea of ​​what I have done so far.

Node.cpp

 Node::Node(void) { descrip = " "; quantity = " "; previous = NULL; next = NULL; } Node::Node(string q, string d) { descrip = d; quantity = q; previous = NULL; next = NULL; } Node* Node::GetNext() { return next; } Node* Node::GetPrevious() { return previous; } void Node::SetNext(Node * setter) { next = setter; } void Node::SetPrevious(Node * setter) { previous = setter; } 

---

List.cpp

 List::List(void) { first = NULL; last = NULL; numNodes = 0; } Node* List::GetFirst() { return first; } Node* List::GetLast() { return last; } void List::SetFirst(Node* setter) { first = setter; } void List::SetLast(Node* setter) { last = setter; } int List::GetNumNodes() { return numNodes; } void List::push_front(Node* item) { if (first == NULL) { first = item; last = item; } else { Node* pFirst = first; item->SetNext(pFirst); first = item; numNodes++; } } void List::push_back(Node * item) { if (last == NULL) { first = item; last = item; } else { last->SetNext(item); last = item; numNodes++; } } Node* List::pop_front() { Node* temp = first; first = first->GetNext(); if (first == NULL) { temp = first->GetNext(); first = p; } if (first == NULL) { last = NULL; } if (numNodes > 0) { numNodes--; } return temp; } Node* List::pop_back() // this whole function may be wrong, this is just my attempt at it { Node* temp; temp = first; while((temp->GetNext()) != NULL) // im stuck here } 

Answer 1

So, if I understand this right, do you just want to look at your linked list until you reach the last node in the linked list and return the pointer to it? I'm sure you will have it there, except

 Node* List::pop_back() // this whole function may be wrong, this is just my attempt at it { Node* temp; temp = first; while(temp->GetNext() != NULL) { temp = temp->GetNext(); } return temp; } 

So, if I read it correctly, it will constantly cycle around until it reaches node, and not one of them remains on the line, and then returns it.

Answer 2

Some pointers:

 0x1243bfa3 0x45afc56e 0xdeadbeef 

A few more pointers:

• You should prefer to initialize your class members in the initialization list rather than in the constructor body.

• In C ++, unlike C89, we declare and define a function with no parameters as void f(); , not void f(void); .

• In C ++, we usually reset pointers from 0 , not NULL .

  See below what I mean in code.

• Good C ++ code will try to use RAII . This implies abandoning primitive pointers for the most part. In this case, the plain old std::auto_ptr<> will do a fairly sufficient replacement for primitve Node* pointers. However, I believe that part of the exercise here is pointer arithmetic, and so I just leave this as a note.

• This would be useful for us if you were to attach class declarations. I assume that all of these accessors and mutators, GetFirst() and SetFirst() , etc., exist because they are publicly available. It is a bad idea. First, they set up private pointers that defeat the entire access point. Secondly, they are not doing anything special, so they are just extra code, which means an extra room for errors. This brings me to the next point.

• Your mutators are wrong. You blindly assign a new value to a private member index without deleting what you had before. This is a memory leak.

• Ever tried pop_front() when the list is empty?

• Finally, 8 is the round number we get to. pop_back() . My question to you is: why do you go through the list to the end if you carefully maintain a pointer to the last node of your list? In fact, if you didn’t bother to maintain a pointer to the end of the list, you would need to go all the way to the last node to mark it. And for that, you were in the right direction. Besides that ...

• When you access members through pointers, as in first->GetNext() , always make sure that first not a null pointer, or indicate in a comment on the function documentation that you assume that the pointer is not null.

This should help you get started.

Points 1, 2 and 3 in the code:

 Node::Node() : descrip(" "), quantity(" "), previous(0), next(0) { } 

Answer 3

I like the answers from the previous posters, but one thing you might want to keep in mind is to have an empty list. Then your first pointer will be NULL, and you will try to call NULL-> GetNext () basically and Seg Fault. I think you can slightly modify the above code and still work like this:

 Node* List::pop_back() { Node* temp; temp = first; while(temp != NULL && temp->GetNext() != NULL) { temp = temp->GetNext(); } return temp; } 

This will have a return NULL function if there is nothing in the list and it still works correctly.

Answer 4

That would definitely help me if you also posted your class ad. I can not guarantee that the below is true, but it makes sense to me.

 Node* List::pop_back() { Node *temp = NULL; if(numNodes == 1) { temp = first; // setting the list pointers to NULL first = NULL; // setting the list pointers to NULL last = NULL; //You should also probably remove the links from your node //to the next and previous nodes but since you didn't specify //this it is up to you numNodes--; } else if(numNodes > 1) //more than one element { //the pointer you want to return temp = last; //For clarity I am creating another variable here Node *newLast = temp->GetPrevious(); //Setting the new last node to point at nothing so now temp //is "disconnected from the list" newLast->next = NULL; //the last pointer of the list is now pointing at the new last node last = newLast; //You should also probably remove the links from your node //to the next and previous nodes but since you didn't specify this it is up to you numNodes--; //decrement the counter } return temp; }