Java, kurs Udemy Tim Buchalka

Question

    private static boolean addInOrder(LinkedList<String> linkedList, String newCity) {
        ListIterator<String> stringListIterator = linkedList.listIterator();

        while(stringListIterator.hasNext()) {
            int comparison = stringListIterator.next().compareTo(newCity);
            if(comparison == 0) {
                //equal, do not add
                System.out.println(newCity + "is already included as a destination");
                return false;
            }
            else if(comparison > 0) {
                //new City should appear before this one
                //Brisbane -> Adelaide
                stringListIterator.previous();
                stringListIterator.add(newCity);
                return true;
            }
            else if(comparison < 0) {
                //move on next City
            }
        }

        stringListIterator.add(newCity);
        return true;
    }

Witam, kod ten sprawia, że lista z nazwami miast segreguje się alfabetycznie. Siedzę już nad tym dłuższy czas i nie mogę zrozumieć jak to się dzieję . Wytłumaczyłby to ktoś? :c

Answer 1

Ponieważ w implementacji LinkedList :) występuje naturalny porządek.

Domyślny naturalny porządek wyznaczany jest na obiekcie klasy String, na podstawie metody hash i equals, która jeśli nie jest zdefiniowana przez Ciebie- działa w oparciu o nie samą długość stringu, ale ' naturalny porządek wystąpienia wyrazów w stringu'

http://www.java67.com/2016/02/how-to-sort-linkedlist-in-java-example.html

 

W przypadku innym niż NATURALNY PORZĄDEK

wystarczy zaglądnąc do dokumentacji funkcji   compereTo();  // zwraca nam 3 możliwe wartości

1 LUB -1 LUB 0

 Jej implementacja działa w taki sposób; ( jest on też zależny od obiekt ui wewnętrznej implementacji tej metody, bo np... dla wrapera Integer będa to wartości, dla stringa zależnie albo alfabetyczny dla Linked, albo jeśli  mamy np Set<String> i jest to TreeSet to bedzie to na bazie alfabetycznym, w przeciwnym razie np HashSetu, bedzie to "domyślny' nie dający gwarancji uporządkowania. Linked- daje gwarancje naturalnego porządku

1) Bierze element A i B  jeśli element  A ( np. na bazie Stringa to jego długość ) jest większy od Elementu B

zwróci nam 1

2) jeśli element A jest mniejszy od Elementu B

zwróci nam  -1

 w pozostałym po prostu zwróci 0 .

w ten sposób na bazie liczb tworzona jest kolejność

Comments

Ponieważ w implementacji LinkedList :) występuje naturalny porządek
 

Nieprawda. LinkedList zachowuje kolejność wstawianych elementów a nie naturalny porządek. Zupełnie dwa różne pojęcia. Naturalny porządek to ma TreeSet, czy TreeMap na podstawie kluczy. 

Domyślny naturalny porządek wyznaczany jest na obiekcie klasy String, na podstawie metody hash i equals, która jeśli nie jest zdefiniowana przez Ciebie- działa w oparciu o nie samą długość stringu, ale ' naturalny porządek wystąpienia wyrazów w stringu'

Equals i hashcode nie mają nic wspólnego z tym. O tym decyduje interfejs Comparable i implementacja metody compareTo.

1) Bierze element A i B  jeśli element  A ( np. na bazie Stringa to jego długość ) jest większy od Elementu B

Skoro String ma zaimplementowaną metodę compareTo to porządek będzie alfabetyczny.

 

Co do pytania autora, to ta metoda robi to co napisał Aisekai. Nie widziałem zastosowania jej w kodzie, ale na podstawie samej implementacji tej metody, to jak dla mnie jest ona "dziurawa", bo nie mamy gwarancji, że lista z argumentu jest posortowana, a skoro nie pozwalamy na duplikaty to lepiej wykorzystać TreeSet. 

 

---

Nieprawda. LinkedList zachowuje kolejność wstawianych elementów a nie naturalny porządek

mówimy o sortowaniu kolekcji ... to  jest logiczne, że wstawiająć elementy, masz je w kolejności wstawianej- czytaj dokładnie.  

w implementacji LinkedList :) występuje naturalny porządek 

czego? sortowania... bo o tym tutaj mówimy,  jak również o compareTo bo do tego się odnoszę gdzie jest to porównywanie na bazie naturalnego porządku domyślnej implementacji ...  

Answer 2

Funkcja nie sprawia, że lista segreguje się automatycznie, tylko dodaje łańcuch w odpowiednie miejsce, tak żeby (przy założeniu, że lista jest uporządkowana/posortowana, jeżeli lista nie jest uporządkowana to doda, gdy dany łańcuch będzie "alfabetycznie przed" pierwszym łańcuchem który powinien być przed nim).

compareTo() zwraca pewną liczbę:

"The value 0 if the argument is a string lexicographically equal to this string; a value less than 0 if the argument is a string lexicographically greater than this string; and a value greater than 0 if the argument is a string lexicographically less than this string".

Jeżeli więc comparison będzie równe 0, to wyświetli że:

(newCity + "is already included as a destination")

Jeżeli będzie większe od 0, tzn że String powinien być przed iteratorem, więc wywołuje się najpierw metodę previous() a potem dodaje się newCity.

W przypadku gdy comparison<0 nic się nie dzieje.

W przypadku gdy się okaże, że w liście String powinien być na ostatnim miejscu, doda go poza pętla do-while.