Suche in einer Linked List

[FireFlow]

Hallo!

Ich habe eine Klasse geschrieben die eine Linked List erstellt. Der Zugriff auf die Elemente der Klasse geht über den [ ] - Operator. Wird ein neues Element eingefügt kommt es immer an die Stelle dass die Liste sortiert (aufsteigend) ist.
Nun meine Frage: Wenn ich auf das letzte Element meiner Liste zugreifen will fängt er beim ersten Element an zu suchen, vergleicht den Index und springt zum nächsten Element bis er es gefunden hat. Gibt es keinen Suchalgorithmus den man auf so Liste anwenden kann?

Achja: Ich hab die Adresse des ersten Elements, wobei jedes Element wiederrum die Adresse des nächsten und vorherigen Elements beinhaltet.

 

[jokey2]

Ineiner sortierten Liste könntest eine binäre Suche machen. Das geht in etwa so:

     int iSearchIndex = list.Maxindex / 2;
     int iInterval = iSearchIndex;
     bool bFound = false;
     while(!bFound)
     {
        iInterval = iInterval / 2;
      if(list[iSearchIndex] == SearchElement)
     	bFound=true;
       else if(list[iSearchIndex] > SearchElement)
     	iSearchIndex -= iInterval
      else // (list[iSearchIndex] < SearchElement)
     	iSearchIndex += iInterval
      }

So ist Dein Suchaufwand nur log und nicht n (n = Anzahl der Elemente in der Liste).

 

[FireFlow]

Ne eine binäre Suche geht nicht da brauch ich ja eben Zugriff auf die Elemente, den hab ich ja nur über die links zwischen den Elementen. Wenn jemand nicht versteht was ich mein, das ganze ist so:

    // Neue Instanz
    dynArray<int> test;

    // Zufälliger Index & Wert
    randomize();
    for(int i=0; i<10; ++i)
        test[rand()%500] = rand()%2000;

    // Debug output
    test.debug_printall();

/* Output:
 
INDEX   ADRESS  VALUE   PREV    NEXT
68      8804548 182     0       8804628
114     8804628 756     8804548 8804568
153     8804568 10      8804628 8804668
248     8804668 1865    8804568 8804688
284     8804688 897     8804668 8804728
319     8804728 1852    8804688 8804648
365     8804648 419     8804728 8804608
441     8804608 629     8804648 8804708
454     8804708 1510    8804608 8804588
468     8804588 1894    8804708 0

*/

Wenn ich nun eingeb zum Beispiel test[441] = 15; dann fängt er erstmal beim Start an (Index 68). Liest dann die Speicheradresse vom nächsten Element und vergleicht den Index dort mit 441 bis er ihn gefunden hat... Ich hab als Startwerte aber eben nur die Adresse vom ersten Element und die vom letzten Element.

 

[MFC openGL]

@FireFlow

Studierst du an der TU WIEN ? denn dort ist momentan eine der Aufgaben GENAU das was du gerade fragst...

Zu deiner Frage : Meiner Meinung nach hast du nur die Möglichkeit das sequenziell durchzugehen, bis du gefunden hast was du suchst, weil du ja nicht weisst wie die adressen der mittleren Elemente ist (oder du machst dafür eine Suchindex liste, sofern du die Liste anlegst, kostet aber reichlich speicher)

 

[FireFlow]

@FireFlow

Studierst du an der TU WIEN ? denn dort ist momentan eine der Aufgaben GENAU das was du gerade fragst...

Zu deiner Frage : Meiner Meinung nach hast du nur die Möglichkeit das sequenziell durchzugehen, bis du gefunden hast was du suchst, weil du ja nicht weisst wie die adressen der mittleren Elemente ist (oder du machst dafür eine Suchindex liste, sofern du die Liste anlegst, kostet aber reichlich speicher)

Nein ich bin nur schüler in der 11ten, aber so nen Studium hab ich noch vor
Trotzdem Danke für die Antwort.