Array og lister


Innfødt array

En array, også kalt en innfødt array, er en liste med fast lengde. Man trenger ikke importere noe for å bruke den. Eksempel på bruk:

// Opprette en array med gitte elementer
String[] a = new String[] { "foo", "bar", "baz" };

// Hente ut lengden av arrayen
int n = a.length;
System.out.println(n); // 3

// Hente ut et element på en gitt posisjon (0-indeksert)
String s = a[1];
System.out.println(s); // "bar"

// Endre et element på en gitt posisjon
a[1] = "qux";

// Skrive ut arrayen
System.out.println(Arrays.toString(a)); // [foo, qux, baz]

// Iterere over arrayen
for (String t : a) {
    System.out.print(t); // fooquxbaz
}
System.out.println();

// Legge til et element på slutten av arrayen: IKKE MULIG!
// Man må eventuelt lage en ny array med større lengde og
// så kopiere den dataen man skal ha, men: dette er *ikke*
// effektivt, og vil *ikke* mutere arrayen a.
String[] tmp = new String[a.length + 1];
System.arraycopy(a, 0, tmp, 0, a.length); // (fra, startIdx, til, startIdx, antall)
tmp[tmp.length-1] = "quack";
a = tmp;
System.out.println(Arrays.toString(a)); // [foo, qux, baz, quack]

// Fjerne et element fra arrayen: IKKE MULIG!
// Man må eventuelt lage en ny array med kortere lengde og
// så kopiere den dataen man skal ha, men: dette er *ikke*
// effektivt, og vil *ikke* mutere arrayen a.
int iToRemove = 2;
tmp = new String[a.length - 1];
System.arraycopy(a, 0, tmp, 0, iToRemove);
System.arraycopy(a, iToRemove + 1, tmp, iToRemove, a.length - iToRemove - 1);
a = tmp;
System.out.println(Arrays.toString(a)); // [foo, qux, quack]

// Sortere arrayen
Arrays.sort(a);
System.out.println(Arrays.toString(a)); // [foo, quack, qux]


// Opprette array med en gitt størrelse og standard-verdier
int[] b = new int[10]; // 10 elementer med verdi 0
String[] c = new String[10]; // 10 elementer med verdi null
double[] d = new double[10]; // 10 elementer med verdi 0.0
boolean[] e = new boolean[10]; // 10 elementer med verdi false

// Fyll en array med en gitt verdi
Arrays.fill(b, 42); // har nå 10 elementer med verdi 42
System.out.println(Arrays.toString(b)); // [42, 42, 42, 42, 42, 42, 42, 42, 42, 42]

ArrayList

En ArrayList er en liste med variabel størrelse. Under paseret benytter den seg av en vanlig array, men den gjør det på en smart og effektiv måte.

Fordeler med ArrayList (vs array):

  • Kan endre størrelse på listen ved å legge til og fjerne elementer
  • Kan benyttes med generiske typer

Ulemper med ArrayList (vs array):

  • ArrayList kan ikke brukes med primitive datatyper som int, double, boolean og lignende, men må i stedet bruke «boks»-klassene Integer, Double, Boolean et cetra. Den er derfor mer ressurskrevende med tanke på tidsbruk og minnebruk hvis (og bare hvis) elementene vi jobber med både er av en primitive datatype og listen ikke endrer størrelse ofte.

For å bruke ArrayList må man importere klassen fra java.util-pakken.

// Opprette en liste med gitte elementer
ArrayList<String> a = new ArrayList<>(Arrays.asList("foo", "bar", "baz"));

// Hente ut lengden av listen
int n = a.size();
System.out.println(n); // 3

// Hente ut et element på en gitt posisjon (0-indeksert)
String s = a.get(1);
System.out.println(s); // "bar"

// Endre et element på en gitt posisjon
a.set(1, "qux");

// Skrive ut listen
System.out.println(a); // [foo, qux, baz]

// Iterere over listen
for (String t : a) {
    System.out.print(t); // fooquxbaz
}
System.out.println();

// Legge til et element på slutten av listen
a.add("quack");
System.out.println(a); // [foo, qux, baz, quack]

// Fjerne et element fra listen
a.remove(2);
System.out.println(a); // [foo, qux, quack]

// Sortere listen
Collections.sort(a);
System.out.println(a); // [foo, quack, qux]


// MISLYKKET: Opprette liste med en gitt størrelse og standard-verdier:
ArrayList<Integer> b = new ArrayList<>(10); // OOPS! dette er en **TOM** liste
System.out.println(b.size()); // 0 (altså en tom liste)

// VELLYKKET: Opprette liste med en gitt størrelse og standard-verdier:
b = new ArrayList<>(Collections.nCopies(10, 42)); // 10 elementer med verdi 42
System.out.println(b); // [42, 42, 42, 42, 42, 42, 42, 42, 42, 42]

List

List er et grensesnitt som blant annet ArrayList implementerer. Det er en god praksis å bruke så abstrakte datatyper for variabler som mulig så lenge datatypen fremdeles er hensiktsmessig for formålet. For eksempel er det god praksis å bruke typen List for variabler som representerer lister, i stedet for å bruke typen ArrayList direkte. Da gjør du koden din mer fleksibel for endringer, og du kan enklere bytte ut ArrayList med en annen listeimplementasjon senere om du skulle ønske.

List<String> a = new ArrayList<>();
a.add("foo");
a.add("bar");
System.out.println(a); // [foo, bar]

Det er mange ulike klasser som representerer lister i Java; i tillegg til ArrayList finnes også LinkedList, Vector, Arrays$ArrayList (som ikke er det samme som ArrayList) og så videre, hver med sine spesielle styrker og egenskaper. Felles for dem (innfødte arrays ikke inkludert) er at de implementerer List -grensesnittet. For mange formål er det egentlig uinteressant hvilken listeimplementasjon vi bruker, så lenge vi bruker en liste. Da er det god praksis å bruke List som variabeltype.

Hvilken klasse vi benytter for å representere en liste kan ha betydning for kjøretiden. Det viktigste eksempelet på dette (som vi kommer tilbake til i INF102) er at LinkedList er veldig rask hvis man skal legge til eller fjerne et element i begynnelsen av listen, men treg hvis man skal se på eller bytte ut et element i midten av listen. En ArrayList vil derimot være veldig treg når det kommer til å legge til eller fjerne elementer i begynnelsen av listen, men er veldig rask hvis man skal se på eller endre et element midt inne i listen. Hvilken klasse vi bør velge vil derfor avhenge av hvilket bruk som er mest aktuelt for oss – men så lenge koden vår benytter List som type vil det være veldig lett å bytte, og vi kan sågar benytte lister i ulike klasser om hverandre uten at vi trenger å endre på koden vår i det hele tatt.