Board index » delphi » Linked Lists

Linked Lists

Can somebody out there please give me a few suggestions as to what to use
linked lists for. Is it possible for a linked list to be greater than about
210 records in real mode, or do extra memory work and switches need to be
set?

Thanx Mintrix

 

Re:Linked Lists


Quote
In article <01bbbb52$68177220$LocalHost@spickers> Mark wrote:
>Can somebody out there please give me a few suggestions as to what touse
>linked lists for. Is it possible for a linked list to be greater thanabout
>210 records in real mode, or do extra memory work and switches need tobe
>set?

Depending on the size of your record, available free memory, etc
you could probably link somewhere between 10 and 15 thousand records
in a real mode program!

Stacks are easily implemented w/ single linked lists.  Queues are
best implemented /w double linked lists, but small ones could be
implemented w/ single linked lists.

Large lists that need to be searched are best implemented using a
balanced binary tree.

Stacks are a LIFO (last-in/first-out) structure that are often
described as being similar to a stack of dinner plates.  As they
are washed and dried they are placed on the top of the stack.  When
you need one, you also take it from the top of the stack.  Since
you only need reference the top most item, a single linked list is
ideal.  To stack an item you store the current top of stack in the
new record and place its address in the stack_top variable.

A queue is a FIFO (First-in/First-out) structure often described as
a line at the check-out register.  New records are added to the end
of the line and are removed from the head of the line.  Adding a
record to a queue is similar to pushing a record on a stack.  However,
when and item is removed, you need to know where the item "behind" it
is located.  To determine this in a single linked list you would have
to start with a pointer pointing to the top of the stack and walk it
through the list until the Next record's next pointer wasn't grounded.
This might go relatively quick for a small list, but could be a serious
performance factor with large lists.  Enter the double linked list.  
Not only does it have a link to the next item in the list, but also
has a link to the precious item in the list.  It allows working or
accessing both ends of a list with similar overhead regardless how
large the list may be.

Both lists are linear by design, so when you want to locate something
other than the top record in a single linked list, or either end of a
double linked list you need to consider alternative methods that
provide a more random and somewhat indexed method.  This is often
fulfilled by binary trees.  Nodes in this structure typically have
a left and right link, and sometimes a link to its parent node.  The
link to the parent is often used to facilitate iterative processing.
A tree that is not properly maintained can easily degrade to being
no better that a single linked list.  To insure that you get optimum
performance the tree has to be balanced.  (AVL, depth, etc).

I've given a quick outline of stacks, queues, and trees implemented
using linked lists.  Similar functionally can be had by using a
collection, or a sorted collection.  While collections are easy to
use, they have their own shortcomings.  Take the case of a sorted
collection reading a list of unsorted items.  Each time a new
item needs to be inserted into the list, all pointers at and above
the new item's position will have to be blocked moved.  Loading a
collection in any order other than appending new records is going to
cost you a sever performance penalty.  (Hint, load the collection
by appending items, then sort it).  A balanced tree allows an almost
binary search and new items are appended at the end of a list.
Balancing consists of one or two rotations (swapping 6-12 pointers),
but does not have to be done often.  It is a consistently fast
method of sorting.  There is little difference in the time it takes
to sort a series of sorted, reversed, or random items.

For an example of a double linked list look at BLOCKIO available from
my home page.  Blocks of data are linked to a local list of all
blocks for a particular file, and to a global list of all blocks for
all files, blocks are also stored in a tSortedCollection index by
offset.  This linkage is part of the LRU (least-recently-used)
algorithm implemented by the unit.

Also look at the tAsort object in AVL.  It uses an AVL tree to sort
records, a stack to hold information about each block of records
flushed to disk, and another tree structure when it merges these
blocks into an ordered sequence of records.  

FYI, the HLL overhead (especially heap management) is such that the
optimized assembly language utilities ASORT and VSORT are many times
faster.  Due to file i/o overhead, protected mode is even slower!

Other uses would be a double linked list to facilitate a free form
data entry program where fields or groups of fields can repeat zero
or more times and could contains any number (hundreds!) of occurrences.

While generating a document, a single-linked list of references where
the number of types of references and the number of occurrences aren't
known until runtime can provide information to allow back-patching
forward page references, as well as providing necessary information
for indexes.

I'm sure others can give you many more ideas.  The list just keeps
going, and going, and going, ...

BTW, performance is something that should be considered in the context
of the application.  For example, a data entry program running on a
10 mhz AT can traverse the links in a 700 element to list to sum the
values of a particular field type, count occurrences of a field, check
for duplicate entries, or otherwise validate an entry and be back
for the next key-stroke before a proficient data entry technician
(read 120 wpm typist) would know that you had taken such a side trip.

    ..red

