Structuri de Date Fundamentale: Array-urile (Listele)

In acest articol o sa inveti tot ce ai nevoie despre array-uri, una dintre cele mai folosite structuri de date din computer science.

Indiferent de limbajul de programare cu care lucrezi, o sa te "lovesti" de array-uri aproape de fiecare data cand o sa ai nevoie sa "stochezi" o lista de lucruri si vei vrea sa efectuezi diverse transformari cu aceasta colectie (sa adaugi elemente in lista, sa stergi elemente din lista, sa le sortezi si asa mai departe).

Ce este un Array? Care sunt tipurile de Liste?

In general un array este un mod de a stoca o lista liniara de lucruri.

Ce inseamna liniar?

Inseamna ca unui element din lista ii corespunde o pozitie (numit si index) de la 0 la n-1.

Asadar intr-un array, primul element va avea de obicei indexul 0, iar ultimul element va avea index-ul n-1.

Daca avem 60 de elemente, atunci ultimul element va avea indicele 59.

Tipuri de Array-uri

In functie de limbajul de programare cu care te "lupti", vei avea la indemana diverse tipuri de array-uri, dar conceptual putem vorbi despre 2 tipuri de array-uri:

• array-uri dinamice (folosite mai ales in general limbajele de programare mai tinere - numite si moderne, care sunt in general dinamice precum PHP, JavaScript, Python, Ruby and friends)
• array-uri statice (folosite mai ales limbajele de programare ceva mai veterane precum C, C++, Java and older friends)

Ce sunt array-uri statice

Iti permit sa stochezi o lista caruia tu ii aloci un spatiu continuu in memorie.

Ce inseamna asta?

Daca tu ai 20 de elemente in lista (sa zicem o lista cu fostii tai colegi de liceu), toate elementele din lista vor exista "unul langa altul" in memoria calculatorului tau.

Daca vei vrea sa adaugi un element nou in lista, iar memoria nu are "sloturi" disponibile, toata lista va trebui realocata pe un sector de memorie care poate sustine toata lista ta.

Prin sloturi de memorie vreau sa intelegi urmatorul lucru: fiecare slot ar fi echivalentul unui plic in care incape sa zicem un post-it note.

Sa nu confunzi sloturile de memorie din acest articol cu sloturile fizice de memorie in care bagi RAM-ul din calculator.

Imagineaza-ti daca ti-ar trebui cate un slot fizic de memorie pentru fiecare lucru banal pe care ai vrea sa il stochezi, nu ar fi spatiu fizic sa tii toate lucrurile pe care ti le-ai dori.

Ce sunt array-urile dinamice

Listele dinamice sunt mai permisive si ti se prealoca un spatiu disponibil suplimentar.

Sa zicem ca ai o lista de 20 de colegi, dar ti se aloca 40 de sloturi de memorie (dublul nevoii tale initiale).

De la 21 pana la 40 vei putea sa adaugi cu usurinta mai multi colegi, dar daca apare si al 41-lea coleg, va trebui sa fie mutata toata lista pe un nou sector de memorie, unde i se va aloca 80 de sloturi de memorie (daca sunt disponibile).

In general, limbajele de programare populare (precum JavaScript, Python, PHP etc) implementeaza array-uri dinamice, pentru ca este destul de dificil sa stii dinainte cate elemente vor intra in lista ta.

Ce poti face cu o Lista? Ce poti face cu un Array?

Hai sa discutam un pic despre ce anume poti face cu o lista:

• Intr-un array poti citi o valoare de la un anumit indice.
• Intr-un array poti sterge o valoare de la un anumit indice.
• Poti sa adaugi la sfarsitul array-ului, la mijloc sau poti adauga - la inceputul array-ului. Cum le adaugi, le poti si sterge.
• Poti sa adaugi chiar si intr-o anumita pozitie (indice) daca ai nevoie.
• Desigur, poti si sa editezi anumite valori de pe anumite pozitii.
• Ti-am zis ca poti si sa copiezi un intreg array?

Dupa cum poti vedea, poti sa faci mai de toate.

Pentru ca in general reprezinta o structura de date foarte flexibila, array-urile sunt omniprezente in aproape orice limbaj de programare.

Big O Notation (Complexitate) pentru operatiunile standard din array-uri

Haide sa discutam despre fiecare situatie in parte, pentru ca daca nu pricepi partea asta, orice intrebare dintr-un interviu in care accentul cade pe structuri de date si algoritmi o sa te incurce.

Accesarea unui element dintr-un Array - O(1)

Pentru ca fiecare element dintr-un array are asociat un index, e ca si cum ai arata cu degetul direct la elementul pe care il vrei sa il accesezi.

Inserarea unui element la inceputul unui Array - O(n)

