Wstęp

Chain

Dzień dobry!

Chłodny, zimowy dzień w Państwie na Wisłą pora przywitać porządną dawką wiedzy. Dzisiaj weźmiemy na tapetę jedno z częstych pytań rekrutacyjnych, jakie możecie spotkać na rozmowach technicznych. Mowa o listach połączonych, lub jak ktoś woli – LinkedList’ach. Zaczynamy! 🚀

Trochę teorii

Najpierw trochę teorii na temat samych list. Otóż lista (liniowa, połączona, ang. linked list) to nic innego jak struktura danych, która służy do reprezentacji zbiorów danego typu, w której elementy (node) są ułożone w porządku liniowym. Listy te można podzielić na listy jednokierunkowe oraz dwukierunkowe.

Jak zapewne łatwo się domyślasz, jednokierunkowe działają w jedną, a te drugie w dwie strony. Odkrywcze, brawo ja 👏. Koncepcją list liniowych jest możliwość przechodzenia (wskazywania) następnego elementu listy, lub – jak w przypadku list dwukierunkowych – również elementu poprzedzającego. To dokładnie jak w przypadku łańcucha – każde ogniwo wie jedynie o isteniniu swojego poprzedniego ogniwa oraz następnego po nim.

LinkedList - schema

Za początek naszej listy odpowiada głowa (head), która jest pierszym elementem listy, oraz ogon (tail), czyli node ostatni.

LinkedList schema

Ok, założenia wydają się zrozumiałem, nie ma tutaj nic więcej. Czas zatem przejść do mięsa, czyli piszemy implementację, oczywiście, w Swift 🧡.

Implementacja

Jak wspomniałem wcześniej, każda lista składa się z elementów, zwanych node’ami. Na elementy te składają się przynajmniej dwa (a w przypadku listy dwukierunkowej – trzy) pola, którymi są kolejno: wartość, wskaźnik następnego elementu (oraz wskaźnik poprzedniego elementu).

Wobec tego najpierw tworzymy instancję Node.

NOTE: Ponieważ nasz obiekt będzie przetrzymywał referencję do innego obiektu typu Node, musi być on typem referencyjnym (class). W ten sposób zapobiegamy rekurencjnemu przypisaniu wartości tego samego typu.

class Node<T> { }

I dodajemy element wartości.

class Node<T> {
    var value: T
            
    init(value: T) {
        self.value = value
    }
}

Jak widzisz, od razu określam klasę Node jako generyczną, gdyż chce móc dodawać do listy objekty różnych typów, a więc nie chce pisać oddzielnej implementacji dla list z elementami typu String, Int itp.

Kolejny etap to dodanie kolejnego elementu z listy. Zastanówmy się nad pytaniem z początku tego wpisu – czy kolejny element zawsze będzie istniał? No… oczywiście że nie 🛑. Np. w przypadku, gdy dany node jest ostatnim w łańcuchu. Zatem zarówno kolejny jak i poprzedni element będzie wartością opcjonalną.

var previous: Node?
var next: Node?

W powyższym kodzie jest jeden, dość poważny błąd. Otóż wyobraźmy sobie przykłąd, w którym Node_1 wskazuje swojego następcę, Node_2. W tym samym momencie Node_2 będzie wskazywał silną referencję do Node_1. Zachodzi coś, co w programowaniu nazywamy z angielska ownership cycles. To sytuacja, kiedy po usunięciu jednego z node’ów, drugi dalej będzie posiadał silną referencję do tego pierwszego, co skutkuje wyciekiem pamięci. Zatem od razu poprawiam kod, przekazując referencję typu weak do node’a poprzedzającego:

class Node<T> {
    var value: T
    weak var previous: Node?
    var next: Node?
            
    init(value: T) {
        self.value = value
    }
}

Ok, mamy już stworzone elementy naszej listy. Czas na samą listę 😅:

class LinkedList<T> {
    private var head: Node<T>?
    private var tail: Node<T>?
}

Hm… jeśli pierwszy raz pracujesz z algorytmem LinkedList’y, to teraz zapewne zastanawiasz się – gdzie jest reszta Node’ów? Czemu mamy tylko pierwszy i ostatni? No właśnie… otóż informacje o następnym i kolejnym elemencie są przechowywane w samych node’ach! To one posiadają informację, czy w łańcuchu jest więcej elementów, czy nie.

No dobrze, po kolei 🤓. Najpierw stwórzmy gettery dla pierwszego oraz ostatniego node’a, oraz zmienna wyliczeniową sprawdzającą, czy nasza lista w ogóle ma jakieś elementy:

class LinkedList<T> {
    private var head: Node<T>?
    private var tail: Node<T>?
            
    var first: Node<T>? {
        return head
    }
            
    var last: Node<T>? {
        return tail
    }
            
    var isEmpty: Bool {
        return head == nil
    }
}

Mamy to 😎. Chwila wytchnienia, radość z dotychczasowego dokonania, i zaraz lecimy dalej. Czas zacząć dodawać elementy do listy…

Dodawanie elementów

Teraz ta ciekawa część implementacji algorytmu list połączonych, czyli dodawanie kolejnych elementów do listy. Na razie nasz kod nie posiada żadnej zmiennej, która ma publiczny setter. I słusznie, bo nie chcemy żeby ktoś próbował samodzielnie przypisać jakieś zmienne np. do pierwszego elementu bez naszej kontroli. Napiszemy więc samodzielnie metodę append, przyjmującą jako parametr obiekt danego typu generycznego T. Następnie metoda sprawdzi, czy:

  • IF Posiadamy już jakiś ostatni element w liście?
    Jeśli tak, to przypiszmy nowy element to wartości tail, obecny ogon będzie teraz poprzednim elementem nowej wartości, zaś wartością next starego ogona będzie nowa wartość.
  • ELSE Nie posiadamy ostatniego elementu, co oznacza tymsamym, że nie posiadamy żadnego.
    Zatem nowy element staje się jednocześnie głową i ogonem.
  • FINALLYZawsze nowy element staje się ogonem.

Implementacja powyższych założeń będzie wyglądać następująco:

func append(value: T) {
    let node = Node<T>(value: value)
    // IF
    if let lastNode = tail {
        node.previous = tail
        lastNode.next = node
    }
    // ELSE
    else {
        head = node
    }
    // FINALLY
    tail = node
}

Ok, zróbmy namacalny test i spróbujmy stworzyć LinkedList’ę z elementami typu String, a potem ją wyświetlmy na konsoli:

let fruits = LinkedList<String>()
fruits.append(value: "Apple")
fruits.append(value: "Banana")
fruits.append(value: "Orange")
        
print(fruits) // __lldb_expr_3.LinkedList<Swift.String>

Aha… 🧐 No to nie jest zbyt pomocne. Musimy zatem sami napisać jakiegoś toString’a, który wyświetli nam to co mamy zapisane w naszej liście. Let’s do that 🏋️‍:

var printable: String{
    guard !isEmpty else {
        return "List is empty"
    }
            
    var text = ""
    var node = head
            
    while node != nil {
        text += "\(node!.">value)"
        node = node?.next
                
        if node != nil {
            text += ", "
        }
    }
    return text
}
    
let fruits = LinkedList<String>()
fruits.append(value: "Apple")
fruits.append(value: "Banana")
fruits.append(value: "Orange")

NOTE: Ogólnie ładnie byłoby zrobić to z użyciem protokołu CustomStringConvertible. Dla chcących 👉 odnośnik na dole strony w sekcji “Dla dociekliwych”.

Kolejny etap za nami. Lecimy dalej 🦅.

Dostęp do elementu

Skoro nie przechowujemy całej listy (jak w przypadku tablic), a bazujemy jedynie na wiedzy jednego elementu o drugim (i odwrotnie w przypadku list dwukierunkowych), to w jaki sposób znaleźć element na miejscu x? 🤔…

Pomyślmy, co musimy zaimplementować:

  • Medotę, która przyjmuje watości (index) typu Int.
  • Wartość nie może być ujemna.
  • Musimy sprawdzać kolejne elementy, zaczynając od pierwszego (head) i przesuwając się po elementach next jednocześnie dekrementować nasz licznik.

Done 👍. Założenia poczynione, teraz do kodu:

func node(at index: Int) -> Node<T>? {
    guard index >= 0 else { return nil }
    var node = head
    var localIndex = index
            
    while node != nil {
        if localIndex == 0 {
            return node
        }
                
        localIndex -= 1
        node = node!.next
    }
    return nil
}

Nasz kod spełnia warunki, które założyliśmy wcześniej. Super. Sprawdzam to behawioralnie, czyli printuje na ekran:

let fruits = LinkedList<String>()
fruits.append(value: "Apple")
fruits.append(value: "Banana")
fruits.append(value: "Orange")
        
