Abstract data types: linked lists, stacks, queues and trees

Learning objectives

Explain what an abstract data type is, and describe how a stack, a queue and a linked list, and (A Level) a binary tree, can each be built from an array of records together with pointers

Use a stack to store data, testing for a full or an empty stack, and describe how a stack holds return addresses while procedures call one another; (A Level) write and trace the push and pop operations

Use a linear queue and a circular queue to store data, and explain why a circular queue avoids wasting the space released at the front; (A Level) write and trace the enqueue and dequeue operations

Add, edit and delete data in a linked list held in an array, showing how the pointers and the free list are updated at each step; (A Level) write the operations that insert a node into, delete a node from and search a linked list

(A Level) Describe the structure of a binary search tree, insert a sequence of values into one, and carry out an in-order traversal, explaining why that traversal outputs the values in sorted order

Compare arrays, linked lists, stacks, queues and (A Level) trees on ease of insertion, ease of deletion, speed of searching and use of memory, and choose a structure for a stated task

(A Level) Describe a graph as an ADT of vertices and edges, which may be directed and weighted, and explain why a graph is the right structure for a stated task

(A Level) Describe a dictionary as an ADT of unique key–value pairs, and show how a stack, a queue, a linked list, a dictionary and a binary tree can each be built either from the data types a language already has or from another ADT