0

Struktury danych: Lista – Strefa Juniora

Cześć! Dzisiaj przedstawię prostą implementację struktury danych tzw. listy. Ale chwila. Przecież do miał być dział algorytmów? Zgadza się. Jednak nie można analizować bardziej złożonych algorytmów nie znając podstawowych struktur danych.

Zdaję sobie sprawę, że lista jest raczej banalną strukturą, ale nie chcę od razu wystrzelić z drzewem binarnym, czy grafem. Mam na uwadze, że wpis ten też mogą czytać osoby dopiero zaczynające. Jeżeli jesteś taką osobą, to na pewno przyda Ci się informacja o tym jak taka lista działa i czym różni się od np. tablicy.

Właśnie, dlaczego nie zacząłem od tablicy? Piszę w języku C#, tutaj implementacja tablicy byłaby chyba wyzwaniem 😉, jest za wysokopoziomowy. W języku C++ wykorzystując wskaźniki, taka implementacja miała by sens. Nie chciałem za bardzo kombinować, dlatego zaczynam od listy.

Wpis ten zawiera informacje pomocne dla osoby zaczynającej swoją przygodę z programowaniem. Jeżeli jesteś taką osobą, to koniecznie odwiedź dział juniora.
Cały kod użyty w tym przykładzie znajduje się również na GitHubie.
Implementacja tutaj przedstawiona ma na celu tylko dydaktykę. Nigdy nie używaj tej implementacji w kodzie produkcyjnym. W standardowych bibliotekach znajduje się klasa List<T>, której powinieneś używać.

Definicja listy

Zacznijmy może od definicji. Czym jest ta lista? Hmm… Jest to bardziej rozbudowana tablica albo inaczej, kontener zawierający elementy w jakiejś określonej kolejności. To chyba najogólniejsza definicja. Na pewno jest przyjemniejsza w użyciu niżeli tablica, wystawia więcej metod, no i najważniejsze: dodawanie do niej elementów jest optymalniejsze niżeli w tablicy.

Tablica z definicji ma stały rozmiar (pojemność), lista z kolei swoją pojemność dostosowuje w zależności od zapotrzebowania. Tak naprawdę, implementacja listy, wykorzystuje w środku tablicę, jednak opakowuje ją tak, że my jako użytkownicy tej listy, nie musimy się martwić o zmiany rozmiaru, przesuwanie elementów przy usuwaniu itp.

Podstawowym typem tablicy jest tablica jednokierunkowa. Oznacza to, że z elementu 1 możemy przejść do elementu 2, ale z elementu 2 nie możemy przejść do elementu 1.

Zmienna pojemność listy

Wspomniałem wcześniej, że lista posiada zmienną pojemność. Jak to działa? Załóżmy, że na początku umieszczamy w liście 5 elementów, a jej pojemność algorytm ustawia na 8 (potęga dwójki, ale to bez znaczenia dla przykładu). Teraz bez zmiany rozmiaru możemy dodać 3 elementy do listy.

Jeżeli następuje dodanie nowego elementu, to trzeba zwiększyć rozmiar listy. Wewnętrzna tablica ustawiana jest na powiedzmy 2*8 (2 razy większa pojemność niż wcześniej), a stara zawartość tablicy jest kopiowana do nowej tablicy. Teraz lista posiada pojemność 16 elementów.

Co istotne, rzadko spotyka się rozwiązania, że lista zmniejsza swoja pojemność. Mam tutaj na myśli sytuację usuwania elementów. Jeżeli lista miała 100 elementów, a jej pojemność wynosiła 124, to gdy usuniemy 99 elementów, jej pojemność prawdopodobnie się nie zmieni. Co skutkuje tym, że w pamięci list będzie zajmowała tyle samo co wcześniej.

Implementacja List w C#

Zaproponuję tutaj prostą implementację, która będzie zawierała tylko podstawowe metody listy. Dodatkowo dla uproszczenia (z myślą o Juniorach) nie będzie to lista generyczna.

Nie chcę się rozczulać nad tak prostą strukturą danych. Chcę tylko, abyś zrozumiał co dzieje się „w środku”.

Jeżeli moja implementacja to dla Ciebie za mało, to polecam przeczytać kod implementacja List<T>.

Zaimplementowałem klasę ListInt o takim interfejsie:

+ListInt()
+ListInt(IEnumerable<int>)
+Count : int
+Capacity : int
+Add(int) : void
+Insert(int,int) : void
+Contains(int) : bool
+IndexOf(int) : int
+Remove(int) : void
+RemoveAt(int) : void
+[int] get,set

Testy

Oczywiście, najpierw napisałem kilka testów jednostkowych sprawdzających działanie klasy. Testy nie testują wszystkich scenariuszy. Nie chciałem za bardzo kompilować implementacji. Sprawdzane jest tylko bardzo podstawowe działanie. Kod prezentuje się następująco:

