<p>Nie będzie żadnych zaskoczeń, wybuchów i zwrotów akcji. Tablica to podstawowa struktura danych dostępna praktycznie w każdym języku programowania. Tym samym powinna być wszystkim doskonale znana :). Niemniej myślę, że warto usystematyzować informacje na jej temat.</p>
<p><b>Krótka charakterystyka:</b></p>
<p>Tablica może przechowywać określoną liczbę elementów, z których wszystkie są tego samego typu. Do każdego elementu można się odwołać poprzez indeks, który reprezentuje adres elementu w tablicy (nie mylić z adresem w pamięci :)) Oczywiście indeks pierwszego elementu tablicy jest równy 0. Mówiąc, że tablica może przechowywać określoną liczbę elementów, mam na myśli to żenie da się zmienić rozmiaru tablicy jako takiej – w niektórych rodzajach tablic zmiana rozmiaru w czasie działania programu jest dla użytkownika możliwa, nie zmienia to jednak faktu, że pod maską tworzona jest nowa tablica, o nowym rozmiarze, i do której są kopiowane elementy starej tablicy. Także trzeba mieć to na uwadze – jak można się domyślić taka operacja kosztuje czas.</p>
<img src="/static/img/blog/arrayrep-1.png" alt="" class=" postImage" />
<p><b>Reprezentacja tablicy w pamięci komputera</b></p>
<p>Powyższy obrazek ilustruje sposób w jaki można wyobrażać sobie tablice w pamięci komputera. Traktując to szare coś jako pamięć, łatwo można zrozumieć, że elementy tablicy zajmują miejsca obok siebie i mają stały rozmiar (są w końcu tego samego typu). </p>
<p><b>Podstawowe operacje i ich wydajność:</b></p>
<ul>
<li><b><i>Dostęp do elementu:</i></b> Do elementu tablicy można dostać się bardzo szybko (O(c)). Przyczyną takiego stanu rzeczy jest to, że kolejne komórki zajmują miejsca obok siebie, tym samym znając rozmiar typu, którego elementy przechowuje tablica i indeks szukanego elementu, możliwe jest bardzo szybkie odnalezienie pożądanego adresu.</li>
<li><b><i>Wstawianie elementu:</i></b> W tym wypadku wiele zależy od miejsca w które chcemy wstawić element. Jeżeli jest to ostatni indeks to złożoność będzie wynosiła O(c). W wypadku gdy chcemy wstawić element gdzieś między pierwszym i ostatnim to przyjmuje się, że średnia złożoność wynosi O(n). Wynika to z faktu, że elementy muszą być przesunięte w taki sposób aby możliwe było wstawienie nowego.</li>
<li><b><i>Usuwanie elementu:</i></b> Sytuacja wygląda podobnie co przy wstawianiu. W wielu językach usuwając element z tablicy, automatycznie pozostałe elementy są „przesuwane”.</li>
</ul>
---
<p> Na koniec chciałbym pokazać jak małe są różnice w tworzeniu tablicy i dostępu do jej elementu w kilku różnych językach. (tablice w Javascript i Python, są dosyć specyficzne, ale nie o tym jest ten materiał :)). Tworzymy tablicę, taką jak na wspomnianym już obrazku i staramy się przypisać do zmiennej jej trzeci element: </p>
<p><b>C#:</b></p>
<pre class="language-csharp" tabindex="0"><code class="language-csharp">int[] exampleArray = new int[] {12, 14, -3, 32, 1, 44};
int thrid = exampleArray[2];</code></pre>
<p><b>C++:</b></p>
<pre class="language-cpp" tabindex="0"><code class="language-cpp">int exampleArray[6] = {12, 14, -3, 32, 1, 44};
int thrid = exampleArray[2]; </code></pre>
<p><b>Java:</b></p>
<pre class="language-java" tabindex="0"><code class="language-java">int[] exampleArray = new int[] {12, 14, -3, 32, 1, 44};
int thrid = exampleArray[2];</code></pre>
<p><b>Javascript:</b></p>
<pre class="language-js" tabindex="0"><code class="language-js">var exampleArray = [12, 14, -3, 32, 1, 44];
var thrid = exampleArray[2];</code></pre>
<p><b>Python:</b></p>
<pre class="language-python" tabindex="0"><code class="language-python">exampleArray = [12, 14, -3, 32, 1, 44];
thrid = exampleArray[2];</code></pre>