10.4.5 Implementing ADTs with Arrays

10.4.5 Implementing ADTs with Arrays

A stack, queue or linked list describes how stored data behaves and which operations may be performed. An implementation explains how those abstract rules can be represented using actual storage.

One common implementation uses one-dimensional arrays together with pointer variables. The pointers record important positions such as the top of a stack, the front and rear of a queue, or the first active and unused nodes in a linked list.

From an Abstract Type to an Implementation

An Abstract Data Type defines the available operations and the way data is accessed. It does not require one particular internal representation.

Arrays provide one possible implementation. Pointer variables and index values are then used to preserve the required behaviour.

Implementing a Stack with a 1D Array

Stack items can be stored in consecutive array elements. A variable called TopPointer identifies the array index containing the current top item.

In this example, TopPointer = 2, so Token is the top item.

Push

To push a value, the program first checks that another array position is available. The top pointer is moved to the next position and the new item is stored there.

Pop

To pop a value, the program reads the value at the current top position. The top pointer is then reduced so that the item below becomes the new top.

Implementing a Linear Queue with an Array

An array-based queue normally requires two pointers:

• FrontPointer identifies the item that will leave next.
• RearPointer identifies the most recently added item.

If FrontPointer = 2 and RearPointer = 4:

• Nova is the next value to be removed.
• Pixel is the most recently enqueued value.
• A new item would normally be stored after index 4.

Moving every remaining value towards index 0 would make those positions available, but repeated shifting is inefficient.

Reusing Space with a Circular Queue

A circular queue treats the array as though the position after the upper bound were the lower bound. The rear pointer can therefore wrap to the beginning of the array.

Suppose:

• FrontPointer = 4
• RearPointer = 1

The queue is read from the front, wrapping after index 5:

Implementing a Linked List with Parallel Arrays

A linked list can be represented using two parallel 1D arrays:

• a data array containing the stored values;
• a pointer array containing the index of each node's successor.

The same index in both arrays represents one node.

If StartPointer = 2, follow the active chain:

1. Index 2 stores Atlas and points to index 0.
2. Index 0 stores Mango and points to index 4.
3. Index 4 stores Quartz and points to -1.

Managing Unused Nodes with a Free List

Unused array positions can form a second linked chain called the free list.

A variable called FreeListPointer identifies the first available node. In the previous example:

Allocating a free node

1. Read the index stored in FreeListPointer.
2. Save the next free index stored in that node.
3. Move FreeListPointer to the next free index.
4. Store the new data in the allocated position.
5. Change its pointer so that it joins the active list.

Returning a deleted node

1. Bypass the node in the active list.
2. Make the released node point to the old first free node.
3. Move FreeListPointer to the released index.

Using an Array of Records

Instead of using two parallel arrays, each node can be represented by one record containing its data and pointer fields.

TYPE NodeType
    DECLARE Data : STRING
    DECLARE Next : INTEGER
ENDTYPE

DECLARE Node : ARRAY[0:5] OF NodeType

Individual fields can then be accessed using dot notation:

Node[2].Data
Node[2].Next

Comparing the Implementations

Interactive: ADT Array Implementation Lab

Choose a structure and perform an operation. The widget shows the physical array, pointer state and logical order.

Common Mistakes and Misconceptions

Practice

Review