Category : C++ Source Code
Archive   : WLIB.ZIP
Filename : WLINK.DOC

 
Output of file : WLINK.DOC contained in archive : WLIB.ZIP
Wheaton Library Linked List Documentation

February 22, 1991
May 15, 1992 (minor tweaks)
October 21, 1992 (minor update)

Copyright (c) 1992, 1993 by Paul Wheaton

Note that this documentation does not cover all of the features of the
provided in this library. For that, you will have to look at the header files.

The Wheaton Libraries are shareware. Anyone may use the libraries provided
that they do not change them. If you want to change them or if you want
phone support from me, you must pay $50. This in the hope that the hundreds
of vendors that are creating their own string libraries can go with just
one - I'm pretty tired of getting a library in that seems like it will be
pretty cool, just to find out that it uses the same identifiers as
something else and there are then link conflicts.

To make these libraries available, you need to include
and link with WLIB.LIB.

1 what is a linked list: help for the heapless
1.1 some references
1.2 my version
2 LinkedList class
2.01 Root()
2.02 Cur()
2.03 Size()
2.04 Top()
2.05 Num()
2.06 Next()
2.07 Prev()
2.08 Last()
2.09 Insert()
2.10 Add()
2.11 Append()
2.12 Push()
2.13 DelCur()
2.14 DelCurObj()
2.15 Pop()
2.16 operator[]
3 custom linked list classes
4 Stack class
5 Queue class



1 what is a linked list: help for the heapless

1.1 some references

Perhaps the best way to learn about linked lists is to go one of the
foremost authorities: In the book "Algorithms + Data Structures =
Programs" by Niklaus Wirth (1976 Prentice-Hall) in the chapter
"Dynamic Information Structures" under the section "Linear Lists" is
a complete tutorial.

The book "Structure and Interpretation of Computer Programs" by
Abelson, Sussman and Sussman (1985 MIT Press) is based on the Scheme
language (a LISP dialect) so it's just thick with list stuff.
Section 2.2.1 should give you a good idea of what's going on here.

The book "An Introduction to Object Oriented Programming and C++" by
Wiener and Pinson (1988 Addison-Wesley) has the only decent C or C++
linked list reference I could find inside half an hour. See section
6.2: "An Object-Oriented Solution to Generating a Linked List"

1.2 my version

I'm going to assume that you have a pretty good grip on what a heap
is: that dynamic memory thing.

Let's say that you have a structure called a DooDad that takes up
about a thousand bytes. Let's also say that you need to keep about
a hundred of them, ordered, in memory for the sake of speed. Part
of what the user will be doing with this list is changing the order
of it.

If you wanted to do a malloc() to store all of this stuff, you'd
have to ask for about 100,000 bytes. More than Microsoft C can
handle in one malloc. Even if you could get that much memory,
what's going to happen when you try to move a DooDad from the middle
and put it at the beginning? A whole lot of time consuming memory
copying, that's what (e.g. make a 1000 byte temp copy of element 50;
shift about 50,000 bytes about 1000 bytes to the right; copy your
temp to the beginning of your data area). If you had to insert and
delete DooDads a lot, things could be unbearably slow.

Now for a linked list approach. With a tiny struct

struct Node
{
Node* PrevNode;
DooDad* Dat;
Node* NextNode;
};

and by allocating memory for your DooDads in thousand byte chunks,
you can just change the pointers that keep track of the order!
Voila'! Everything just the way you want it and without all that
copying stuff.

Linked lists are also good for bunches of different sized objects.

2 LinkedList class

This linked list class currently uses the model described above.
Sometimes called a "doubly linked list with nodes", the "doubly"
referring to the fact that the list has "previous" pointers as well
as "next" pointers. The "nodes" part refers to the pointers being
in its own record and not part of the data record.

There is only one way to create a LinkedList object. With
absolutely no parameters (e.g. "LinkedList L;"). When you add any
data to the list, you must create your data yourself and simply pass
in a pointer to your data. You are welcome to add data that is on
the heap, the stack (local variables or parameters) or the data
segment (global data). If you want to add the same object several
times, you'll just have several nodes pointing to the same place.

When the list is deleted or goes out of scope, it will delete any
nodes that may still be active. It will not delete any data that
you have connected to the list.

All of the pointers are of type "void*".

2.01 Root()

Prototype: void* Root()

The "current pointer" is changed to point to the last element in the
list and then the new "current pointer" is returned. Returns NULL if
there are no elements.

2.02 Cur()

Prototype: void* Cur()

Returns a pointer to the current element. Returns NULL if there
are no elements.

2.03 Size()

Prototype: Long Size()

Returns the number of elements in the list.

2.04 Top()

Prototype: Long Top()

