Stacked list is all about having ONE head pointer.
Pop is O(1)
Push is O(1)
The head pointer is used to add and remove.
For append:
1) We have head point to NULL in the beginning
2) First item is initialized through being supplied with values from its constructor parameters. These parameters are int data, and whatever head is pointing to.
If we’re starting out, head should be pointing to NULL. If there were previous items, then head should be pointing to the latest pushed item.
3) In the case of appending the first node, our first node’s pNext should be to what head is pointing to, which is NULL.
4) our head then re-points to the newly created Node object. Our first object as been appended.
For pop, its about having a temp pointer pointing to the head, then have the head traverse 1 step forward. Then delete the object that temp is pointing to.
|
1 2 3 4 5 6 7 8 9 10 11 |
if(!isEmpty()) { Node * toDelete = head; head = head->pNext; int toReturn = toDelete->iData; toDelete->iData = -1; toDelete->pNext = nullptr; delete toDelete; return toReturn; } |