Arrays gemmer elementer i sammenhængende hukommelsesplaceringer, hvilket resulterer i let beregnelige adresser for de lagrede elementer, og dette giver hurtigere adgang til et element ved et bestemt indeks. Linkede lister er mindre stive i deres lagringsstruktur, og elementerne lagres normalt ikke på sammenhængende steder, hvorfor de skal lagres med yderligere tags, der giver en henvisning til det næste element. Denne forskel i datalagringsordningen afgør, hvilken datastruktur der er bedst egnet til en given situation.

Dataopbevaringsskema for et array

Dataopbevaringsskema for en linket liste

De vigtigste forskelle er anført nedenfor:

• Størrelse:
  • Størrelse: Da data kun kan lagres i sammenhængende blokke af hukommelse i et array, kan størrelsen ikke ændres under kørslen på grund af risikoen for overskrivning af andre data. I en linket liste peger hver knude imidlertid på den næste, således at data kan findes på spredte (ikke-sammenhængende) adresser; dette giver mulighed for en dynamisk størrelse, som kan ændres under kørselstiden.
  • Hukommelsesallokering: For arrays på kompileringstidspunktet og på køretid for linkede lister.
  • Hukommelseffektivitet: For det samme antal elementer bruger linkede lister mere hukommelse, da en reference til det næste knudepunkt også lagres sammen med dataene. Størrelsesfleksibiliteten i linkede lister kan dog gøre, at de samlet set bruger mindre hukommelse; dette er nyttigt, når der er usikkerhed om størrelsen, eller når der er store variationer i dataelementernes størrelse; der skal allokeres hukommelse svarende til den øvre grænse for størrelsen (selv om ikke al den bruges) ved brug af arrays, hvorimod linkede lister kan øge deres størrelse trinvis i forhold til datamængden.
  • Udførelsestid: I et array kan man få direkte adgang til ethvert element i et array ved hjælp af dets indeks, men i tilfælde af en linket liste skal alle de foregående elementer gennemløbes for at nå et element. Desuden kan bedre cache-lokalitet i arrays (som følge af sammenhængende hukommelsesallokering) forbedre ydeevnen betydeligt. Som følge heraf er nogle operationer (f.eks. ændring af et bestemt element) hurtigere i arrays, mens nogle andre (f.eks. indsættelse/sletning af et element i dataene) er hurtigere i linkede lister.

  Følgende er de punkter, der taler til fordel for linkede lister.
  (1) Arrays’ størrelse er fast: Vi skal altså kende den øvre grænse for antallet af elementer på forhånd. Desuden er den tildelte hukommelse generelt lig med den øvre grænse uanset brugen, og i praktisk brug nås den øvre grænse sjældent.

  (2) Det er dyrt at indsætte et nyt element i et array af elementer, fordi der skal skabes plads til de nye elementer, og for at skabe plads skal eksisterende elementer flyttes.

  For eksempel antager vi, at vi vedligeholder en sorteret liste af ID’er i et array id.

  id = .

  Og hvis vi ønsker at indsætte et nyt ID 1005, skal vi for at bevare den sorterede rækkefølge flytte alle elementer efter 1000 (undtagen 1000).

  Sletning er også dyrt med arrays indtil, medmindre der anvendes nogle særlige teknikker. For eksempel for at slette 1010 i id, skal alt efter 1010 flyttes.

  Så linkede lister giver følgende to fordele i forhold til arrays
  1) Dynamisk størrelse
  2) Let at indsætte/slette

  Linkede lister har følgende ulemper:
  1) Tilfældig adgang er ikke tilladt. Vi er nødt til at få adgang til elementerne sekventielt fra det første knudepunkt. Vi kan altså ikke foretage en binær søgning med linkede lister.
  2) Der kræves ekstra hukommelsesplads til en pointer med hvert element i listen.
  3) Arrays har bedre cache-lokalitet, der kan gøre en ret stor forskel i ydeevnen.