print(fruits.node(at: 0)?.value) // Optional("Apple")
print(fruits.node(at: 1)?.value) // Optional("Banana")
print(fruits.node(at: 6)?.value) // nil

Bajka. Wszystko działa jak należy. Została nam już tylko jedna rzecz i jesteśmy w domu 😁.

Usuwanie elementów listy

Ostatnią rzeczą, na jaką powinniśmy zwrócić uwagę jest usuwanie elementów listy. Oczywiście mamy tutaj dwa scenariusze:

  • Kiedy chcemy usunąć całą listę
  • Kiedy chcemy usunąć konkretny element

W przypadku #1 nie ma większej filozofii. Skoro bazujemy tylko na informacjach elementów względem siebie, wystarczy że usuniemy pierwszy i ostatni element listy. Inne również zostaną wyrzucone z pamięci, bo zadbaliśmy o to dodając słabą referencję między obiektami. Zatem:

func removeAll() {
    head = nil
    tail = nil
}

I już. Teraz drugi przykład, w którym tak prosto nie będzie 😢. Znowu musimy rozważyć pewne przypadki, bo pamiętamy że nasza lista posiada początek i koniec, zatem przy usunięciu danego elementu trzeba będzie aktualizować informację o poprzednim i następnym elementcie w liście. Przypadek usunięcia pierwszego i ostatniego node’a jest prostszy, bo bazuje na przypisaniu nowych wartości końcowych. W przypadku usunięcia node’a pośredniego, musimy zaktualizować dwie informacje.

Removing Node

Removing tail node

Removing middle node

Impementacja metody remove(at: Int) będzie zatem wyglądała następująco:

func remove(at index: Int) {
    guard let node = node(at: index) else { return }
    let previous = node.previous
    let next = node.next
            
    if let previous = previous {
        previous.next = next
    } else {
        head = next
    }
            
    next?.previous = previous
            
    if next == nil {
        tail = previous
    }
            
    node.previous = nil
    node.next = nil
}

Efekt:

let fruits = LinkedList<String>()
fruits.append(value: "Apple")
fruits.append(value: "Banana")
fruits.append(value: "Orange")
        
fruits.remove(at: 1)
print(fruits.node(at: 1)?.value) // Optional("Orange")
print(fruits.printable) // Apple, Orange

JEST 👏😁 Działa pięknie. Całość zaimplementowana.

Testy jednostkowe

Jak przystało na dobrych praktyków – trzeba napisać testy. Nie będziemy przecież pisali printów do naszych klas, bez partyzantki. Możemy przecież napisać choćby proste testy jednostkowe, więc zróbmy to żeby być pewnymi, że wszystko działa jak należy.

// UNIT TESTS
class LinkedListTests: XCTestCase {
    var list: LinkedList<String>!
            
    override func setUp() {
        super.setUp()
        list = LinkedList<String>()
        list.append(value: "Ford")
        list.append(value: "Tesla")
        list.append(value: "BMW")
    }
            
    func testNodeAt() {
        // Node at
        XCTAssertEqual(list.node(at: 1)?.value, "Tesla")
        XCTAssertNil(list.node(at: 6))
    }
            
    func testRemoveNodeAt() {
        list.remove(at: 0)
        XCTAssertEqual(list.node(at: 0)?.value, "Tesla")
    }
            
    func testRemoveAll() {
        list.removeAll()
        XCTAssertNil(list.node(at: 0))
    }
            
    override func tearDown() {
        list = nil
    }
}
        
// Run Unit tests
LinkedListTests.defaultTestSuite.run()

Teraz już mamy pewność ➡️ Executed 3 tests, with 0 failures (0 unexpected) in 0.074 (0.076) seconds.

Podsumowanie

To już wszystko na dzisiaj. Dziękuję że dotarłeś ze mną do końca, mam nadzieję że temat udało mi się opisać dosyć szeroko. Jak zawsze bardzo mile widziany jest feedback w komentarzu lub gdzieś na social mediach. Jeżeli chciałbyś przeczytać o czymś konkretnym na tym blogu to również daj znać w komentarzu pod tym postem, jaki temat warto byłoby poruszyć.

Jeszcze raz dzięki i do następnego!

@jkornat

Extras

Nowość w zestawieniu – linki z pogłębionymi teamtami, na które nie było miejsca w tekście 😎. Bierzcie i czerpcie!

Dla dociekliwych:

Kod źródłowy

Kod źródłowy napisany na potrzeby tego wpisu znajduje się pod tym adresem na GitHub’ie.

Struktura listy połączonej – czyli linked listy w Swift

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *