1.4. Data types data structures and algorithms

primitive data types

set of basic data types from which all other data types are constructed

arrays

ordered finite set of element of a single type

arrays are static - meaning ?

static means that the size is determined when the array is acollated

what is a record ?

a row in a file

difference between a list and an array

values are stored non-contiguously

elements can be different data types

non-contiguous

doesn’t have to be stored next to one another in memory

isEmpty()

checks if the list is empty

append(val)

adds a new value to the list

remove(val)

removes the value the first occurrence in the list

search(val)

searches for a value in a list

len()

returns the length of list

index(val)

return the position of input val in a list

insert(position,val)

insert value at given position in a list

pop()

removes last value of the list

pop(index)

removes value at given postion in a list

list

data structure consisting of orders items where the values are stored non-contiguously

what is an abstract data type?

object created by the programmer, defined by a set of values and set of operations.

what is a static data type ?

data type defined when the data is given and is fixed as the same type for the lifetime of the program

tuples

static, immutable, ordered, stores more than one data type, contiguous

linked list

a dynamic data structure that holds an ordered sequence. each node has a value and a pointer to the next node.

graph

set of vertices connected by edges

directed graph

edges can be traversed in only one direction

undirected graphs

the edges can be traversed in both direction

weighted graphs

a cost is attached to each edge

what is a queue?

FIFO data structure enQueue at rear, deQueue at front.

applications of queue

keyboard buffer, first come first serve printer, stimulation programs

what is a doubly linked list

extra node that points at the previous node

how are queues implemented ?

using arrays or objects

issue with implementing queue with array ?

the array has a fixed size, if the array is filled nothing can be added to the queue.

What are stacks in Data structures?

a LIFO data structure

peek()

returns the top value of the stack

what is stack overflow

error when attempt to push an item to a full stack

push(item)

adds a new item to the top of the stack

stack underflow

pop item from empty stack

applications of stacks

holding parameters, local variables, holding return addresses

what is a priority queue ?

allows items to be added at a specific point in a queue

applications of a linked list

os process block storage, image viewers, web browsers, hash table collision, file allocation.

what is a hash table?

a table which uses hash functions on data values to determine the address in the hash table to store that value

what is a collision hash table

two values produce the same hash value

how can collision values be reduced

increase the size of the hash table, use better hashing function