February 23, 2021

in1010-2021-uke7-forelopig.pdf

Forrige forelesning (del 1) Neste forelesning (tråder)

Lecture outline:

• Implementasjon av lenkelister (ulik datarepresentasjon i beholderne)
  • Enveislister (som vi så på sist)
  • Toveislister (nytt)
  • Egen referanse til siste element i listen
• Varianter av lister (ulike grensesnitt for beholderne)
  • Stabel (stack, Last In First Out – LIFO)
  • Kø (First In First Out – FIFO)
  • Prioritetskø
• Mer Java
  • Innpakking ("boxing")
  • Å sammenligne objekter (Comparable )
  • Å gå gjennom alle elementer i en beholder (Iterator)

Lenkelister

Lenkelister - alternative datastrukturer

Fordeler og ulemper ved enkeltlenket liste

• + Fleksibel! Alltid plass til akkurat så mange elementer som trengs
• + (relativt) enkelt å programmere metodene
• - Mye "nesting" for å jobbe seg frem til elementer langt ut i listen
• - Må passe på å stoppe én node foran den som skal fjernes

Valg av datastruktur for en liste

• Det er vanligvis fornuftig å ha en instansvariabel slutt også i en enveis liste
• Da kan man i hvert fall enkelt lese av/ endre det siste, og legge til nytt element bakerst