pop() function implementation in a Linked List (C++)

Question

I'm overall kind of confused about the idea of linked lists. So I'm trying to implement some functions to help me understand.

struct Node {
  string val;
  Node* next;
  Node* prev;
};

struct Stew {
  Node* first;
  Node* last;
};

So here, Stew has special pointers to the front element and the last element.

I'm trying to remove the first element (pop).

So I attempted it as follows, and I can't seem to find what the error in it is:

void pop (Stew& q) {
  assert (!isEmpty(q));
  q.first = q.first->next;
  q.first -> prev = NULL;
}

Any help would be appreciated, thank you!

By the way, I'm currently using C++98, not C++11.

What tells you this is wrong? Do you get compile-time / run-time errors or is the behaviour not correct, in what cases is it not correct? — user3072164
– user3072164, Commented Feb 27, 2014 at 18:06
Is there some reason you are not encapsulating the pop function within your linked list class? — Zac Howland
– Zac Howland, Commented Feb 27, 2014 at 18:06
note that a pop function should remove the first item from the list and return it, right now you are just losing this item, having no pointer to it and no way to use it or free the memory it uses. — Ron Teller
– Ron Teller, Commented Feb 27, 2014 at 18:09
@user3358732 Is it always wrong or only in specific cases and what does wrongly happen? — user3072164
– user3072164, Commented Feb 27, 2014 at 18:14

user3072164 · Accepted Answer · 2014-02-27 18:17:50Z

You forgot to free the memory of the deleted node with delete and you didn't take care of the case that the list is exactly one element long. Because if that is the case then after

q.first = q.first->next;

q.first is NULL. Then you try to dereference q.first in the next line:

q.first -> prev = NULL;

Don't do that step if the list was original one element long and is afterwards empty. Instead take care of q.last which won't be pointing to allocated memory anymore:

q.first = q.first->next;
if(q.first)
    q.first->prev = NULL;
else
    q.last = NULL;

(Although depending on the implementation of the rest of the linked list the else block won't be necessary, because the information whether the list is empty is fully contained in either q.last or q.first)

Also pop usually returns the removed value. Your pop doesn't do that.

Raydel Miranda · Accepted Answer · 2014-02-27 18:22:42Z

0

I just realized you have implemented a last pontier to your Stew class so you can:

struct Node {
  string val;
  Node* next;
  Node* prev;
};

struct Stew {
  Node* first;
  Node* last;
};


typedef struct Node node_t;
typedef struct Stew stew_t;

node_t* pop(stew_t& q)
{
    node_t* last = q->last;
    if (q->last == q->first)        // List is empty or has only one element.
    {
        q->first = NULL;
        q->last = NULL;
    }
    else
    {
         q->last = last->prev;     // Update the last pointer.
    }

    return last;
}

edited Feb 27, 2014 at 18:22

answered Feb 27, 2014 at 18:17

Raydel Miranda

14.4k3 gold badges48 silver badges66 bronze badges

Collectives™ on Stack Overflow

pop() function implementation in a Linked List (C++)

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related