Datenstrukturen

[Susi123]

Ich habe ein Array A und eine einfach verkettete Liste ungerader Länge n (gegeben für das Array, noch unbekannt für die Liste). Ich soll auf das Element in der Mitte zugreifen und feststellen, wie viele Elemente ich besuchen muss, um darauf zugreifen zu können
a) Array A?
b) Liste L?

Leider bin ich völlig planlos, wie ich die Aufgabe angehen könnte. Als Hinweis bekomme ich, dass mehrfache Bsuche des selben Elementes natürlich zu dieser Aufwandsabschätzung dazu zählen.

Ich habe mir schon mal überlegt, dass sich die Mitte folgendermaßen finden lässt: Anzahl der Elemente geteilt durch 2 und danach aufrunden auf die nächste ganze Zahl. Gehört das zu Array oder Liste?

Eine andere Möglichkeit wäre das zweite Element zu streichen und dann das zweite+2 Schritte. Bin ich am Ende der Liste müsste ich wieder bei der kleinsten Zahl beginnen.

 

[Ullenboom]

Es könnte bei der Aufgabe darum gehen, dass du bei Arrays wahlfreien Zugriff hast, auf verkette Listen aber nicht. Bei Arrays kannst du direkt auf array[array.length/2] zugreifen, bei der Liste musst du n/2 Schritte vom Anfang an in die Mitte laufen. Zusammengefasst: Bei Arrays besuchst du keine vorherigen Elemente, bei verketten Listen schon.

 

[mihe7]

Anzahl der Elemente geteilt durch 2 und danach aufrunden auf die nächste ganze Zahl. Gehört das zu Array oder Liste?

Ein Array erlaubt den wahlfreien Zugriff, Du kannst also direkt auf eine gewünschte Stelle im Array zugreifen. Demnach gehört das zum Array. Deine Berechnung stimmt aber nicht. Der Index des ersten Elements ist 0. Hast Du 3 Elemente im Array, liefert Dir die ganzzahlige Division der Anzahl der Elemente durch 2: (3/2) = 1. Und 1 ist das zweite, also das mittlere Element.

Bei der verketteten Liste, musst Du ggf. erstmal feststellen, wie viel Elemente gespeichert sind, um Dich dann erneut durch die Liste zu hangeln.

 

[Ullenboom]

@mihe7 hat einen guten Punkt: Wenn man nicht weiß, wie groß die Liste ist, wird es deutlich teurer. Dann hat du erst einmal lineare Laufzeit für das herausfinden, und du musst noch zusätzlich n/2 Schritte gehen. Das ist der Grund, warum eine java.util.LinkedList die Länge wirklich intern ablegt ...

 

[insanezulu]

Btw. da eine einfach verkettete Liste keinen wahlfreien Zugriff bietet, und wenn "die Mitte" nicht als Zeiger gespeichert ist, dann bleibt dir nichts anderes übrig, als durch die ganze oder halbe Liste zu laufen... (pro Operation...)
1000 Elemente in den hinteren Bereich einfügen würde also 1000*1000/2=500.000 "Anweisungen" kosten.

 

[Susi123]

Also zusammenfassend könnte man das dann so sagen:
a) Array: Zugriff ist auf die gewünschte Stelle direktmöglich. Vorgang: ganzzahlige Division der Anzahl der Elemente durch 2, sodass man auf das mittlere Element kommt.
b) Liste: mehrfaches Durchhangeln. Man benötigt folgende Anzahl an Schritte: Anzahl der Elemente geteilt durch 2.

Wie ist der Ablauf mit der Liste dann genau, wenn man es darstellen möchte? Das ist mir noch nicht ganz klar.
Sorry, bin leider noch absoluter Anfänger.

 

[kneitzel]

Also wenn die Anzahl der Elemente in der Liste nicht bekannt ist, dann benötigst du das 1,5 fache:
1. Musst Du ja die Anzahl ermitteln, so dass du einmal komplett durch gehen musst.
2. musst du zum n/2 Element, so dass du erneut n/2 Elemente durch gehen musst.

Und um eine Vorstellung zu bekommen:
Stell Dir die Liste als ein Zug vor. Und die Verbindung von einem Wagon zum anderen kannst du auch nur von vorn nach hinten gehen bei einfach verketteten Wagons.
Du hast nun einen Zug, dessen Länge Du nicht kennst. Also läufst du erst einmal durch und zählst die Wagons.
Wenn du dann weißt, wie viele Wagons der Zug hat kannst du erneut von vorne durchlaufen, bis Du im gewünschten Wagon angekommen bist.
(Der Vergleich hakt etwas. Du kannst halt gewisse Punkte markieren und dich da hin Beamen lassen ... also hier kannst du dich immer zum Kopf des Zuges Beamen lassen. Diese gemerkten Positionen sind halt Referenzen, die in Variablen gespeichert sind.)

 

[Susi123]

Vielen Dank für die hilfreichen Erklärungen. Jetzt habe ich es auch verstanden.