Interpret Arrays
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. [row][column]
3D Array - hard to visualise,every item is positioned using three indexes. [depth][row][column]
Properties of arrays
- 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
What is a stack?
- 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.
example: store webpages for a back button in a browser
When representing using arrays and pointers….Uses a single pointer to track top of the stack. When an element is pushed on, the pointer increments. When the top element is popped, the pointer decrements but the item isnt actually removed until the next item is pushed.
What is a queue
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.
When representing using arrays and pointers…. It will have a front pointer to indicate top element and a rear pointer to indicate last element. When an element is added, the rear pointer will incremented to that element. When an element is deqeueued, the front pointer is incremented.
What is a tree?
-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
what is a balanced and unbalanced binary tree?
balanced is when a tree has the same amount of nodes each side of the tree. Unbalanced is the opposite.
Traversing Acronym
(n) Pre
L
(n) In
R
(n) Post
Linked List
-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
An ordered linked list items are stored in an order so by looking at the first node, if the value is greater than the value you are looking for you can stop the search as its not there, saving time. In an unordered linked list you would have to traverse the whole thing to get your answer which is extremely time consuming
Adding/deleting nodes in a linked list
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
Doubly and Singly
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
Hash Tables
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.
Load factor
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). associative array uses indexes for instant access to data so performance is not affected by number of items stored
Lower Load Factor
- Faster Operations
- Fewer Collisions
- Wasted Space
Higher Load Factor
-Slower Operations
- More Collisions
- Conserves Space
Collisions Fixing
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.
