where : ibrtses delphi
Delphi - double linked list
disclaimer
the source code of this page may not appear correctly in certain browsers
due to special characters. Have a look at the source of this HTML page
with notepad instead
A template for a double linked list, queue and stack is shown :
unit DoubleLinkedList;
interface
type
DListNode=class(TObject)
private
next,prev:DListNode;
public
constructor create;
destructor destroy; override;
end;
DList=class(TObject)
private
fhead,ftail:DListNode;
fsize:integer;
function getsize:integer;
public
constructor create;
destructor destroy; override;
procedure append(p:DListNode);
procedure insertbefore(p,before:DListNode);
procedure remove(p:DListNode);
procedure delete(p:DListNode);
function next(p:DListNode):DListNode;
function prev(p:DListNode):DListNode;
published
property size:integer read getsize;
property head:DListNode read fhead;
property tail:DListNode read ftail;
end;
DQueue=class(DList) //FIFO
public
constructor create;
destructor destroy; override;
procedure QueueIn(p:DListNode);
function QueueOut:DListNode;
end;
DStack=class(DList)
public
constructor create;
destructor destroy; override;
procedure push(p:DListNode);
function pop:DListNode;
end;
implementation
uses Sysutils;
type EDoubleLinkedStuff=class(Exception);
constructor DListNode.create;
begin
inherited create;
next:=nil; prev:=nil;
end;
destructor DListNode.destroy;
begin
inherited destroy;
end;
function DList.getsize:integer;
begin
result:=fsize;
end;
constructor DList.create;
begin
inherited create; fhead:=nil; ftail:=nil; fsize:=0;
end;
destructor DList.destroy;
var q:DListNode;
begin
while head < > nil do
begin
q:=fhead; fhead:=fhead.next; q.destroy;
end;
end;
procedure DList.append(p:DListNode);
begin
if fhead=nil then begin
fhead:=p; ftail:=p;
end
else begin
p.prev:=ftail; ftail.next:=p; ftail:=p;
end;
inc(fsize);
end;
procedure DList.insertbefore(p,before:DListNode);
begin
if head=nil then begin
fhead:=p; ftail:=p;
end
else begin
if before=head then begin
p.next:=head; head.prev:=p; fhead:=p;
end
else begin
p.next:=before; p.prev:=before.prev;
p.prev.next:=p; before.prev:=p;
end;
end;
inc(fsize);
end;
procedure DList.remove(p:DListNode);
begin
if p=fhead then begin
fhead:=fhead.next;
if fhead=nil then ftail:=nil
else fhead.prev:=nil;
end
else begin
if p=ftail then begin
ftail:=ftail.prev;
if ftail=nil then fhead:=nil
else ftail.next:=nil;
end
else begin
p.prev.next:=p.next;
p.next.prev:=p.prev;
end;
end;
dec(fsize);
p.next:=nil; p.prev:=nil;
end;
procedure DList.delete(p:DListNode);
begin
remove(p); p.destroy;
end;
function DList.next(p:DListNode):DListNode;
begin
if p=nil then raise EDoubleLinkedStuff.create('next(DList) is nil');
result:=p.next;
end;
function DList.prev(p:DListNode):DListNode;
begin
if p=nil then raise EDoubleLinkedStuff.create('prev(DList) is nil');
result:=p.prev;
end;
constructor DQueue.create;
begin
inherited create;
end;
destructor DQueue.destroy;
begin
inherited destroy;
end;
procedure DQueue.QueueIn(p:DListNode);
begin
insertbefore(p,head);
end;
function DQueue.QueueOut:DListNode;
begin
result:=tail;
if tail < > nil then remove(result);
end;
constructor DStack.create;
begin
inherited create;
end;
destructor DStack.destroy;
begin
inherited destroy;
end;
procedure DStack.push(p:DListNode);
begin
append(p);
end;
function DStack.pop:DListNode;
begin
result:=tail;
if tail < > nil then remove(tail);
end;
notes
These templates are for one datatype only, to hold a TObject,
further steps are necessary. Usually the DListnode will be
changed to hold the data, such as an integer.
Feedback is welcome
sponsored links
Delphi
home
last updated: 23.june.99
Copyright (99,2000) Ing.Büro R.Tschaggelar