Null Object Pattern in a doubly linked list

Question

I'm trying to use the null object pattern in a doubly linked list in c++, but I can't seem to find a way to use it while keeping the code clean.

The problem lies in the following piece of code:

node->getNext()->setPrevious(node->getPrevious());
node->getPrevious()->setNext(node->getNext());

getNext and getPrevious will return a NullNode object if the next/previous node is a nullptr.

A use case where this fails - when node is the head node:

The following will set the 2nd node's previous pointer to a NullNode object causing a memory leak .

node->getNext()->setPrevious(node->getPrevious());

What I'm trying to accomplish here is to keep the NOP and keep the code clean from nullptr and class type comparison,

Any suggestions will be very appreciated!

I did not understand the problem. If node->prev is NullObject wouldn't you want node->next->prev to be set to NullObject? — selalerer
If I'm understanding you, this is a memory management problem more than a Null Object implementation problem. (e.g., If you use smart pointers, you'd see the expected behavior and without the memory leak.) In fact, you'd have the exact same memory leak if you weren't using the NOP at all. — Lilshieste
@Lilshieste Smart pointers don't work for double linked lists, because of the cycles involved. — James Kanze
@JamesKanze Excellent point; completely overlooked that one. — Lilshieste

galop1n galop1n · Accepted Answer · 2014-04-17T14:28:01

Things are simpler if you store the node previous and next, something like that :

Node* Detach( Node* node) {
  auto prev = node->getPrevious();
  auto next = node->getNext();
  prev->setNext( next );
  next->setPrevious( prev);

  node->setNext( nullNodeAddr);
  node->setPrevious( nullNodeAddr);

  return node;
}

The NOP or Sentinel pattern is a way to simplify operations to never care about null value at the head and tail of the list. If you need to test about it somewhere, then you fail.

Null Object Pattern in a doubly linked list

1 Answers