chapter 8

Dynamic Data Structures
Arrays are an example of a static data structure
Even if there are only a few elements in the array, all the memory gets allocated
A more efficient method would be to allocate only the space that we are actually using
This is called using dynamic data structures
Where Does Memory Come From?
The OS allocates some memory from what is called the Stack
The Stack typically holds Local Variables
Dynamic allocation is taken from what is called the Heap
Think of this as a bunch of memory, with no particular structure, but divided into arbitrary blocks
Linked Lists
The most common example of a dynamic data structure is the linked list
A linked list typically consists of:
a data part
some overhead

Linked Lists (cont.)
Linked Lists have the following general structure:
Access (or Allocation) Types
Recall what a RECORD declaration looks like:
TYPE RecType IS RECORD
    . . .Fields. . .
END RECORD;
. . .
MyRecord : RecType;
The variable MyRecord is of type RecType
Access (or Allocation) Types (cont.)
To declare a Pointer to this record type:
TYPE RecPointer IS ACCESS RecType;
P1, P2, P3 : RecPointer;
This allocates space for a Pointer to a record of type RecType
It does NOT allocate space for the whole record, just the pointer
In order to allocate space for the whole record, we use the NEW keyword
??
Creating a Linked Structure
TYPE ElectricityType IS ( DC, AC );

TYPE Node;
TYPE NodePtr IS ACCESS Node;
TYPE Node IS RECORD
Power : ElectricityType;
Volts : Natural;
Next : NodePtr;
END RECORD;
Pointer Manipulation
P : NodePtr;
Q : NodePtr;
R : NodePtr;

P : NEW Node;
Q : NEW Node;

P.ALL.Power := AC;
P.ALL.Volts := 115;
Q.ALL.Power := DC;
Q.ALL.Volts := 12;
Pointer Manipulation (cont.)
Pointer Manipulation (cont.)
Pointer Manipulation (cont.)
Linking Things Together
Before We Go On...
Given P1 and P2 of type NodePtr, and S of type Node:
Allocation: P1 := NEW Node;
Assignment: P2 := P1;
Dereferencing: S := P1.ALL;
Equality/Inequality: IF P1 = P2 THEN
Different from: IF P1.ALL = P2.ALL THEN
What is the difference between P and P.ALL?
Returning Memory to the Heap
We might want to return a piece of dynamically allocated memory it:
Ada provides a GENERIC operation for this
GENERIC
TYPE Object IS LIMITED PRIVATE;
TYPE Name is ACCESS Object;
PROCEDURE Unchecked_Deallocation(
     X : IN OUT Name );
Returning Memory to the Heap (cont.)
To Instantiate a usable procedure from this generic:

PROCEDURE DisposeNode IS
NEW Unchecked_Deallocation(
     Object => Node, Name => NodePtr );
And to use it:

DisposeNode( X => P );
Watch for Dangling Pointers!!
Operations on Linked Lists
Major operations:
AddToFront( ): Prepend an item to the list
AddToEnd( ): Append an item to list
Copy( ): Return a complete copy of a list
Traverse( ): Display the contents of each data element in the list
Procedure AddToFront
PROCEDURE AddToFront( L : IN OUT LIST;
    Word : IN WordType ) IS
Temp : List;
BEGIN -- AddToFront
Temp := NEW ListNode;
Temp.ALL.Word := Word;
Temp.ALL.Next := L;
L := Temp;
END AddToFront;
Recursive Traverse
PROCEDURE Traverse( L : IN LIST ) IS
BEGIN -- Traverse
IF L = NULL THEN -- Stopping Case
    RETURN;
ELSE             -- Recursion Case
    Ada.Text_IO.Put( Item => L.ALL.Word );
    Ada.Text_IO.Put( Item => “. . .”);
    Traverse( L => L.ALL.Next ); -- Recurse
END IF;
END Traverse;
Recursive AddToEnd
PROCEDURE AddToEnd( L : IN OUT LIST;
    Word : IN WordType ) IS
BEGIN -- AddToEnd
IF L = NULL THEN -- Stopping Case
    L := NEW ListNode’( Word, NULL );
ELSE             -- Recursion Case
    AddToEnd( L.ALL.Next, Word );
END IF;
END AddToEnd;
Recursive Copy
FUNCTION Copy( L : IN List ) RETURN List IS
BEGIN -- Copy
IF L = NULL THEN -- Stopping Case
    RETURN NULL;
ELSE             -- Recursion Case
    RETURN NEW ListNode’( L.ALL.Word,
                 Copy( L.ALL.Next ) );
END IF;
END Copy;

Improvements?
What is the space complexity of Traverse?

What is the space complexity of AddToEnd?

What is the space complexity of Copy?
Iterative Traverse
PROCEDURE Traverse( L : IN LIST ) IS
Current : List; -- Point to Each node in turn
BEGIN -- Traverse
Current := L; -- Initialize Loop
WHILE Current /= NULL LOOP
    Ada.Text_IO.Put( Item =>
                     Current.ALL.Word );
    Ada.Text_IO.Put( Item => “. . .”);
    Current := Current.ALL.Next; -- Increment
END LOOP;
END Traverse;
Iterative AddToEnd
PROCEDURE AddToEnd( L : IN OUT LIST;
    Word : IN WordType ) IS
Current : List; -- Point to Each node in turn
BEGIN -- AddToEnd
IF L = NULL THEN
    L := NEW ListNode’( Word, NULL );
ELSE
    Current := L; -- Initialize Loop
    WHILE Current.ALL.Next /= NULL LOOP
      Current := Current.ALL.Next; -- Increment
    END LOOP;
    Current.ALL.Next := NEW ListNode’( Word, NULL );
END IF;
END AddToEnd;
More Improvements?
What is the runtime complexity of AddToFront?

What is the runtime complexity of AddtoEnd?
Linked Lists with Head and Tail Pointers
TYPE ListNode;
TYPE ListPtr IS ACCESS ListNode;
TYPE ListNode IS RECORD
Word : WordType := “###”
Next: ListPtr;
END RECORD

TYPE List IS RECORD
Head : ListPtr;
Tail : ListPtr;
END RECORD;
Ordered Lists
Typically, you will want to order your linked list by some key.
To do this, you need to handle 4 main cases:
You are inserting into an empty list
You are inserting at the front of the list
You are inserting at the end of the list
You are inserting somewhere in the middle of the list
Gotchas To Be Wary Of
Dereferencing a NULL pointer
instead of:
IF ( P.ALL.ID /= 9999 ) AND
   ( P /= NULL ) THEN
use:
IF ( P /= NULL ) AND THEN
   ( P.ALL.ID /= 9999 ) THEN
Gotchas To Be Wary Of (cont.)
Infinite Loops
It is a common mistake to have a WHILE loop that executes forever
Forget to initialize
Forget to increment
Ptr := Ptr.Next;
It is also a common mistake to forget an exit test in a recursive algorithm
Gotchas To Be Wary Of (cont.)
Off-By-One errors
It is a common error when traversing a list to miss your target by one, because pointers are touchy
Solution:
Insert Put statements in critical points
Draw pictures of what is happening at each step in your algorithm