Datenstrukturen: Arrays

Arrays, oder auch Felder gehören zu den ältesten Datentypen der Softwareentwicklung. Bereits 1945 schrieb von Neumann den Mergesort-Algorithmus zum sortieren von Arrays. Bei einem Array handelt es sich um einen zusammengesetzten Bereich, der eine bestimmte Anzahl von gleichen Datentypen aufnehmen kann. Die Größe eines dieses Bereichs muss bei dessen Initialisierung bekannt sein. Nach der Initialisierung können dann Elemente in das Feld geschrieben werden. Ein Array kann nicht dynamisch wachsen oder schrumpfen. Ein Array belegt daher immer den gesamten Speicherbereich, welcher bei der Initialisierung deklariert wurde. Bei der Initialisierung sollte man daher immer genau wissen wie groß das benötigte Array sein muss. Wird ein Element nicht zugewiesen, so verbraucht das Array unnötigen Speicherplatz.

Angeberwissen

Wird ein Array Initialisiert, so wird der benötigte Speicherbereich für das Array reserviert. Für Programmiersprachen ohne Speichermanagement besteht das Array dann aus den Daten die zu diesem Zeitpunkt im Speicher lagen. Der Wert muss nicht immer null sein. Es ist durchaus üblich, dass der Wert aus einer alten Speichernutzung erhalten bleibt.
Wurde beispielsweise vor der Initialisierung des Arrays eine Methode aufgerufen, welche mehrere Variablen benutzt und anschließend wieder verwirft, so kann es durchaus vorkommen, dass diese Variablen nun über das Array wieder auslesbar sind.

Ein Array verbraucht genauso viel Platz im Speicher wie die Summe seiner Elemente. Es entsteht kein Overhead, da wirklich nur die darin enthaltenen Datentypen in einem zusammenhängenden Block im Speicher abgelegt werden. Die Variable selbst ist nur ein Zeiger auf den Anfang des Blocks.

Der Zugriff erfolgt über den Index des gewünschten Elements. Es ist dabei darauf zu achten, dass das Array in den meisten Programmiersprachen bei 0 beginnt. Ein Array aus 10 Elementen erlaubt Zugriffe über die Indizes 0-9. Möchte man beispielsweise auf das sechste Element zugreifen muss dies mit dem Index 5 geschehen.

Bei einem Zugriff wird der gewünschte Index mit der Größe des Datentypes multipliziert und dieser Wert mit dem Zeiger auf den Anfang des Arrays addiert. Fängt das Array beispielsweise bei Speicherposition 100 an und möchten wir auf den sechsten Integer-Wert zugreifen, welche jeweils 8 Byte groß sind, so befindet sich der gewünschte Wert an Speicherposition 140 (100 + (6 – 1) * 8 = 140).

Die Berechnung ist trivial, bietet jedoch auch ein großes Gefahrenpotential. In Programmiersprachen, welche kein memory Management besitzen könnte mit einem zu großen Index auf Elemente zugegriffen werden, welche sich zwar im Speicher befinden, jedoch nicht Teil des Arrays sind. Dies kann ausgenutzt werden um an vertrauliche Daten zu gelangen oder diese zu ändern.

Mehrdimensionale Arrays

Mehrdimensionale Arrays sind letztendlich eine Kombination aus eindimensionalen Arrays. Die Spalten bestehen aus Arrays welche den Gewünschten Datentyp besitzen, wobei die Zeilen wiederum Arrays beinhalten. Dabei ist zu beachten, dass jede Zeile separat initialisiert werden muss.

Array<Array<Integer>> myArray = new Array<>(5);
for(int i = 0; i>5; i++) {
	myArray[i] = new Array<>(5);
}

Der Zugriff auf ein mehrdimensionales Array erfolgt über zwei Indizes. 
Die Anzahl der Dimensionen ist im Grunde egal. Mehrdimensionale Arrays werden gerne in der Bildverarbeitung eingesetzt, da Bilder eine fixe Größe besitzen und sich die Bildpunkte als zweidimensionale m·n Matrix darstellen lassen.

Array-Listen

Array-Listen sind Wrapper-Klassen für Arrays. Sie speichern ihre Werte in einem Array, erlauben dem Anwender jedoch einen einfachen Zugriff und erweitern das Array dynamisch, falls der Speicherplatz innerhalb des Arrays nicht mehr ausreichen sollte. Im Hintergrund wird dabei nichts weiter getan als ein neues Array anzulegen, das um einen bestimmten Faktor größer ist als das vorherige.

package com.florianbuchner.library.collection;

import java.lang.reflect.Array;

public class ArrayList<T> implements List<T> {

	public static int INCREMENT = 30;
	
	private int size;
	
	private T[] array;
	
	private Class<T>; type;
	
	@SuppressWarnings("unchecked")
	public ArrayList(Class<T> type) {
		this.type = type;
		this.array = (T[]) Array.newInstance(type, INCREMENT);
	}
	
	public ArrayList(T[] source) {
		this.array = source;
		this.size = source.length;
	}
	
	@Override
	public int size() {
		return this.size;
	}

	@Override
	public T get(int index) {
		if (index >= size) {
			throw new ArrayIndexOutOfBoundsException(index);
		}
		return array[index];
	}

	@Override
	@SuppressWarnings("unchecked")
	public void add(T item) {
		if (this.size >= this.array.length) {
			final T[] current = this.array;
			this.array = (T[]) Array.newInstance(this.type, current.length + INCREMENT);
			for (int i = 0; i < current.length; i++) {
				this.array[i] = current[i];
			}
		}
		this.array[this.size] = item;
		this.size++;		
	}

	@Override
	public T remove(int index) {
		final T item = this.get(index);
		for (int i = index; i < size - 1; i++) {
			this.array[i] = this.array[i+1];
		}
		this.size--;
		return item;
	}

	@Override
	public void clear() {
		this.size = 0;
	}

}

Komplexität