Circular Doubly Linked List End Function

Question

In the bool end() function will the program know whether the sentinel is the beginning or end? Is there a check I can make to make sure it's reading the sentinel as the end?

#include "ring.h"
#include <stdlib.h>
#include <stdio.h>

struct node {
  int item;
  struct node *prev;
  struct node *next;
};
typedef struct node node;

struct ring {
  node *sentinel;
  node *current;
};

ring *new_ring() {
  ring *p;
  node *n;

  p = (ring *) malloc (sizeof(ring));
  n = malloc(sizeof(node));
  p->sentinel = n;
  n->next = n;
  n->prev = n;
  return p;
}

void start(ring *r) {
  r->current = r->sentinel;
}

bool end(ring *r) {
  return r->current == r->sentinel;
}

void forward(ring *r) {
  while (r->current != r->sentinel) {
     r->current = r->current->next;
  }
}

Please describe in more detail how exactly the circular list is supposed to work. What exactly is the role of the sentinel? — Codor, Dec 07 '15 at 14:06
The purpose is to allow the first and last nodes to point to it, so that there are no NULL pointers anywhere, and therefore no special-case tests for NULL. When the list is empty, it contains only the sentinel node, which points forwards and backwards to itself. — user5647965, Dec 07 '15 at 14:09
They say [you shouldn't cast the result of `malloc()`](http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc). — MikeCAT, Dec 07 '15 at 14:15
so, you want to replace special case tests for `NULL` with special case tests for the sentinel node. What do you expect to gain ? — Sander De Dycker, Dec 07 '15 at 14:43
In `end(ring *r)`, Initialize a new instance of `node` to the head of the list , then use a while loop to test for NULL as you loop through each item. — ryyker, Dec 07 '15 at 15:14

score 1 · Answer 1 · answered Dec 07 '15 at 15:20

Your specifications are:

start positions before first element of ring (ok)
end tests if current is past last element (ok)
forward steps one element on the ring (ok, unless that after calling start(), you have current == sentinel, so forward does nothing!)

But you should answer this question: do you need to implement the symetric functions?

If the answer is no, just change start to position on sentinel->next, ie on first element of ring if it exists and past the end if the ring is empty, and your are done.

If the answer is yes, then you have to be able to distinguish before first on one hand, and past end on the other.

There are 2 simple ways for that:

use a boolean to distinguish:
```
struct ring {
  node *sentinel;
  node *current;
  bool end;
};
```
you just set end to true when you position directly past the end of when forward (or any other read function) goes past the end, and to true in the opposite cases.
use 2 sentinels
```
struct ring {
  node *before;
  node *after;
  node *current;
};
```
You should initialize them with before->next = after; and after->prev = before

score 1 · Answer 2 · answered Dec 07 '15 at 16:21

As far as I understood, you need your end function to determine whether this is your last node of the ring or is this the beginning.

You may modify your end function to look something like this.

bool end(ring *r) {
    return r->current->next == r->sentinel;
}

If there is only one element in the ring, then always after your start function, the end condition will be true.

If however there are more than one elements then once end returns true, r->current will be the last element before sentinel.

Circular Doubly Linked List End Function

2 Answers2