A láncolt lista olyan adatszerkezet, amely dinamikusan szabályozott mennyiségű, azonos típusú elemet tárol. Ilyen a tömb, de az nem dinamikus és maximális mérete van, ilyen a sor, de annak is maximális mérete van, valamint a verem, de az is maximalizált méretű.
A láncolt lista dinamikus adatszerkezet, és a méretét csak a fizikai memória szabja meg (32Mbyte-nál max. 32Mbyte-os lehet).
A tömb indulási mérete fix, és használat közben ugyanannyi marad. A sor és a verem is ilyen, hiába dinamikus, a teljes mérete fix. A láncolt lista indulási mérete minimális, menet közben a mérete „alkalmazkodó”.
A tömb elemei tetszőleges (direkt) elérésűek. A sor elérése FIFO (amit elsőnek be, elsőnek ki). A verem elérése LIFO (amit utolsónak be, elsőnek ki). A láncolt lista elérése soros (szekvenciális). Az elejétől a kiválasztott elemig sorrendben kell feldolgozni.
A láncolt lista elemei két részből állnak: értékből és mutatóból. A lista elején egy fej áll.
Fej(mutató) -> 1. elem, mutató -> 2. elem, mutató -> utolsó elem, NIL
A fej megmutatja, hogy az első elem a memóriában hol helyezkedik el, az első elem egy értéket tartalmaz, valamint egy mutatót, ami a második elem címét mutatja. Az utolsó elem muatatója NIL értékű.
Az üres lista feje NIL. Egy elemű lista feje mutat az elemre, elem mutat NIL-re.
Beszúrás:
Egy új elem beszúrása 2 mutató átállításába kerül (8 byte).
Törlés:
Egy elem törlése 1 mutató átállításába kerül (4 byte).
![]() |
Hozzáadás a végéhez:
Egy új elem hozzáadása a végéhez 2 mutató átállításába kerül (8 byte).
Algoritmusok:
TYPE
PRekord=^TRekord;
TRekord=Record
Nev:String;
Kov:PRekord;
end;
Var
Start:PRekord;
{Inicializáló eljárás - NIL-re állítja a fejet:}
Procedure ListaInit;
begin
GetMem(Strart,SizeOf(TRekord));
Start^.Nev:=’’;
Start^.Kov:=NIL
end;
{Új elemet hoz létre - nem illeszti be, csak létrehozza az új elemet:}
Fuction Ujelem(Nev:String):PRekord;
begin
GetMem(P,SizeOf(TRekord));
P^.Nev:=Nev;
P^.Kov:=NIL;
Ujelem:=P;
end;
{A következő elemet adja vissza:}
Function Kovetkezo(P:PRekord)PRekord;
begin
If P=NIL then Kovetkezo:=NIL
else Kovetkezo:=P^.Kov;
end;
{Lista kiírása:}
Procedure Listakiir;
var
P:PRekord;
begin
P:=Start;
While Kovetkezo(P)<>NIL do
begin
P:=Kovetkezo(P);
Writeln(P^.Nev);
end;
end;
{Hozzáadás a végéhez:}
Procedure Vegehezad(S:String);
var
P:PRekord;
begin
P:Start;
While Kovetkezo(P)<>NIL do P:=Kovetkezo(P);
P^.Kov:=Ujelem(S);
end;
{Egy elem beszúrása egy adott elem mögé: (probléma, ha nagyobb elemet adunk meg, mint a lista elemeinek száma)}
Procedure Adotthelyrebeszur(S:String;I:Integer);
var
P,Puj:PRekord;
begin
P:=Start;
While (Kovetkezo(P)<>NIL) and (I>0) do
begin
P:=Kovetkezo(P);
I:=I-1;
end;
Puj:=Ujelem(S);
Puj^.Kov:= P^.Kov;
P^.Kov:=Puj;
end;
{Elem törlése:}
Procedure Torol(I:Integer);
var
B,P:PRekord;
begin
P:=Start;
I:=I-1;
While (Kovetkezo(P)<>NIL) and (I>0) do
begin
P:=Kovetkezo(P);
I:=I-1;
end;
B:=Kovetkezo(Kovetkezo(P));
If P^.Kov<>NIL then FreeMem(P^.Kov,SizeOf(TRekord));
P^.Kov:=B;
end;
{Hely keresése rendezett beszúráshoz:}
Function Helyetkeres(S:String):Integer;
var
P:PRekord;
I:Integer;
begin
P:Start;
I:=0;
While (Kovetkezo(P)<>NIL) and (Kovetkezo(P) ^.Nev<S) do
begin
I:=I+1;
P:=Kovetkezo(P);
end;
Helyetkeres:=I;
end;
{Rendezett beszúrás:}
Procedure Helyrebeszur(S:String);
var
I:Integer;
begin
I:=Helyetkeres(S);
Adotthelyrebeszur(S,I);
end;
{Gyors rendezett beszúrás:}
Procedure Helyrebeszurgyors(S:String);
var
P,Puj:PRekord;
begin
P:=Start;
While (Kovetkezo(P)<>NIL) and (Kovetkezo(P) ^.Nev<S) do
P:=Kovetkezo(P);
Puj:=Ujelem(S);
Puj^.Kov:=P^.Kov;
P^.Kov:=Puj;
end;
{A lista elejétől a végéig törli az elemeket:}
Procedure Teljeslistatorol;
var
P,Puj:PRekord;
begin
P:Start;
While Kovetkezo(P)<>NIL do
begin
Puj:=Kovetkezo(P);
FreeMem(P^.Kov,SizeOf(TRekord));
P^.Kov:=NIL;
P:=Puj;
end;
Start^.Kov:=NIL;
end;
Begin
Listainit;
Vegehezad(‘Alma’);
Vegehezad(‘Barack’);
Adotthelyrebeszur(‘Balazs’,1);
Helyrebeszur(‘Csongor’);
Helyrebeszurgyors(‘Tibor’);
Torol(2);
Listakiir;
Teljeslistatorol;
end;