Odwracanie listy

0

Mamy prostą listę:

class Node {
Node next;
int value;
...
}

oraz dostępną w niej metodę:

Node reverse(Node list) {
  // if head is null or only one node, it's reverse of itself.
  if ( (list==null) || (list.next == null) ) return head;

  // reverse the sub-list leaving the head node.
  Node reversed = reverse(list.next);

  // head.next still points to the last element of reversed sub-list.
  // so move the head to end.
  llist.next.next = list;

  // point last node to nil, (get rid of cycles)
  list.next = null;
  return reversed;
}

Dla listy [1, 2]...
metoda reverse wywoływana jest na list.next czyli [2]... następnie wywoływane są jakieś dziwne operacje mianowicie:

  // so move the head to end.
  llist.next.next = list;

  // point last node to nil, (get rid of cycles)
  list.next = null;

następnie metoda zwraca:

return reversed;

Moje pytanie... jak to możliwe, że

  // so move the head to end.
  llist.next.next = list;

  // point last node to nil, (get rid of cycles)
  list.next = null;

mają jakikolwiek wpływ na zmienną reversed? Przecież jest ona ustalona linijkę wcześniej i zwracana na końcu...

Z góry dzięki i pozdro.

0

A czemu te linie mają mieć wpływ na reversed? Reversed to referencja na ostatni Node z wejściowej listy.

0

Chodzi mi bardziej o to, co tu się w Javie dzieje, niż o rekurencję.
Nie rozumiem, w jaki sposób zmienna reversed jest jakkolwiek modyfikowana (dla mnie jest tylko przypisana i zwrócona) i reverse na liście [1 2] powinno dać [2], jednak wynik jest poprawny dla wszelkiej długości listy.

ADMINie: można domerdżować do pytania ;)

0
Shakaz napisał(a):

A czemu te linie mają mieć wpływ na reversed? Reversed to referencja na ostatni Node z wejściowej listy.

Jeśli je zakomentujesz, metoda na liście [1 2] zwróci [2].

0

Jeszcze raz, zmienna reversed nie jest modyfikowana - jest to referencja na ogon listy, która jest przekazywana.
Modyfikowane są jedynie referencje w node'ach na następne elemety. Jeżeli zakomentujesz te linie, to dostaniesz wyłącznie ogon listy, którego następnym elementem będzie null, czyli koniec listy.

0
Shakaz napisał(a):

Jeszcze raz, zmienna reversed nie jest modyfikowana - jest to referencja na ogon listy, która jest przekazywana.

Jak dla mnie reverse dla [2] po prostu zwraca [2] (tzw. base case u samej góry) i jest to przypisane do reversed.
Pomiędzy tym przypisaniem a zwróceniem wartości przez funkcję... dzieje się coś dla mnie niezrozumiałego.
Modufikowane jest argument... i dalej nie wiem dlaczego to wpływa na tę zmienną, więc proszę może rozwiń myśl 'referencji na ogon listy'.

0

Masz 3 node'y:
[Head]->[1]->[Tail]->null

Podczas wywołania reverse, metoda rekurencyjnie dochodzi do przypadku, gdzie list(aczkolwiek tutaj argument powinien nazywać się head) jest null, lub następny element tego node jest nullem.
Patrząc na schemat node'ów powyżej widać, że node [Tail] ma jeden z tych warunków spełniony, tj. jego następny element next jest nullem. W takim razie wychodzimy z metody i w zmiennej reversed mamy referencję na node [Tail]. Jak już wcześniej wspomniałem, zmienna reversed nie jest nigdzie modyfikowana, w takim razie w każdym wywołaniu metody referencja reversed wskazuje zawsze na Tail, nie ważne ile jest elementów w tej liście. Teraz jest właśnie sytuacja, gdzie miałbyś zakomentowane wspomniane przez Ciebie linijki, czyli jako wynik metody dostałbyś [Tail] z następnym elementem ustawionym na null.

Następnie, po wyjściu z reverse z agumentem [Tail], jesteśmy w node [1]. Mamy linijkę list(head).next.next, patrzymy na schemacik na początku postu - następny element po [1] i znowu następny element, czyli po [Tail] ustawiamy na list(head), czyli na aktualny node, w którym jesteśmy(w tym przypadku [1]). Ostatnia linijka to ustawienie następnego elementu bieżącego node'a na null, żeby już nie wskazywał na [Tail].
I cały cykl w kółko aż do [Head].

Teraz, Twoje pytanie brzmi: Jak jest modyfikowana zmienna reversed? Otóż zmienna reversed nie jest modyfikowana, ale jest modyfikowany obiekt, na który wskazuje, czyli [Tail]. Zmienna reversed wskazuje zawsze na to samo.

Do nadrobienia: http://stackoverflow.com/questions/40480/is-java-pass-by-reference-or-pass-by-value

0

Długo wiedziałem, że Java jest pass by value... Rozumiem to tak, że po przekazaniu obiektu do metody jego referencja nie jest już istotna; można natomiast manipulować jego pola (co ma tu miejsce poprzez .next).
Jeśli się pomyliłem, to proszę mnie poprawić.

Potrzebowałem jeszcze raz przejść przez te podstawy.
Sporo do zrozumienia dało mi to: http://stackoverflow.com/questions/869033/how-do-i-copy-an-object-in-java.

1 użytkowników online, w tym zalogowanych: 0, gości: 1