fundamentals of data structures

the arrangment of data

stores data in one direction useful way of representing a vector

stores data horizontally and vertically useful way of representing a matrix example: triplets = [[a,b,c], [d,e,f], [g,h,i]] triples[2,1] = h

formatted so only one a program can read them

contain characters structured as lines of text

closing free up resources, preventing corruption and ‘flushes’ the buffer

usually for a single entity heterogenous

an ‘out of line’ block that performs a specific task (can be ither user written or pre existing)

by calling their name in a statement causing them to be executed

through parameters (variables used for the input to the subroutine)

procedure (doesn’t return a value) functions (returns a value

improves the quality and clarity of code

code is more readable and easier to understand easier to test modules can be reused

• apply hash function to calculate the hash value for the key . • use the hash value to find the index in the hash table so that the new record could be stored. • check if there is a record at the index. if yes, use a collision resolution technique. • insert the new record at the index in the hash table and update the number of records in the hash table.

local variables and parameters

• initialize an empty stack • push values onto a stack from left hand side. • for each number in the expression; push it onto a stack. for each operator; pop the top two numbers off the stack. • after both have been processed, the stack should contain only one value, which is the result of the expression. • check if empty by comparing the stack pointer to the initial address of the stack • check if full by comparing the stack pointer to the max address of the stack

• check if the queue is empty by comparing the front and rear pointer. if equal, the queue is empty and no item can be removed. • if not empty, remove the front item from the front of the queue. • update the front pointer to the next item in the queue. if the front pointer exceeds the size of the array, reset it to 0. • reduce the count of items in the queue by 1

• Check if the number of elements in the queue is equal to the maximum capacity. If it is, the queue is full. • If it is not full, increment the count of elements in the queue. Insert the item at the next available position in the queue. • Check if the number of elements in the queue is equal to the maximum capacity. If it is, the queue is full. If it is not full, return false or display an appropriate message.

static data structures memory are allocated at compile time/dynamic data structure memory are allocated at run time. static data structure size is fixed and cannot change during runtime/ dynamic data structure size can be changed during runtime static data structure memory is managed by compiler/ dynamic data structure memory is managed by the programmer

• deque all the items from the queue and push them onto the stack • pop them off one by one and enqueue them back into the original queue • the order of the items in the queue will be reversed

when two key values compute the same hash.

A collection of key-value pairs in which the value is accessed via the associated key.

information retrieval

addition achieves translation and multiplication achieves scaling.