Sentinel (Programmierung)

Als Sentinel (engl. für Wächter), Wächter oder Wächterwert bezeichnet man in der Informatik, dort im Bereich der Programmierung, ein Konstrukt, welches beim Durchsuchen z. B. von Listen nach Inspektion aller echten Fälle auf jeden Fall gefunden wird.

Damit wird die Anzahl der Abfragen innerhalb der Suchschleife um eine verringert auf Kosten geringfügig komplizierterer Aktionen außerhalb der Schleife.

Beispiel

In den beiden folgenden Suchschleifen Search und SearchWithSentinel soll in einer verketteten Liste vom Typ

// Globale Variable:
struct Node {
  int key;
  struct Node *next;
} List, *first;

nach einem Schlüsselwert Datum gesucht werden – bei gleichem Suchergebnis.

• Version ohne Sentinel: Die Liste List wird terminiert durch NULL.

  // Global:
  first = NULL; // vor der ersten Einfügung
  
  Search(struct Node *first, int Datum) {
      struct Node *node;
      for (node = first; node != NULL; node=node->next) {
          if (node->key == Datum) return node;
      }
      // Nicht gefunden
      return NULL;
  }
  

  Die for-Schleife enthält pro Schleifenschritt die zwei Abfragen

  1. if (node != NULL) und
  2. if (node->key == Datum).
• Version mit Sentinel: Die Liste List wird terminiert durch sentinel.

  // Globale Variable:
  struct Node Sentinel, *sentinel = &Sentinel;
  // Global:
  first = sentinel; // vor der ersten Einfügung
  
  SearchWithSentinel(struct Node *first, int Datum) {
      struct Node *node;
      sentinel->key = Datum;
      for (node = first; node->key != Datum; node=node->next) {
      }
      if (node != sentinel) return node;
      // Nicht gefunden:
      return NULL;
  }
  

  Die for-Schleife enthält pro Schleifenschritt nur die eine Abfrage

  1. if (node->key != Datum).

Siehe auch

• Suchmethode en:Elephant in Cairo (englisch), die auf einen satirischen Essay über verschiedene Suchmethoden nach Elefanten in Afrika zurückgeht.
• Sentinel-Lymphknoten, siehe Wächterlymphknoten