home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
The World of Computer Software
/
World_Of_Computer_Software-02-385-Vol-1of3.iso
/
l
/
lnklst10.zip
/
LINKLIST.DOC
< prev
next >
Wrap
Text File
|
1993-01-19
|
10KB
|
279 lines
Linked List algorithms and implementation, version 1.0.
All code and documentation is (c) Copyright 1993 SpeedSOFT
Development and Ben Morris. All rights reserved.
INTRODUCTION
---------------------------------------------------------------------------
This code implements a linked-list algorithm using standard techniques
(ie: a dual circular list). Although standard, the code is fast and
memory-efficient.
The purpose behind writing this code was simple: nobody else would give
me any. It's funny, actually, because it took about 30 minutes to write.
Is it my imagination, or are people becoming more selfish? <grin>.
Anyway, enough moral lecturing.
DESCRIPTION
---------------------------------------------------------------------------
(If you already know what a linked list is (and what its benefits are),
then skip to the next section.)
A linked list is an alternative to a 'data array'. Although slightly more
difficult to use than an array (which is built-in to any language), a
linked list is faster and uses memory more efficiently.
For example: Suppose you needed to load a lot of structured information
(ie: Each 'block' of information is identical in size and structure) into
memory. The obvious way to do so would be to declare an array of 'blocks'
and load the data into the array sequentially. However, there is no
conventional (or simple) way to expand an array should it be too
small to receive all the data. On the other hand, there would be wasted
memory in the array if it was not completely used. And, if members of the
array have to be moved or deleted, a lot of processor time may be required
to reassign the necessary pointers in the array.
A linked list solves the above problems with elegance. The first, memory
usage, is quite simple: A linked list will use only the amount of memory
required, and not a byte more (excluding pointer overhead). Each 'node'
in the list (identical to an index in an array) contains three members.
The first and second are pointers to the previous and subsequent nodes
respectively, and the third node is a 'data' pointer. It is this third
member that points to the data stored in the node.
Although each node in this linked list method requires 12 or 6
additional bytes (depending on the memory model used) for pointers, the
savings are quite considerable when using a large amount of data.
The other memory advantage is that each node in the list can contain a
different size data block. Of course, it is up to the programmer to
determine and retrieve the size of each block.
Linked lists can be dynamically expanded and contracted by inserting and
deleting nodes (see next section for details). Deleting nodes in a linked
list is considerably faster than doing so with arrays: A maximum of four
pointers are re-arranged in a list. The same goes for inserting nodes
anywhere in the list.
I did mention that linked lists are more awkward than arrays to implement.
While indeces in an array can be referenced simply by using pointer
mathematics (ie: files[14]), the data in a linked list must be retrieved
with a call to a function.
CAUTIONS. A linked list is only speed-effective if no (or very little)
random access is performed.
USAGE
---------------------------------------------------------------------------
NB: The 'C' structure NODE (and NODEPTR) is used with all linked-list
functions in this source.
The header file LINKLIST.H must be #included to use the code.
Each linked list must have a 'head' node. This node, which is passed to
some functions, is used by LINKLIST.C. NOTE that once defined, the head
node MUST NOT BE CHANGED IN ANY WAY outside of LINKLIST.C.
To define the head node, assign it the return value from the function
InitList(). For example,
NODEPTR head = InitList();
Calls to the functions NodeInsert() and NodeDelete() allow you to insert
and delete nodes in the list. For a detailed function reference, see below.
Data is stored in the 'data' member of a NODEPTR structure. The data
member can be allocated with a call to NodeInsert(), or with a call to
malloc() (or compat.) outside of LINKLIST.C. Note that the head node's
data member is always NULL.
Once you're finished with the list, call DestroyList() to free all
allocated memory.
FUNCTIONS
---------------------------------------------------------------------------
NOTE: Since LINKLIST.C doesn't depend on any internal variables, you can
use as many linked lists as the system has memory for. The one
restriction is that you must define a different head node for every list
you use.
The only external functions used in LINKLIST.C are malloc() and free().
The calls to these functions can be replaced by compatible
substitutes.
ALL functions here will work even if the head node is the only one defined
in a list.
.................................................................InitList()
Function: Initializes a linked list.
Call : NODEPTR InitList( void );
Returns : Pointer to the head node, or NULL: Not enough memory.
Remarks : Call this function to initialize the 'head node' for a list.
Subsequent calls to functions that require a 'head node' as one
of the parameters should be passed the pointer returned from
this function.
...............................................................NodeInsert()
Function: Inserts a node in the linked list.
Call : NODEPTR NodeInsert( NODEPTR previous, size_t len );
previous: A pointer to the previous node in the list. The new
node will be inserted after this node (and before any
subsequent nodes). You can use the head node here,
if desired.
len : The number of bytes to allocate for the 'data' member
of the NODEPTR structure. Specify 0 here if you
don't want to allocate memory immediately.
Returns : A pointer to the allocated and inserted node, or NULL: Not
enough memory.
Remarks : NodeInsert() inserts a node in the list after the node specified
in 'previous'. Unless the parameter 'len' is set to 0, memory
will be allocated in the 'data' member of the NODEPTR.
Note that the data member is never used inside of LINKLIST.C.
...............................................................NodeDelete()
Function: Deletes a node from the linked list.
Call : void NodeDelete( NODEPTR ndp );
ndp : A pointer to the node to delete from the list.
Returns : Nothing.
Remarks : NodeDelete() will delete 'ndp' from the linked list, free its
'data' member (if allocated), and free the memory allocated in
'ndp'. Note that NO error checking is performed to see that the
pointer passed is valid.
.............................................................NodeNumtoPtr()
Function: Converts a node number to its pointer in the list.
Call : NODEPTR NodeNumtoPtr( int num, NODEPTR head_ndp );
num : The number of the node to return a pointer for
(starting at 0).
head_ndp: The head node in the list.
Returns : A pointer to the retrieved node, or NULL: There is no node with
that number.
Remarks : NodeNumtoPtr() will return a NODEPTR corresponding to its number
(sequence) in the list. If NULL is returned, then the number
passed was too large (ie: the list doesn't contain that many
entries).
.............................................................NodePtrtoNum()
Function: Converts a node pointer to its number (sequence) in the list.
Call : int NodePtrtoNum( NODEPTR sndp, NODEPTR head_ndp );
sndp : The pointer to convert to a number.
head_ndp: The head node in the list.
Returns : The number (sequence) of 'sndp' in the list, or -1: 'sndp' was
not found.
Remarks : NodePtrtoNum() will return a number corresponding to its NODEPTR
in the list (starting at 0). If -1 is returned, then the
NODEPTR passed was not found in the list.
.................................................................NodePrev()
Function: Returns a node's previous node in the list.
Call : NODEPTR NodePrev( NODEPTR ndp );
ndp : The node whose previous node is to be returned.
.................................................................NodeNext()
Function: Returns a node's next node in the list.
Call : NODEPTR NodeNext( NODEPTR ndp );
ndp : The node whose next node is to be returned.
................................................................NodeFirst()
Function: Returns a pointer to the first (non-head) node in the list.
Call : NODEPTR NodeFirst( NODEPTR head_ndp );
head_ndp: The head node of the list.
.................................................................NodeLast()
Function: Returns a pointer to the last node in the list.
Call : NODEPTR NodeLast( NODEPTR head_ndp );
head_ndp: The head node of the list.
................................................................NodeTotal()
Function: Returns the total number of nodes in a list (excluding the head
node).
Call : int NodeTotal( NODEPTR head_ndp );
head_ndp: The head node of the list.
..............................................................DestroyList()
Function: Frees all memory for a list (destroys it).
Call : void DestroyList( NODEPTR head_ndp );
head_ndp: The head node of the list.
NOTE : The head node is destroyed in this call!