LISTE - ASPECTE TEORETICE. DEFINIţIE. OPERAţII ASUPRA LISTELOR REFERAT SCOALA

O listă L e o secvenţă de zero sau mai multe elemente, numite noduri, toate fiind de acelaşi tip de baza T. L=a1,a2,...,an (n>=0) Dacă n>=1, a1 se spune că este primul nod al listei, iar an, ultimul nod. Daca n=0, lista este vida. O proprietate importantă a unei liste este aceea că nodurile sale pot fi ordonate liniar funcţie de poziţia lor în cadrul listei. Se spune că ai precede pe ai+1 (i=1,2,...,n-1), iar ai succede pe ai-1 (i=2,3,...,n), ai aflându-se pe poziţia i. Se postulează(presupune) existenta poziţiei următoare ultimului element al listei şi se introduce funcţia FIN(L) ce va returna poziţia următoare poziţiei n din lista L de n elemente. Folosind notaţiile anterioare şi notând x(de tip T) un nod al listei, iar p fiind de tip poziţie, se introduce următorul set reprezentativ de operatori aplicabili obiectelor de tip lista: