Linked List pop() function

Question

Consider the following list:

[LinkNode * head -- LinkNode * node1 -- LinkNode * node2]

I'm creating a stack of FIFO. I Call pop() which I want to pop node1.

LinkNode::LinkNode(int numIn) {
    this->numIn = numIn;
    next = null;
}
.
.
.
int LinkNode::pop() {
    Link * temp = head->next;
    head = temp->next;
    int popped = head->nodeNum;
    delete temp;
    Return numOut;

Question:
1) head should be a pointer or a LinkNode *?
2) Link * temp is created on the call stack and when pop finishes doesn't temp delete automatically?
3) My major confusion is on what is the value of temp->next? Does this point to node1.next which equals node2?

Appreciate your help?

My reference is C++ for Java Programmers by Weiss.

Answer 1

1. LinkNode * is a pointer. So I'm not sure what you are asking.
2. The variable goes out of scope but this does not automatically remove the dynamically allocated data. In C++, if you dynamically allocate data (call new) you need to free it (call delete)

Answer 2

It is often useful when implementing linked lists, trees, or other linked data structures to separate the implementation into an encapsulating object (LinkedList, Tree, etc.) and a node object (LinkedListNode, TreeNode, etc.), which allows one to implement methods outside of the actual nodes in question. A problem with popping from the node is that the popped node becomes invalid. Encapsulating the nodes in some larger datastructure allows that datastructure to perform the pop externally, removing the old node.

Another thing to consider is how pop will behave if there are no items left to pop. Should it throw an exception? Should it simply result in undefined behavior?

In a typical linked list, the encapsulating class typically maintains a pointer to the first element, an integer count of the number of elements, and optionally a pointer to the last element (for constant time insertion to the end of the list). For implementing a stack, you only need a single pointer to the front of the list.

Local variables are destructed automatically; however, it is your pointer that is a local variable, not the item to which it is pointing. The item pointed to by your pointer will not be deallocated without an explicit delete.

In your pop code, you are actually removing one too many items. It should be:

int result = head->nodeNum; // extract the result
LinkNode* tmp = head; // save this so we can delete it
head = head->next; // move the head forward to the next item
delete tmp; // deallocate previous head
return result;

Also, don't forget to check that head is non-null before attempting to pop.

Answer 3

Good reference with pictures here. Very good visuals.

http://richardbowles.tripod.com/cpp/linklist/linklist.htm