Sentinel und Listenkopf

Mr. Blonde

Hallo,

Wie kann ich mit einem Sentinel und Listenkopf in einer einfach verketteten Liste arbeiten?
Ich hab dazu noch nichts im Internet bzw. in meinen Büchern gefunden ... hab hier mal ein kleines Beispiel ohne Sentinel und Listenkopf:

dekl:

class Kset
{
private:
        struct Knoten
        {
         int Inhalt;
         Knoten *pNext;
        };

        int Anzahl;
        Knoten *pFirst;
        Knoten *pLast;

public:
        Kset();
        ~Kset();

        void insert_front(int obj);
};

impl:

#include "dekl11.h"

//Konstruktor///////////////////////////////////////////////////////////////////

Kset::Kset()
{
 Anzahl = 0;
 pFirst = pLast = NULL;
 /*Knoten *Listenkopf = new Knoten;
 Knoten *Sentinal = new Knoten;
 pFirst = Listenkopf;
 Listenkopf->pNext = Sentinal;
 Sentinal->pNext = pLast;*/
}

//Dekonstruktor/////////////////////////////////////////////////////////////////

Kset::~Kset()
{
 Knoten *ptemp = pFirst;
 for(; Anzahl>0;)
 {
  pFirst = pFirst->pNext;
  delete ptemp;
  ptemp = pFirst;
  Anzahl--;
 }
}

//vorne einfügen////////////////////////////////////////////////////////////////

void Kset::insert_front(int obj)
{
 if(Anzahl == 0)
 {
  pFirst = new Knoten;
  pFirst->Inhalt = obj;
  pFirst->pNext = NULL;
  pLast = pFirst;
 }
 else
 {
  Knoten *pNew = new Knoten;
  pNew->Inhalt = obj;
  pNew->pNext = pFirst;
  pFirst = pNew;
 }
Anzahl++;
}

Wie sieht das ganze aber mit aus?

Werner Salomon

Deine insert_front-Methode würde mit Sentinel auch nicht viel anders aussehen. Der Vorteil kommt bei einer einfach verketteten Liste nur bei Operationen am Ende zum tragen. Bei push_back z.B. (füge Element am Ende ein) kann auf jede Sonderbehandlung verzichtet werden.

Zum Beispiel

// -- mit Sentinel
class Kset
{
private:
    struct Knoten
    {
        explicit Knoten( int i = 0, Knoten* next_ = 0 )
            : Inhalt( i ), pNext( next_ )
        {}
        int Inhalt;
        Knoten *pNext;
    };

    int Anzahl;
    Knoten m_head; // <-- Sentinel
    Knoten *pLast;
    // ... usw.

Kset::Kset()
    : Anzahl( 0 )
    , m_head()
    , pLast( &m_head )
{}

void Kset::push_back( int obj )
{   // 'pLast' zeigt auch bei leerer Liste auf einen gültigen Knoten
    pLast->pNext = new Knoten( obj );
    pLast = pLast->pNext;
    ++Anzahl;
}

bei pop_back (entferne das letzte Element) wäre es ähnlich.

ohne Sentinel - also mit den Parametern, die Du gepostet hast - sähe push_back etwa so aus:

// -- ohne Sentinel
void Kset::push_back( int obj )
{
    if( pFirst ) // Liste ist nicht leer
    {
        pLast->pNext = new Knoten( obj );
        pLast = pLast->pNext;
    }
    else  // Liste ist bisher leer
    {
        pFirst = new Knoten( obj );
        pLast = pFirst;
    }
    ++Anzahl;
}

So richtig vorteilhaft ist ein Sentinel erst bei einer doppelt verketteten Liste. Dann ist jede Einfüge- oder Lösch-Operation immer gleich, egal an welcher Stelle der Liste sie stattfindet.

Gruß
Werner

Mr. Blonde

danke