Array list: insert at position

tonic
Neuling
Neuling
Beiträge: 1
Registriert: 19. Sep 2013 01:31

Array list: insert at position

Beitrag von tonic »

Wenn insert at position mit l aufgerufen wird, ist es dann beabsichtigt, dass der einzufügende Key immer an einer Position weiter als l eingefügt wird?
Ganz triviales Beispiel: Ein ArraylistItem, N=5, Array ist mit 4 Items befüllt von 1..4, an Position l=3 soll nun ein neuer key eingefügt werden: Dann tritt Fall 2.3 der Implementation ein und m=3-0+1=4 .... Und der neue Key wird dann an Position p.A[4] eingefügt und nicht an Position 3.... ist das so gewollt oder habe ich einen Denkfehler ?

lkbaerenfaenger
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 13. Mär 2012 12:44

Re: Array list: insert at position

Beitrag von lkbaerenfaenger »

tonic hat geschrieben:Wenn insert at position mit l aufgerufen wird, ist es dann beabsichtigt, dass der einzufügende Key immer an einer Position weiter als l eingefügt wird?
Das hast Du richtig erkannt! Ich habe das auch lange nicht gecheckt! Die Idee ist, dass wenn Du etwas an Stelle l=0 einfügst, wird der Wert am Anfang der Liste gespeichert, also an Position 1. Wenn Du etwas an Stelle l=1 einfügst, wird es dementsprechend an Position 2, also als zweites Element der Liste, gespeichert. Ich weiß nicht, warum man das so lösen sollte, aber es ist auch bei LinkedLists und DoublyLinkedLists so, wenn ich mich recht erinnere... LG

genix
Windoof-User
Windoof-User
Beiträge: 39
Registriert: 16. Okt 2010 13:41

Re: Array list: insert at position

Beitrag von genix »

Weil die Listenpositionen im Wiki bei 1 anfangen und nicht bei 0. Wurde irgendwo am Anfang bei Listen definiert.

sbechtel
Mausschubser
Mausschubser
Beiträge: 56
Registriert: 17. Apr 2013 19:13

Re: Array list: insert at position

Beitrag von sbechtel »

genix hat geschrieben:Weil die Listenpositionen im Wiki bei 1 anfangen und nicht bei 0. Wurde irgendwo am Anfang bei Listen definiert.
Genau, steht bei general infos -> linear sequenz. Eine lineare Sequenz ist eine Abbildung von {1, ..., n} -> V

Assax
Windoof-User
Windoof-User
Beiträge: 41
Registriert: 2. Dez 2011 10:38

Re: Array list: insert at position

Beitrag von Assax »

Ich habe dazu auch noch eine Frage:

Ich gehe die Induction steps grad auf Papier durch.
Angenommen wir haben ein ArraylistItem mit N=5 und n=3, sowie l=3.
Jetzt gilt weder 1: 0+3 < 3 noch gilt 2.2: 3-0 > 3, also folglich nach 2.3: m = 3-0+1 = 4.
Es folgt 2.4, dass von p.n bis m alle Werte im array um eins verschoben werden in dieser Reihenfolge, da m aber 4 ist und p.n = 3 entsteht da doch eine Lücke selbst nach einfügen des neuen Keys?

Angenommen das alte Array war |x|x|x| | | ist nach dem schieben das neue doch |x|x| |x| | und danach |x|x| | |x|.
Nach dem Einfügen dann |x|x| |y|x| ? Soll doch sicher nicht so sein.
Hab ich da was falsch gelesen oder ist das ein Fehler?

robertH
Mausschubser
Mausschubser
Beiträge: 58
Registriert: 29. Apr 2013 13:11

Re: Array list: insert at position

Beitrag von robertH »

In diesem Fall soll eigentlich nichts verschoben werden und der neue Wert einfach an der 4. Stelle eingefügt werden.
Im Punkt 2.4. des Wikis heißt es, dass die Werte von p.n,...,m eine Stelle nach hinten verschoben werden. Dies soll eine absteigende Reihenfolge von Zahlen sein, z.B. 5,4,3. Von hinten im Array bis an die Stelle an der wir einfügen möchten. Wenn dies nicht zutrifft, da p.n wie in diesem Fall kleiner als m ist, soll überhaupt nichts verschoben werden.

Assax
Windoof-User
Windoof-User
Beiträge: 41
Registriert: 2. Dez 2011 10:38

Re: Array list: insert at position

Beitrag von Assax »

Das nichts verschoben werden soll, hab ich beim Durchgehen auf dem Blatt schon gemerkt, nur im Wiki steht halt:
"Otherwise set m = l-sum+1" was in meinem Beispiel dann ja die 4 wäre.
Ab da geht es wenn man den Schritten im Wiki folgt nur noch durcheinander, es sei denn, ich überlese ein ausschlaggebendes Wort.

Da weder 2.1 noch 2.2 eintrifft, muss m.M.n 2.3 ansetzen wo dann m = 4 errechnet wird, was dann im Schritt 2.4 zu dem Chaos führt. :?

Dass in 2.4 alles um eins nach hinten geschoben wird funktioniert ja nur, wenn p.n < m ist im Endeffekt, da die Reihenfolge p.n bis m so eingehalten werden soll.
" Wenn dies nicht zutrifft, da p.n wie in diesem Fall kleiner als m ist, soll überhaupt nichts verschoben werden. "
Genau diese Information fehlt wie ich finde im Eintrag.

Antworten

Zurück zu „Archiv“