1. 4. 2 Data Structures

Question 1

Arrays / Records

Answer 1

• Array is an ordered, finite set of elements of a single type, one dimensional (1D), two dimensional (2D) and three dimensional (3D) arrays described below
• 1D linear array, zero indexed (1st element pos 0)
• 2D table or spreadsheet, when searching first go down rows then across columns to find pos
• 3D multi paged spreadsheet, multiple 2D arrays, to select element use AryNme(z,y,x) where z array number, y row number, x column number
• Record is a row in a file made up of fields, to create row variable first declared then attributes can be accessed
• Example Variable- fighter : fighterDataType
• Attributes accessed- fighter.FirstName

Question 2

Lists / Tuples

Answer 2

• Ordered items that can occur more than once as well as be a different data type, stored non-contiguously (do not need to be stored next to each other in memory). For manipulation look at below and refer to Photos
• isEmpty(), append(value), remove(value), search(value), length(), index(value), insert(position, value), pop(), pop(position)
• Tuple is an ordered set of values of any data type, immutable (cannot be altered), Elements cannot be added or removed after creation, initialized using (), retrieval same as an array using name and []

Question 3

Linked Lists

Answer 3

• Linked list is a dynamic data structure holds ordered sequence, item = node contains data field, link or pointer field (another address)
• Data field contains value of actual data that is part of list
• Pointer field contains address of next item in list
• Linked lists store index of first item in list as a pointer
• When traversing algorithm begins at index given by “Start” pointer and outputs values at each node until it fins that the pointer field is empty or null (end of list)
• Refer to image in Photos
• Disadvantages- Wastes memory does not remove values from list ignores them, items cannot be directly accessed

Question 4

Graphs

Answer 4

• Graph is a set of vertices / nodes connected by edges / arcs; Categories of graph shown below
• Directed Graph- The edges can only be traversed in one direction
• Undirected Graph- The edges can be traversed in both directions
• Weighted Graph- A cost is attached to each edge
• Adjacency Matrix Advantages- Convenient to work with (quick access times), easy to add nodes
• Adjacency list Advantages- More space efficient for large sparse networks
• View Photos to see how above looks and works

Question 5

Stacks

Answer 5

• Last In First Out (LIFO) data structure
• Items added and removed from top of stack
• Used to reverse an action (go back web page, undo button)
• Can be static (easier to implement more efficient use of memory) or dynamic
• Implemented using a pointer, points top of stack where next piece data inserted
• View Photos to see how to manipulate stack

Question 6

Queues

Answer 6

• First In First Out (FIFO) data structure
• Items added end of queue removed front of queue
• Used in printers, keyboards and simulators
• Linear queue consists of an array, makes use of two pointers one front one back
• enQueue(item) is how items are added to a queue
• deQueue(item) is how items are removed from a queue
• deQueue() on its own removes first value in queue
• .isEmpty() checks queue empty
• .isFull() checks queue full
• Disadvantage of Linear- When items removed addresses in array cannot be used again, ineffective implementation of a queue
• Circular queue coded in a way once rear pointer = max size of queue, can loop back to front to store values there, use space more effectively harder to implement