Pentru ca inserezi la inceputul unui array, toate celelalte elemente din lista trebuie mutate la dreapta si fiecarui element ii trebuie asociat un nou index.

Inserarea unui element la mijlocul unui Array - O(n)

Pentru ca inserezi la mijlocul unui array, toate celelalte elemente din lista care sunt in dreapta elementului proaspat inserat trebuie mutate la dreapta si fiecarui element ii trebuie asociat un nou index.

Inserarea unui element la finalul unui Array - O(1) / O(n)

Pentru ca inserezi la final, niciun index (indice) precedent nu trebuie recalculat si reasociat cu vreun element.

Totusi daca vorbim despre array-uri statice (cu spatiu prealocat), s-ar putea sa fie nevoie sa fie mutate toate elementele din lista intr-o secventa noua de sloturi de memorie in care sa incapa toate elementele din array-ul tau.

Stergerea primului element dintr-un Array - O(n)

Cand stergi un element de la inceputul listei, toate elementele au nevoie de un nou index cu care sa fie asociate.

Stergerea unui element de la mijlocul unui Array - O(n)

La fel ca in situatia precedenta, doar ca elementele afectate sunt toate elementele de la dreapta elementului pe care tocmai l-ai sters.

Stergerea ultimului element dintr-un Array - O(1)

Nimic nu trebuie reasociat, pentru ca ai sters doar ultimul element din lista, toate celelalte elemente isi pastreaza indexul.

Update-ul oricarei valori dintr-un array - O(1)

Foarte similar cu accesarea, doar ca in cazul acesta faci update direct pe o pozitie deja cunoscuta.

Cum se creaza un array in diverse limbaje de programare

Desi la baza majoritatea exemplelor de mai jos reprezinta toate array-uri, s-ar putea ca in anumite limbaje de programare aceasta structura de date sa poarte alt nume, cum ar fi lists in Python.

Fiecare limbaj de programare implementeaza in modul lui structura de Array, deci s-ar putea ca de la un limbaj la altul sa fie ceva diferente in ce fel de date poti stoca intr-unul (poate fiecare element sa fie o valoare de acelasi tip: string, number etc) sau felul cum operatiunile standard descrise mai sus functioneaza.

JavaScript Arrays

• in JS array-urile dinamice sunt numite array-uri si sunt un tip special de obiect (poti sa faci in Dev Console typeof [] ca sa vezi ce o sa se intample)

const myFamily = ['Gabriel', 'Antonia', 'Arthur']
console.log(myFamily[0]) // Gabriel
console.log(typeof myFamily) // object

TypeScript Arrays

• pentru TypeScript e doar un superset de-al lui JavaScript, sintaxa este aproape identica (cu exceptia specificarii tipurilor)

const myFamily: string[] = ['Gabriel', 'Antonia', 'Arthur']
console.log(myFamily[0]) // Gabriel

Python Lists

• in Python cand vrei sa creezi un array de obicei vei crea o lista (List)

myFamily = ["Gabriel", "Antonia", "Arthur"]
print(myFamily[0]) # Gabriel

C# Arrays

• in C# cand vrei sa creezi un array va trebui sa declari si tipul elementelor din lista

string[] myFamily = {"Gabriel", "Antonia", "Arthur"}
Console.WriteLine(csharp[0]); // Gabriel

PHP Arrays

$myFamily = ["Gabriel", "Antonia", "Arthur"]
echo $myFamily[0]; // Gabriel

Go Arrays

• Go este un pic mai special, pentru ca are array-uri statice (fixe), array-uri dinamice (slices). De obicei vei ajunge sa folosesti slices, pentru ca nu trebuie sa prealoci spatiu pentru elemente si poti face cu usurinta append de fiecare data cand vrei sa adaugi ceva.

Array static:

package main

import (
    "fmt"
    "reflect"
)

func main() {
    /*
      poti sa scrii ce ai mai jos si ca
      var family = [3]string{"Gabriel", "Antonia", "Arthur"}
    */
    family := [3]string{"Gabriel", "Antonia", "Arthur"} // shorthand syntax = declaration + initialization

    fmt.Println(family) // [Gabriel Antonia Arthur]
    fmt.Println(cap(family)) // 3
    fmt.Println(reflect.TypeOf(family).Kind())  // array
}

Array dinamic (Slice)

package main

import (
    "fmt"
    "reflect"
)

func main() {
  family := make([]string, 0)
  family = append(family, "Gabriel", "Antonia", "Arthur")

  fmt.Println(family) // [Gabriel Antonia Arthur]
  fmt.Println(len(family)) // 3
  fmt.Println(cap(family)) // 3
  fmt.Println(reflect.TypeOf(family).Kind()) // slice
}