Hoofdstuk 1. Lineaire lijsten

1. Definitie

Een lineaire lijst is een verzameling, voorzien van een complete orderelatie. Naargelang van de context heten de elementen informatie-eenheden, knopen of records.

Opmerkingen

• een lineaire lijst kan leeg zijn
• compleet betekent dat men voor ieder paar elementen kan zeggen, welke van de twee de ander voorafgaat
• we werken steeds met eindige lineaire lijsten; dit laat toe de elementen te nummeren {X₁,X₂,...,X_n} zodat X_i<=X_j a.s.a. i<=j

Voor wat de voorstelling van een lijst in een computergeheugen betreft, voeren we de volgende notaties in:

Afspraak

Binnen dezelfde lijst is c voor alle records gelijk.

Voorbeeld

De verzameling van alle Belgische identiteitskaarten, gerangschikt op nummer. Eén kaart bevat:

c bedraagt 76 karakters (bijvoorbeeld bytes) of 38 woorden van 2 karakters. c kan in verschillende eenheden worden uitgedrukt, maar is steeds een natuurlijk getal, dus minstens 1, in de gebruikte eenheid.

2. Bewerkingen op lineaire lijsten

Een lineaire lijst is een dynamische structuur, dat wil zeggen dat hij kan veranderen. Enkele mogelijke veranderingen in één afzonderlijke lijst zijn:

• een element toevoegen vóór de k-de record (INSERT)
• een element toevoegen na de laatste record (APPEND)
• een element verwijderen (DELETE)

Verder kunnen twee lijsten met gelijke c tot één lijst worden ineengeschoven (MERGE) en kan een lijst in twee of meer andere gesplitst worden.