Wat is het verschil tussen een array en een lijst?

Het array heeft een vaste grootte, bepaald bij het maken. De lijst past zijn grootte dynamisch aan bij het toevoegen of verwijderen van elementen.

Toegang tot array-elementen gebeurt via index in O(1) tijd. Toegang tot lijst-elementen kan variëren, bijvoorbeeld, een enkel gekoppelde lijst heeft toegang via index in O(n), terwijl ArrayList gemiddeld in O(1).

In een array worden de elementen opgeslagen in continue geheugengebieden, wat een betere cache-prestatie garandeert. In een lijst kunnen de elementen verspreid zijn in het geheugen, verbonden door pointers.

Invoegen en verwijderen in het midden van een array vereisen het verschuiven van alle volgende elementen, wat kostbaar kan zijn (O(n)). In lijsten kunnen deze operaties efficiënter zijn (bijvoorbeeld, in gekoppelde lijsten O(1) als er een pointer naar het element is, anders O(n) voor zoeken), maar vereisen het bijwerken van pointers.

Arrays kunnen primitieve types direct opslaan. Lijsten slaan meestal referenties naar objecten op (wrappers voor primitieve types).

// Voorbeeld van array
int[] array = new int[5];
array[0] = 10; // Toegang O(1)

// Voorbeeld van ArrayList (lijst in Java)
import java.util.ArrayList;
import java.util.List;

List<Integer> list = new ArrayList<>();
list.add(10); // Toevoegen O(1) gemiddeld
list.get(0); // Toegang O(1) gemiddeld

# Voorbeeld van array (numpy array)
import numpy as np
array = np.array([1, 2, 3]) # Vaste grootte

# Voorbeeld van lijst
data_list = [1, 2, 3]
data_list.append(4) # Dynamische grootte

data_list[0] # Toegang O(1)

Vergelijking:

Kenmerk	Array	Lijst
Grootte	Vast	Dynamisch
Toegang via index	O(1)	Variabel (vaak O(1) of O(n))
Geheugen	Continu	Kan verspreid zijn
Invoegen/Verwijderen	O(n) in het midden	Variabel (kan O(1) zijn)
Gegevenstypen	Primitief en objecten	Meestal referenties naar objecten