3. Einfuehrung - Einfach verkettete Listen

Einfuehrung - Einfach verkettete Listen

  • H

    Ich hab den thread nur mal ganz kurz überflogen, also nicht aufrregen, wenn einiges schon besprochen wurde.

    1.) Was ist eine verkettete Liste

    Eine verkettete Liste ist eine Menge von Knoten, welche eine bestimmte
    Information speichern. Dabei gibt es einen Anfangsknoten und einen Endknoten
    und dazwischen endlich viele weitere Knoten. Der Anfangsknoten zeigt auf den
    naechsten Knoten, welcher wiederum auf den naechsten Knoten zeigt usw. Der
    vorletzte Knoten zeigt auf den Endknoten.

    Ich kenn das eher so:
    Eine Liste ist entweder eine leere Liste (Effektiv durch 0 repräsentiert) oder ein Knoten bestehend aus den zu speichernden Werten und einer weiteren Liste.
    So ist auch sofort der rekursive Character erkennbar

    Allgemein würde ich erst mal mit einer absolut minimalen Liste anfangen, die auch nur das ist, was eine Lsite ausmacht. Dinge, wie zeiger auf den letzten Knoten, größe speichern, etc. würde ich erstmal komplett weglassen. Schnickschnack kannste immernoch dazubauen.

    ---------------------------

    Vor allem bin ich froh, das ich mir mal 'ne kleine Bibliothek gebastelt habe, mit der man solche Datenstrukturen deutlich einfacher, wenn auch nicht unbedingt übermäßig performant umsetzen kann.

    Bei mir sähe eine Liste dann so aus:

    VARIANT (List)

CASE_0 (List, Nil)

CASE_2 (List, Cons, 
   int, head,
   List, tail
)

    Algorithmen müssen dementsprechend umgesetzt werden:

    size_t size (List const & list)
{
   MATCH (list)
      WITH0 (Nil)
         return 0;
      ELSE_WITH (Cons, cons)
         return 1 + size (cons->tail);
   END_MATCH
}

    -----------------------------

    Zurück zum Thema. Um liste generell zu erklären muss die Implementation nicht auf Geschwindigkeit achten. Lieber so aufbauen, dass es leicht leserlich ist:

    class NodeImpl {
   int head;
   shared_ptr<Node> tail;

   NodeImpl (int head) : head (head) {}

   NodeImpl (int head, shared_ptr<NodeImpl> tail) : head (head), tail (tail) {}
};

typedef shared_ptr<NodeImpl> Node;

Node node (int head) ( return Node (new NodeImpl(head)); }
Node node (int head, Node tail) ( return Node (new NodeImpl(head, tail)); }

size_t size (Node const & node)
{
   if (node.get() == 0) return 0;
   else return 1 + size (node->tail);
}

    So lassen sich sämmtliche gängige Algorithmen deutlich einfach aufbauen:

    int nth (Node const & node, size_t n)
{
   assert (node.get() != 0);

   if (n == 0) return node->head;
   else return nth (node->tail, n - 1);
}

int last (Node const & node)
{
   if (node->next.get() == 0) return node->head;
   else return last (node->tail);
}

template <typename F>
Node filter (Node const & node, F f)
{
   if (node.get() == 0) return node;
   else 
      if (f (node->head)) return node(node->head, filter (node->tail, f));
      else return filter (node->tail, f);
} 

template <typename M>
Node map (Node const & node, M m)
{
   if (node.get() == 0) return node;
   else return node(m (node->head), map (node->tail, m));
}

...

    Fehlen noch jede Menge standard-Algorithmen, wie Faltung, etc. Aber wie du sieht ist es so extrem einfach sie aufzubauen. Wenn man sie dann alle mal verstanden hat, kannste auch zu einer aufwendigen Listen-Implementation übergehen, die dann effizienter ist.

    0
Anmelden zum Antworten