Re:Linked Lists


On 16 Oct 1996 11:09:56 GMT, "Mark" <spick...@powerup.com.au> wrote:

Quote
>Can somebody out there please give me a few suggestions as to what to use
>linked lists for. Is it possible for a linked list to be greater than about
>210 records in real mode, or do extra memory work and switches need to be
>set?

>Thanx Mintrix

Dear Mintrix

I use double linked lists for many things in real mode dos programs.
These types of lists are useful for items of which you do not know of
in advance how many there will be, and when you want to insert and
remove items at random locations (other people will surely think of
other reasons to use them....) Here's a short list:

- Graphical viewports, layers, and windows.
- Sprites for animation.
- Segments of and markers in a sound recording.
- Lists.... like this one...
- Sorting algorithms of big items.
- Database like file handling.
- many more.

Here's the two basic types I use for a double linked list:

TYPE
{defining a Node of a list}
  NodePtr    = ^NodeType;
  NodeType   = RECORD
                 QN_Previous,
                 QN_Next      :NodePtr;
               END;
{defining the Header of a list}
  HeaderPtr  = ^HeaderType;
  HeaderType = RECORD
                 QH_Head,
                 QH_Tail      :NodePtr;
               END;

Again, other people will favour other methods, but they all are
basically the same. Now when I want to define a node which can contain
a string of maximal 80 characters I would do:

TYPE
  Str80NodePtr  = ^Str80NodeType;
  Str80NodeType = RECORD
                    S80_Node      :NodeType;
                    S80_Str       :STRING[80];
                  END;

This type will occupy 84 bytes, which is 96 in reality because the
heap manager of borland pascal uses chuncks of 16 bytes. So, how much
memory would 210 nodes and one header occupy? 210*96+16=20176, or
almost 20 Kb. Not too much, I think...

Peter

wpdej...@worldonline.nl

Re:Linked Lists


Quote
Mark wrote:

> Can somebody out there please give me a few suggestions as to what to use
> linked lists for. Is it possible for a linked list to be greater than about
> 210 records in real mode, or do extra memory work and switches need to be
> set?

> Thanx Mintrix

Hi Mark!

1.) Actually I have never really needed linked lists, yet. But I read about them being used
building balanced trees. Of course you can use them instead of your array[..] of ... but it is
more convenient and faster to access data by means of arrays (lazy me thinks; for that reason I
never really considered them for my programs).

2.) Is there a reason for your "210" records (are your records bigger than let's say 1.5kB)? You
have your free conventional memory (TP) (or this plus your free extended memory (BP, target
protected mode)) and memory is allocated for each list element indiviually until all memory is
allocated.
Could you please be more specific about "extra memory work and switches"?

I' m not sure this helps, but I would like to help in case you could provide more specific
information.

Cheers,

Bernd

Re:Linked Lists


Quote
> Can somebody out there please give me a few suggestions as to what to use
> linked lists for. Is it possible for a linked list to be greater than about
> 210 records in real mode, or do extra memory work and switches need to be
> set?

   Aren't you coming at this the wrong way?  I mean, a technique (such as
L/Ls) is a solution to a specific problem, rather than a solution looking
for a problem.  I believe it's better to know how something works/what
it's for and be able to use it when the problem arises.
   Linked Lists are useful for applications which (1) are dynamic in
size, (2) don't require fast access to array elements, and (3) can
maintain a static order from creation (they aren't easy to reorder/sort).
There are other (and better, IMHO) ways of doing many such things, but
they don't seem to be taught in school classes.
   Your question about "more than 210 records" is meaningless, since we
know nothing about the record description - so we can't say _anything_
about L/Ls' applicability for your application.  I will say that if total
Heap memory is a problem (it's always an issue with L/Ls) and the record
is enormous, L/Ls and other techniques won't help you at all - you need
to have enough Heap memory to store all the data elements, no matter how
you address/link it for access.  You have approximately 400K of
(potentially) available Heap, so you'd have to determine what you _must_
store and how to expect to access it.
   The last point is very important: how you intend to use/access the
data.  Simply having it stored in memory is a small part of the solution,
and doing it the wrong way can severely inhibit what you can do and how
your application will run.  IMO, Linked Lists are a poor compromize for
situations which either need reordering of the data or require fast
access - L/Ls can only be traversed sequentially.
   So, although L/Ls seem "kewl" from an acedemic view, their
usefullness in most programming applications is pretty much limited to
storing a lot of data and accessing it sequrentially in its stored order.
Pointer arrays have much greater applicability, in my experience.

Re:Linked Lists


Hi!

Quote
"Mark" <spick...@powerup.com.au> wrote:
>Can somebody out there please give me a few suggestions as to what to use
>linked lists for. Is it possible for a linked list to be greater than about
>210 records in real mode, or do extra memory work and switches need to be
>set?

Usually you are using linked lists, whenever you need a set of data and you
don't know the amount of data at the time of programming. E.g.: If you write a
program to sort numbers, you can:
a) Use arrays: In that case you have to give the maximum number of elements in
the program.
b) Use linked lists: You determine the number of elements during the runtime of
the program.