[TestMethod]
public void ListInt_Ctors()
{
    Assert.AreEqual(0, new ListInt().Count);
    Assert.AreEqual(2, new ListInt(new int[] { 1, 2 }).Count);
}
 
[TestMethod]
public void ListInt_Index()
{
    ListInt list = new ListInt(new int[] { 1, 2 });
    Assert.AreEqual(1, list[0]);
    Assert.AreEqual(2, list[1]);
    list[0] = 3;
    list[1] = 4;
    Assert.AreEqual(3, list[0]);
    Assert.AreEqual(4, list[1]);
}
 
[TestMethod]
public void ListInt_Add()
{
    ListInt list = new ListInt();
    list.Add(1);
    list.Add(2);
    Assert.AreEqual(2, list.Count);
    Assert.AreEqual(1, list[0]);
    Assert.AreEqual(2, list[1]);
}
 
[TestMethod]
public void ListInt_Insert()
{
    ListInt list = new ListInt(new int[] { 1 });
    list.Insert(2, 0);
    Assert.AreEqual(2, list.Count);
    Assert.AreEqual(2, list[0]);
    Assert.AreEqual(1, list[1]);
}
 
[TestMethod]
public void ListInt_Contains()
{
    ListInt list = new ListInt(new int[] { 1, 2 });
    Assert.IsTrue(list.Contains(1));
    Assert.IsTrue(list.Contains(2));
    Assert.IsFalse(list.Contains(3));
}
 
[TestMethod]
public void ListInt_IndexOf()
{
    ListInt list = new ListInt(new int[] { 1, 2 });
    Assert.AreEqual(0, list.IndexOf(1));
    Assert.AreEqual(1, list.IndexOf(2));
}
 
[TestMethod]
public void ListInt_Remove()
{
    ListInt list = new ListInt(new int[] { 1, 2 });
    list.Remove(1);
    list.Remove(2);
    Assert.AreEqual(0, list.Count);
}
 
[TestMethod]
public void ListInt_RemoveAt()
{
    ListInt list = new ListInt(new int[] { 1, 2 });
    list.RemoveAt(1);
    Assert.AreEqual(1, list.Count);
    Assert.AreEqual(1, list[0]);
}
 
[TestMethod]
public void ListInt_Resize()
{
    ListInt list = new ListInt();
    for (int i = 0; i < 1024; i++)
    {
        list.Add(i);
    }
    Assert.AreEqual(1024, list.Count);
}

Implementacja ListInt

Kod starałem się napisać w miarę czytelnie, dlatego nie zawiera komentarzy. Przedstawię cały kod, a później omówię co ciekawsze elementy. Kod wygląda tak:

public class ListInt : IEnumerable<int>
{
    private int[] _values;
 
    public int Count { get; private set; }
    public int Capacity { get; private set; }
 
    public ListInt()
    {
        Capacity = 64;
        _values = new int[Capacity];
        Count = 0;
    }
 
    public ListInt(IEnumerable<int> values)
    {
        if (values == null)
        {
            throw new ArgumentNullException(nameof(values));
        }
        Capacity = values.Count() * 2;
        _values = new int[Capacity];
        (values as int[]).CopyTo(_values, 0);
        Count = values.Count();
    }
 
    public void Add(int value)
    {
        EnsureSize(Count + 1);
        _values[Count] = value;
        Count++;
    }
 
    public void Insert(int value, int index)
    {
        EnsureSize(Count + 1);
        if (index < Count)
        {
            Array.Copy(_values, index, _values, index + 1, Count - index);
        }
        _values[index] = value;
        Count++;
    }
 
    public bool Contains(int value)
    {
        for (int i = 0; i < Count; ++i)
        {
            if (_values[i] == value)
            {
                return true;
            }
        }
        return false;
    }
 
    public int IndexOf(int value)
    {
        for (int i = 0; i < Count; ++i)
        {
            if (_values[i] == value)
            {
                return i;
            }
        }
        return -1;
    }
 
    public void Remove(int value)
    {
        int index = IndexOf(value);
        if (index >= 0)
        {
            RemoveAt(index);
        }
    }
 
    public void RemoveAt(int index)
    {
        if (index < 0 || index >= Count)
        {
            throw new ArgumentOutOfRangeException();
        }
        Count--;
        if (index < Count)
        {
            Array.Copy(_values, index + 1, _values, index, Count - index);
        }
        _values[Count] = 0;
    }
 
    public int this[int index]
    {
        get
        {
            if (index < 0 || index >= Capacity)
            {
                throw new ArgumentOutOfRangeException();
            }
            return _values[index];
        }
        set
        {
            if (index < 0 || index >= Capacity)
            {
                throw new ArgumentOutOfRangeException();
            }
            _values[index] = value;
        }
    }
 
    public IEnumerator<int> GetEnumerator()
    {
        return (_values as IEnumerable<int>).GetEnumerator();
    }
 
    IEnumerator IEnumerable.GetEnumerator()
    {
        return _values.GetEnumerator();
    }
 
