Lecture overview -- Keyboard shortcut: 'u'  Previous page: Lister [Section] -- Keyboard shortcut: 'p'  Next page: Enkeltkædede lister -- Keyboard shortcut: 'n'  Lecture notes - all slides and notes together  slide -- Keyboard shortcut: 't'  Help page about these notes  Alphabetic index  Course home  Page 13 : 28
Forelæsningsnoter i Objekt-orienteret Programmering
Arrays og Lister
Introduktion til lister

En liste men 6 elementer. Med denne måde at tegne listen på understreger vi at den indbyrdes rækkefølge af elementer er væsentlig. Vi giver også samtidig et hint til en typisk repræsentation af lister

  • En liste er en abstrakt datatype som tillader os at registrere en bestemt rækkefølge af et antal homogene elementer.

  • Vigtige liste-operationer:

    • Indsættelse af nyt element i listen

    • Sletning af eksisterende element fra listen

    • Navigering til et naboelement i listen

    • Aflæsning af et nærmere angivet element i listen

Vi har forsøgt at fastslå de vigtige og karakteristiske operationer på lister. Indsættelse og sletning tillader os manipulere rækkefølgen af elementer. Hvis vi sammenligner med array-typen kan vi notere os, at der er fundamentale forskelle, idet rækkefølgen af array-elementer i bund og grund er fastlagt på det tidspunkt, tabellen skabes. (At vi kan simulere ændringer af rækkefølgen af array-elementer ved at skubbe og ombytte indholdet er tabellens elementer er en anden sag). Navigering til naboelementer er også fundamentalt for lister. På dette niveau af diskussionen vil vi ikke fastlægge nøjagtigt hvilken navigering der er tale om, og ej heller hvordan resultatet af navigeringen manifesterer sig. Men i alle typer af lister vil vi kunne navigere til næste element i listen. (I mange liste typer kan vi også komme afsted med at navigere til forrige element i listen). Endelig må vi have en eller anden måde at aflæse elementer fra listen. Aflæsning hænger ofte sammen med navigering, således at vi kan aflæse det element, hvortil vi har bevæget os.

I forhold til arrays ser vi følgende væsentlige forskelle:

    Der er ingen fast øvre grænse på antallet af elementer Der er typisk ikke effektiv og direkte tilgang til elementerne i listen Elementerne i listen lagres ikke konsekutivt (altså ikke i hinanden følgende lagerceller i maskinens arbejdslager).

  • Der er flere mulige repræsentationer af lister:

    • Her vil vi koncentrere os om sammenkædede lister