CODEWITHSUNDEEP
c++linked-listc++98
E 4 6
E 4 6

Reputation: 157

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

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.

Upvotes: 0

Views: 1409

Answers (2)

Raydel Miranda
Raydel Miranda

Reputation: 14360

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;
}

Upvotes: 0

user3072164
user3072164

Reputation:

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.

Upvotes: 1

Related Questions