Of course you can use more than 210 Elements (depends on the size of the data).
You can allocate the whole heap memory with elements (I worked in TP7.0 with
2000 elements and didn't have any problems with memory). I think that there are
some options to increase the amount of available memory (if necessary).

Best regards, Andreas.

Re:Linked Lists


In a previous article, wpdej...@worldonline.nl (Peter de Jong) wrote:

Quote
>On 16 Oct 1996 11:09:56 GMT, "Mark" <spick...@powerup.com.au> wrote:

>TYPE
>  Str80NodePtr  = ^Str80NodeType;
>  Str80NodeType = RECORD
>                    S80_Node      :NodeType;
>                    S80_Str       :STRING[80];
>                  END;

>This type will occupy 84 bytes, which is 96 in reality because the
>heap manager of borland pascal uses chuncks of 16 bytes. So, how much
>memory would 210 nodes and one header occupy? 210*96+16=20176, or
>almost 20 Kb. Not too much, I think...

1.)  This type occupies 85 bytes, not 84:  you forgot the length byte of
     the strings.

2.) The BP heap manager uses EIGHT byte chunks, not 16, so your 210 node +
    1 header would occupy 210*88+8=18488 bytes.

If you are going to use a record of strings, why not use
String[83] instead of String[80]:  this gives you another 3 chars for
your longest strings without increasing the amount of space the record
really uses on the heap.

Re:Linked Lists


On 17 OCT 96 11:08:28 GMT, s...@skyfox.usask.ca wrote:

Quote
>In a previous article, wpdej...@worldonline.nl (Peter de Jong) wrote:
>>On 16 Oct 1996 11:09:56 GMT, "Mark" <spick...@powerup.com.au> wrote:

>>TYPE
>>  Str80NodePtr  = ^Str80NodeType;
>>  Str80NodeType = RECORD
>>                    S80_Node      :NodeType;
>>                    S80_Str       :STRING[80];
>>                  END;

>>This type will occupy 84 bytes, which is 96 in reality because the
>>heap manager of borland pascal uses chuncks of 16 bytes. So, how much
>>memory would 210 nodes and one header occupy? 210*96+16=20176, or
>>almost 20 Kb. Not too much, I think...

>1.)  This type occupies 85 bytes, not 84:  you forgot the length byte of
>     the strings.

Actually it is 89 bytes, you (and I) forgot that the NodeType is eight
bytes big....

Quote
>2.) The BP heap manager uses EIGHT byte chunks, not 16, so your 210 node +
>    1 header would occupy 210*88+8=18488 bytes.

Maybe yours is using eight bytes... mine is using six{*word*249} in real
mode. I think this value can be changed somewhere. For eight byte
chunks the story would be: 210*96+8=20168 bytes.

Quote

>If you are going to use a record of strings, why not use
>String[83] instead of String[80]:  this gives you another 3 chars for
>your longest strings without increasing the amount of space the record
>really uses on the heap.

Actually it was just a crude example, showing that 210 elements can be
stored in the lower 640 Kb of memory.

Peter

Re:Linked Lists


Quote
Mark (spick...@powerup.com.au) wrote:

: Can somebody out there please give me a few suggestions as to what to use
: linked lists for. Is it possible for a linked list to be greater than about
: 210 records in real mode, or do extra memory work and switches need to be
: set?

Why not use an array of pointers to your records? In this case, you can have
more than 16,300 items.

e..g,

Type
pMyRecord=^MyRecord;
MyRecord = Record {I like to use Objects for this}
   Name : String[80];
   Age  : byte;
   Address : Array[1..2] of String[80];
   ID   : Real;
   Num  : longint;
   Comments : Array[1..2] of String[80];
   Cust_FileName : String[80];
end;

Type
pRecArrayType=^RecArrayType;
RecArrayType = Array[1..16000] of pMyRecord;

Var
Cust_Rec:pRecArrayType;

The only problem with arrays is that you have to specify the maximum size at
compile time. However, they are generally easier and faster than lists. You
can also overcome the problem I referred to earlier (maximum size) by using
the syntax: array[0..0] of pMyRecord - however, this is a hack and can lead
to certain problems - and you need to turn range checking to do this.

