RxSLR14 - Data Structures

OCR A-Level Computer Science (H446)

What are linked lists composed of?

Nodes and pointers

What does the start pointer identify? What do the pointers point to?

• The first node

• The next node

How can linked lists be implemented?

By using arrays or objects

What are the steps for adding an item to a linked list?

• Checks if there is free memory for a node, else output error

• Updates free pointer to the next available storage space

What are the steps for deleting an item to a linked list?

• Checks if list is empty, outputs error if so

What is a tuple?

• An ordered set of values of any type

• Immutable (values CANNOT be changed)

• Regular brackets

What are records?

• A structure with a collection of related fields

• Each field is a variable and can have different data types

What is a graph?

• Dynamic, non-linear data structure

• Consists of nodes and pointers

• Each node can have any number of pointers

• Directed, undirected, weighted

• Searched using Depth-first or Breadth-first search

What is a tree?

• Type of graph

• Each tree has a root node, child nodes, and leaf nodes at bottom

• 1-direction

• Doesn’t cycle

• Not weighted

What are binary trees?

• Special case of graph

• Each node can only have 0, 1, or 2 pointers

• Can be stored as an array

What are stacks?

• Data structure using LIFO

• Items push() and pop().

• Can peek() without removing data

• Single stack pointer (top)

What are queues?

• Data structure using FIFO

• Items enqueue() and dequeue()

• Can peek() at item at front of queue

• Two pointers (front & back)

What happens when you add an item to a stack?

• push() operation

• Checks if stack is full, outputs error if so

• If not full, increment stack pointer

• Insert new item at location of stack pointer

What happens when you remove an item from a stack?

• pop() operation

• Checks if stack is empty, outputs error if so

• If not empty, item at stack pointer deleted

• Stack pointer decrements

What happens when you add an item to a queue?

• enqueue() operation

• Check if queue is full, output error if so

• If not full, increment