3.1 Data Structures

Question 1

Interpret Arrays

Answer 1

1D Arrays - A row of the same values e.g keeping a shopping list. Access an element via index.

2D Arrays (martixs) - implement columns as well as rows. acess via a column and row index.

3D Array - hard to visualise,every item is positioned using three indexes.

Question 2

Properties of arrays

Answer 2

• non dynamic data structure
• can only hold one data type
• stored contiguously in memory (elements of arrays are placed in adjacent memory locations for efficient and fast retrieval)
• allows for instant access to data via index

Question 3

What is a stack?

Answer 3

• Stacks hold data in a linear sequence
• stacks can be used as a recursive data structure
• underflows occur when an attempt is made to pop an empty stack. Overflows is when an attempt is made to add to a full stack.

LIFO (last in first out), meaning the the most recent piece of data added is the first to be removed)

uses push(), pop() and peek(). push() adds new items, pop() removes the most recent item. peek says what item is at the top of the stack.

real life example: tennis ball tube

Question 4

What is a queue

Answer 4

queue holds data in a linear sequence

FIFO (first in first out, meaning the most recent piece of data is the last to be removed)

uses enqueue() and dequeue() which adds/ removes people from the queue.

Question 5

What is a tree?

Answer 5

-node based data structure
- consists of nodes and edges. have a root node which is the point is starts
- useful for managing folder structures and other hierarchal structures like family tree

Question 6

what is a balanced and unbalanced binary tree?

Answer 6

balanced is when a tree has the same amount of nodes each side of the tree. Unbalanced is the opposite.

Question 7

Traversing Acronym

Answer 7

(n) Pre
L
(n) In
R
(n) Post

Question 8

Linked List

Answer 8

-Dynamic data strcuture
- allocate memory dynamically are not stored in contigous memory locations
- each element in a linked list has a node which each node store data and a pointer
- slower access speed than arrays as they have to be traversed linearly

Question 9

Adding/deleting nodes in a linked list

Answer 9

adding to an** unordered list**, just add at either beginning or end. Adding to an ordered list, insert into correct postion

When deleting a node, cross it out and reconnect pointers without it

Question 10

Doubly and Singly

Answer 10

A singly linked list has one pointer to the next node whereas doubly has two pointers (one to previous and one to next) which is useful when working with ordered list when the previous node needs to be accessed

Question 11

Hash Tables

Answer 11

A data sturcture that uses a hashing algorithm to map key values to array indices to create key-value paris. This allows for efficient storage and fast retrieval of key value paris.

Question 12

Load factor

Answer 12

The dictionary (asscotive array0 used to store key-value pairs needs to be sized accoridngly while balancning efficieincy, this is determined by the load factor (0.75 is optimal)

Lower Load Factor
- Faster Operations
- Fewer Collisions
- Wasted Space

Higher Load Factor
-Slower Operations
- More Collisions
- Conserves Space

Question 13

Collisions Fixing

Answer 13

Linear Probing - Store data in the next avaibale space when a collision occurs

Chaining - Data is stored with a pointer. if a collision occurs the data is stored elsewhere and the orignal pointer is pointed towards it. This wil eventually create a chain of pointess and eliminate the need for linea probing.