    private void EnsureSize(int size)
    {
        if (Capacity < size)
        {
            Capacity *= 2;
            int[] old = _values;
            _values = new int[Capacity];
            old.CopyTo(_values, 0);
        }
    }
}

Omówienie implementacji ListInt

Zmienne i konstruktory

Na samym początku mamy property Count i Capacity. Nie są one zbytnio interesujące, informują po prostu o stanie listy. W pierwszych liniach znajduje się również definicja _values. Jest to serce listy tj. tablica elementów, na której będziemy pracować.

Konstruktory są równie nudne. Następuje tam jedynie odpowiednie ustawienie wartości. W przypadku pustego konstruktora, przyjąłem Capacity na 64 (bez większego powodu), w drugim przypadku Capacity ustawiam na wartość dwukrotnie większą niż aktualna liczba elementów – powinienem użyć jakiejś potęgi dwójki, ale nie chciałem Ci zbytnio komplikować.

Dodawanie nowych elementów

Funkcja Add(int value) ma za zadanie dodać element do tablicy. Dodaje zawsze na końcu. Na koniec wskazuje property Count. W pierwszej linii tej funkcji wołana jest funkcja EnsureSize, która dba o to, aby wewnętrzna tablica zawsze miała miejsce na nowe dane. Funkcja ta sprawdza, czy pojemność jest wystarczająca. Jeżeli nie jest, to zwiększa ją dwukrotnie – alokuje tablicę o dwukrotnie większej pojemności – a aktualne dane kopiuje do nowego miejsca.

Następnie mamy funkcję Insert. Funkcja ta jest bardziej złożona od Add. Oczywiście na początku trzeba sprawdzić pojemność tablicy, ale to już powinno być dla Ciebie zrozumiałe. Następnie sprawdzany jest ważny warunek. Jeżeli nowo dodawany element nie znajduje się na końcu, to trzeba zrobić mu miejsce w tablicy nie nadpisując danych. Robione jest to za pomocą funkcji Array.Copy, która to przesuwa wszystkie elementy – począwszy od indeksu, gdzie będzie wstawiany nowy element – o jeden do przodu. W wolne miejsce wskakuje nowy element.

Przeszukiwanie elementów

Funkcje Contains i IndexOf są bardzo podobne i chyba dosyć proste. Enumeruję się po wszystkich elementach tablicy i sprawdzam czy aktualny element jest identyczny z poszukiwanym. Tutaj zauważ proszę, że nie enumeruję się wykorzystując pętlę foreach, tylko pętlę for z warunkiem granicznym i < Count. Powodem jest to, że tablica w rzeczywistości może posiadać dużo więcej elementów (ma zarezerwowane miejsce na nowe elementy), ale z punktu widzenia użytkownika one „nie istnieją” (w tym przykładzie będą miały wartość 0).

Usuwanie elementów

Funkcja Remove wykorzystuje tak naprawdę funkcję IndexOf i przekazuje sterowanie do RemoveAt. To na tej funkcji się skupię. Jest ona podobna do wcześniejszej funkcji Insert, tyle, że działa w drugą stronę. Jeżeli usuwany element nie jest elementem na końcu, to trzeba „skurczyć” tabelę. Robione jest to za pomocą funkcji Array.Copy, która tym razem przesuwa elementy w lewo (począwszy od indeksu). Skutkuje to tym, że usuwany element został nadpisany elementem występującym po nim.

Pozostałe

Funkcja this[int index] umożliwia dostęp do elementów za pomocą wywołania list[index]. Nie jest ona szczególnie ciekawa.

Funkcje zwracające enumeratory też są raczej standardowe. Przekazują one enumeratory z wewnętrznej listy.

Podsumowanie

Zaprezentowany kod zdaje założone testy jednostkowe. Jest to kod bardzo okrojony, ponieważ w rzeczywistości interfejs listy jest znacznie większy. Zależało mi jedynie na tym, abyś pojął jak działa lista.

I jak działa? Zapewne zauważyłeś, że dodawanie elementów do listy jest bardzo szybkie. W prawdzie trzeba czasami zmienić rozmiar, ale dzięki założeniu, że zawsze zwiększamy dwukrotnie, daje to dobry “zapas”.

Faktycznie dodawanie jest szybkie, jednak usuwanie albo wstawianie w jakieś miejsce (nie na końcu) wymaga już zmieniania wewnętrznej struktury elementów. W obecnych czasach nie jest to jakoś bolesne, chyba, że pracujesz w środowisku, gdzie masz bardzo ograniczone zasoby. Jednak wtedy nie piszesz w C#, ale bardziej w C 😉.

Teraz już wiesz, jak działają listy. Czym się różnią od tablic. Czy są to ważne informacje? Może i nie, na pewno warto to wiedzieć. Stanowi to też dobry wstęp do bardziej złożonych struktur danych.

Pozdro!

 

Patryk Bogdański

Dodaj komentarz

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.