Pointer Quickly

Pointers: The Essentials

Class Pair - References

• Class Pair uses references:

   class Pair{
      int x, y;
      Pair(_x, _y){x = _x; y = _y}
   }
   // Client - Memory diagram ...
   ...
   Pair a, b;
   a = new Pair(1, 2);
   b = new Pair(3, 4);

   System.out.println(a.x);
   System.out.println(b.x);
   

Type Pair With Pointers!

• Type Pair implemented using pointers: :

   -- Client - Memory diagrams ...

   type Pair is record
      x, y: Integer;
   end record;

   type PairPtr is access Pair;

   g: Pair := (55, 66);

   p, q: PairPtr;  -- Initialized to Null
begin
   put(g.x);

   p := new Pair'(11, 12);
   put(p.x);

   q := new Pair;

   q.all := g;

   put(q.x);
   put(q.all.x);
   

Linked Lists!

• Linked list of integers 1, 2, 3: draw picture
• Linked lists use two types:

   type Node is record
      data: Integer;
      next: NodePtr;
   end record;

   type NodePtr is access Node;

   p: NodePtr;
   

• Compile?


• Create a list:

   p := new Node'(1, new Node'(2, new Node'(3, null)));
   

• How do we do this in several statements
• Which integer to add first.

Lengthen the Linked List

• How to add 0? Must do steps in order
1. Allocate node
2. Make new node point to existing first node
3. Make pointer to list point to new node
4. Can you do this in 1 statement?


• How to add 4? Must access 3:
• Access 3 directly
• Access last node if list has unknown length

Types Node and NodePtr: Ada vs Java

• Reference variables have a type, objects have a class


• Two distinct types in Ada

How to Declare

• How to deal with circular definition: Incomplete definition

   type Node;   -- Incomplete type

   type NodePtr is access Node;  -- Size?

   type Node is record   -- Completion
      data: Integer;
      next: NodePtr;
   end record;


   p: NodePtr;
   

Dynamic Stacks and Queues

• Can grow as needed!


• Notes on Pointers, Linked Lists, Stacks and Queues, Other Uses

Other Uses of Pointers

• Use pointers in to allow arrays and records contain data of unknown size!


• Notes on Pointers, Linked Lists, Stacks and Queues, Other Uses

Other Topics on Pointers

• Errors (Null pointers, garbage, dangling references) and solutions


• Memory allocation: Stack, Heap, Static


• Looking at Addresses


• See Notes on course page