Pratybos
Penkios užduotys. Visos su Playlist, visos su skaitikliais.
1. (*Playlist) Reverse()
Apverčia grojaraštį vietoje, nekurdamas naujų mazgų — tik sukeisdamas
Prev ir Next.
Kiek rodyklių perrašai? Ar tai priklauso nuo n? Kaip tą patį darytum su
[]Item ir kiek kainuotų?
2. (*Playlist) FindNode(title string, c *metrics.Counter) *Node
Suranda mazgą pagal pavadinimą.
Palygink su 1 pamokos LinearFind. Sudėtingumas tas pats — ar tas pats ir
skaičius? Paleisk abu su ta pačia biblioteka ir paaiškink skirtumą, jei jis yra.
3. (*Playlist) InsertAfterNode(n *Node, it Item)
Įterpia naują įrašą po turimu mazgu.
Suskaičiuok rodyklių perrašymus. Tada paleisk su n = 1 000 ir n = 1 000 000. Skaičius turi nesiskirti. Tai ir yra O(1) — patikrink, o ne patikėk.
4. Vidurio paieška vienu perėjimu
(*Playlist) Middle(c *metrics.Counter) *Node — grąžina vidurinį mazgą
neskaičiuodamas Len ir apeidamas sąrašą tik vieną kartą.
(Užuomina: dvi rodyklės, viena juda dvigubai greičiau.)
Kiek šuolių? Palygink su naiviu būdu — pirma suskaičiuoti, paskui nueiti iki
Len/2.
5. Kur sąrašas iš tikrųjų laimi
Sukurk matavimą, kuriame Playlist neabejotinai laimi prieš []Item.
Sąlyga: nesukčiauk paslėpdamas vaikščiojimą. Jei tavo scenarijus reikalauja mazgo — pasakyk, iš kur jį gauni, ir įskaičiuok tą kainą.
Jei nepavyksta sugalvoti sąžiningo scenarijaus — parašyk ir tai. Tai teisingas atsakymas dažniau, negu tikiesi.