Welke beschrijving van een gelinkte lijst (een lijst waarin elk element een pointer naar het volgende element bevat) is juist in vergelijking met een array?

Antwoord: A. Als het element vlak vóór de invoegpositie bekend is, kan een element worden ingevoegd door alleen pointers te wijzigen, zonder andere elementen te verplaatsen; om het i-de element te lezen moet de lijst echter vanaf het begin worden doorlopen

In een gelinkte lijst kost invoegen of verwijderen O(1) zodra de positie bekend is, want alleen de pointers van de buren hoeven te worden herschreven. Om het i-de element te lezen moeten echter vanaf het begin i pointers worden gevolgd, wat O(n) kost. Een array kan het adres van het i-de element berekenen uit het beginadres en de elementgrootte en leest dus elk element in O(1), maar invoegen in het midden kost O(n), omdat de elementen erachter moeten opschuiven. Bovendien staan de elementen van een array aaneengesloten, zodat caches en prefetching goed werken, terwijl de knopen van een gelinkte lijst vaak verspreid in het geheugen liggen; daardoor kan zelfs een doorloop van dezelfde orde O(n) veel trager zijn.