Returns the index to the last element. Equivalent to Size()-1.

2.05 Num()

Prototype: Long Num()

Returns the index to the current element. Would be any number from
0 to Top().

2.06 Next()

Prototype: void* Next()

The Cur() pointer is changed to point to the next element in the
list and then the new Cur() is returned. Returns NULL if there are
no elements.

2.07 Prev()

Prototype: void* Prev()

The Cur() pointer is changed to point to the previous element in the
list and then the new Cur() is returned. Returns NULL if there are
no elements.

2.08 Last()

Prototype: void* Last()

The Cur() pointer is changed to point to the last element in the
list and then the new Cur() is returned. Returns NULL if there are
no elements.

2.09 Insert()

Prototype: Bool Insert(void* NewRec)

Will insert a new node between the previous element and the current
element. On exit, Cur() will point to NewRec. Returns False if
there was not enough memory to create a new node.

2.10 Add()

Prototype: Bool Add(void* NewRec)

Will insert a new node between the current element and the next
element. On exit, Cur() will point to NewRec. Returns False if
there was not enough memory to create a new node.

2.11 Append()

Prototype: Bool Append(void* NewRec)

Will stick a new node on the end of the list. On exit, Cur() will
point to NewRec. Returns False if there was not enough memory to
create a new node.

2.12 Push()

Prototype: Bool Push(void* NewRec)

Will stick a new node on the end of the list. On exit, Cur() will
point to NewRec. Returns False if there was not enough memory to
create a new node.

Note that this works the same way as Append(). This function is
provided for clarity in your code when you wish to use a linked list
like a stack (see the Pop() function).

2.13 DelCur()

Prototype: void DelCur()

I recommend that if this node points to data on the heap (as is most
often the case) that you should first remove your data from the heap
using the Cur() pointer.

This function will remove the current node from the list. It will
*not* do anything to the data. On exit, Cur() will point to what
would have been pointed to by Next().

2.14 DelCurObj()

Prototype: void DelCurObj()

This function will attempt to "delete" your data. This will only
work on data that has been created with "new" and does not have a
destructor. After this, it will remove the current node from the
list. On exit, Cur() will point to what would have been pointed to
by Next().

2.15 Pop()

Prototype: void* Pop()

This function will delete the last node in the list and return a
pointer to what that node pointed to. On exit Cur() will point to
the new last element.

2.16 operator[]

Prototype: void* operator[](Long Index)

This operator will allow your linked list to be treated like an
array. If you want a pointer to the fifth element of your
LinkedList name "L", simply use "L[4]". A valid function call would
be something like "memcpy(L[2],L[8],400);". On exit, Cur() will
point to the same place.

3 custom linked list classes

A problem with the LinkedList class is that it will only deal with
void pointers. That means that if you want to reference a field of
a struct in a LinkedList, you will first have to take the pointer it
gives you and cast it to be a pointer to your object and then
de-reference a field. What a hassle! For example:

struct FooType
{
Char Name[40];
Long SSN;
Long BirthYear;
};

void Bar()
{
LinkedList L;
L.Add(new FooType);
strcpy(((FooType*)L.Cur())->Name,"Bob");

((FooType*)L.Cur())->SSN=123456789;
((FooType*)L.Cur())->BirthYear=1954;
}

Using the same FooType struct, we could have

CreateLinkedListClass(FooList,FooType);

void Bar()
{
FooList L;
L.Add(*new FooType);
strcpy(L.Cur().Name,"Bob");
L.Cur().SSN=123456789;
L.Cur().BirthYear=1954;
}

Note that all the parameters in your custom class accept and return
references instead of pointers.

4 Stack class

The Stack class works exactly the same as the LinkedList class.
This class is provided for readability's sake only. If you intend
to use your linked lisk like a stack, you might want to declare it
as "Stack FooStack;" rather than "LinkedList FooStack;"

5 Queue class

This class works exactly the same as the LinkedList class *except*
for the Pop() function. Pop() will delete the first node in the list
and return a pointer to what that node pointed to. On exit Cur()
will point to the new first element. So now you see how it behaves
like a Queue instead of a Stack: You Push() stuff onto the top and
Pop() them off the bottom.


  3 Responses to “Category : C++ Source Code
Archive   : WLIB.ZIP
Filename : WLINK.DOC

  1. Very nice! Thank you for this wonderful archive. I wonder why I found it only now. Long live the BBS file archives!

  2. This is so awesome! 😀 I’d be cool if you could download an entire archive of this at once, though.

  3. But one thing that puzzles me is the “mtswslnkmcjklsdlsbdmMICROSOFT” string. There is an article about it here. It is definitely worth a read: http://www.os2museum.com/wp/mtswslnk/