Kako misliš drže različite podatke, i šta tačno podrazumevaš pod "headerom"? Pointer na "glavu" liste?

Pretpostavljam da pod headerom podrazumeva sentinel nod, koristi se u dvostruko uvezanim listama kao NULL node, tako da umesto da imas:

prvi.prev = null and zadnji.next = null

imas

prvi.prev = headerObj and zadnji.next = headerObj

Po teoriji omogucava lakse dodavanje novih elemenata na pocetak i kraj liste, i omogucava dvostruko uvezane liste sa nula elementata bez da pointer na listu bude null (lista pokazuje na samo header ciji prev i next pokazuju na samog sebe). Sam header se ne tretira kao node u listi i ne mora da bude istog tipa kao ostali nodovi (mada moze biti istog tipa sa odredjenom "nemogucom" kombinacijom elemenata noda koji ga cine headerom)

Downside je sto se dvostruko uvezana lista pretvara u cirkularnu jer prvi i zadnji element referenciraju header, tako da ako izgubis pointer na header GC nece moci da pocisti listu jer postoji kruzna referenca => memory leak.

mmix je otprilike objasnio o cemu se radi, mada nije apsolutno neophodno da lista bude dvostruko ulancana. Ali mi opet nije jasno ono glavno. Da li se header razlikuje po podacima koje drzi(sto je bezveze jer bi onda morao da provaram svaki cvor za tu neku "nemogucu kombinaciju" pri svakoj operaciji, ili je to stvarno drugi tip podatka?

Rasmisljajuci o ovome palo mi je na pamet kako bi se eventualno to moglo realizovati(ne od strane mene:)).
Da li je moguce to uraditi koriscenjem virtuelnih funkcija kao sto to radimo kod klasa derivata, da bismo mogli da razlucimo o kojoj strukturi se radi, prilikom samog izvrsavanja programa. ?

Header uopste ne nosi podatke, on je samo pozicioni objekat koji ti sluzi za ulazak u listu, nista vise. Provere mozes raditi po bilo kom osnovu npr ako je heder klase MojeHeader ovo ce proci kroz celu listu:




Eventualno heder moze da bude instanca klase u koju mozes da ubacis metode i implementiras interfejse za podrsku radu sa listom, npr da implementiras IEnumerable<T> i IList<T> ili da ubacis Count property ili ubacis indexer this[] itd.

Ono sto ne razumem je zasto ti uopste hoces da implementiras ovo (skolski zadatak?). U .NETu jednostavno nemas potrebe za ovime jer vec postoje implementacije koje mogu da zadovolje sve potrebe. Npr LinkedList<T> generic je dvostruko uvezana lista gde samu instancu liste mozes tretirati kao header (mada nije bas koser po definiciji, ne vaze oni uslovi koje sam naveo prosli put sa ciklicnoscu, sto su sigurno uradili da bi izbegli memory leak situacije).

[PS: sarry sad videh, ovo je tema u art-of-prog, ignorisi pitanje :), koji jezik bi ti koristio za implementaciju?]

jeste skolski zadatak :)

Mislim iako to sustinski nije bitno ali bi mi svakako koristila implementacija u plain C.

Ako znas engleski, pogledaj sledecu lekciju sa stanforda, oni su bas lepo objasnili i koncep i sve moguce operacije nad linked listama zajedno sa C kodom:

Stanford Edu: Linked List Basics

Tvoja implementacija bi se utliko razlikovala sto ti head pointer ne pokazuje na prvi element niza, vec na tvoj header, koji moze biti drugacije strukture, ali treba da ima next, tako da sve funkcije modifikujes tako da umesto da koriste head kao pocetak liste, koriste head->next kao prvi element.

hvala puno na tekstu. samo sam preleteo, ali mislim da ce koristiti