With the example above, you can optimize memory usage - by allocating enough
memory at run time for the number of records you will need - e.g.,

Var
i, j, k:Word;

Begin
  k := GetMaxRecNums; {something that returns the upper limit of records}
  If (k>16000) then k:=16000;
  If (k < 1 ) then Halt(100);

  j := Sizeof(Pointer) * (k+2); {safety margin of 2 !!}
  Getmem(Cust_Rec, j); {allocate just enough - not the whole 16,000}
                       {but you could also just do "New(Cust_Rec)"}

  for i := 1 to k do begin
      New(Cust_Rec^[i]);
      ReadRecord(RecFile, Cust_Rec^[i]);
  end;  

  {... process Cust_Rec, etc ....}

  for i := 1 to k do begin
      WriteRecord(RecFile, Cust_Rec^[i]);
      Dispose(Cust_Rec^[i]);
  end;  

  Freemem(Cust_Rec, j);
End.
{---}

OK - this is all from the top of my head, and the code has not been
tested - but it shows the general idea.

The Chief
--------
Dr. A{*word*73}la A. Olowofoyeku (The African Chief)
Email: la...@keele.ac.uk
Author of: Chief's Installer Pro 2.91 for Win16 and Win32:
           Winner of PC PLUS Magazine Gold Award (April 1995 U.K. edition)
           http://ourworld.compuserve.com/homepages/African_Chief/
           ftp://ftp.simtel.net/pub/simtelnet/win3/install/chief291.zip  

Re:Linked Lists


Quote
A.A. Olowofoyeku (la...@cc.keele.ac.uk) wrote:

[...]

:   j := Sizeof(Pointer) * (k+2); {safety margin of 2 !!}
:   Getmem(Cust_Rec, j); {allocate just enough - not the whole 16,000}
:                        {but you could also just do "New(Cust_Rec)"}
:  
:   for i := 1 to k do begin
:       New(Cust_Rec^[i]);
:       ReadRecord(RecFile, Cust_Rec^[i]);
:   end;  

Looking back at this, I think that the ReadRecord line should read
  ReadRecord(RecFile, Cust_Rec^[i]^);

The important thing being the dereferencing of Cust_Rec^[i] ...

Same with the WriteRecord example below.

:   for i := 1 to k do begin
:       WriteRecord(RecFile, Cust_Rec^[i]);
:       Dispose(Cust_Rec^[i]);
:   end;  

The Chief
--------
Dr. A{*word*73}la A. Olowofoyeku (The African Chief)
Email: la...@keele.ac.uk
Author of: Chief's Installer Pro 2.91 for Win16 and Win32:
           Winner of PC PLUS Magazine Gold Award (April 1995 U.K. edition)
           http://ourworld.compuserve.com/homepages/African_Chief/
           ftp://ftp.simtel.net/pub/simtelnet/win3/install/chief291.zip  

Re:Linked Lists


Quote
Mark (spick...@powerup.com.au) wrote:

: Can somebody out there please give me a few suggestions as to what to use
: linked lists for. Is it possible for a linked list to be greater than about
: 210 records in real mode, or do extra memory work and switches need to be
: set?

Linked lists are great for data that could be placed in an array but
doesn't have a fixed number of segments.  For instance a phonebook may
have 50 entries in it so an array of 100 would be safe but very
wastefull.  Lets say, though, that a 4 families leave and 40 move in.  
Now the book has 110 entries.  With an array based system you would need
to get in and rewrite the code but since a linked list is dynamic you can
just add or delete records as needed without wasting resources.  This is
just a very minor example.

You can, in my experience, have more then 210 records in the linked
list.  Perhaps it is easier at times to only have part of the data file
in memory though.  If the phonebook was much more then 110 entries it
would be more efficent to have only a certain number of the records in
memory at any given time and the rest being stored solely in the data file.

Am I making any sense at all?

Anyway ... linked lists are good.

use them.

Robert

--
 .-_-.-_-.-_-.-_-.-_-.-_-.-_-.-_-.-_-.-_-.-_-.-_-.-_-.-_-.-_-.-_-.-_-.-_-.-_-.
 | Robert Horvick - <rphor...@gloria.cord.edu> - Concordia College, MN - USA |
 | Computer Science & Psychology - http://cobweb.cord.edu/horvick    [KaNiN] |
 `-_-.-_-.-_-.-_-.-_-.-_-.-_-.-_-.-_-.-_-.-_-.-_-.-_-.-_-.-_-.-_-.-_-.-_-.-_-'

For every credibility gap, there is a gullibility fill.
                -- R. Clopton

Other Threads