1.1 data structures Flashcards
pre order
dots to the left
in order
dots on the bottom
post order
dots on the right
linked list characteristics
- dynamic data structure it can grow and stinks in size after declaration
- each element is called a node - first element is head node
- each node consists of the data and the reference to the next node
- consists of starter pointer which points at the first item in the list and so on
- items can be added into a linked list without having to shift the other items to fill the gap left (adv over 1D array)
how to create binary trees
from first element - bigger (right) smaller (left)
remove from a binary tree with 2 children
go the right pointer and find the lowest value child from that element then replace the value being deleted with that child
what is a data structure
a set of related data items
why are the data structures are useful
- efficient way of organising data relating to a real problem
- may be efficient to deal with various elements as one item
an example of data that could be stored in a 2D array
sales of each product number by month
what are the key features of an array
- a data structure which is a set of data elements of the same type
- can be directly accessed via indexes, subscripts, row/column names
- has a fixed number of elements (static)
give an example of data that could be stored in 3D arrays
what is a record data and structure and when would they be used
- a record is a set of data items all related to a single individual/ entity
- a record can contain data of different types
- a record would be used if there is data of more than one type
drawbacks of using 3D arrays
- more complex to program/process
what data is suitable for a 1D array
when the data set comprises of single values of the same data type
what is a stack
- a container of objects that are inserted and removed according to LIFO
- It has a limited access data structure - elements can be added and removed from the stack only at the top
- push adds an item to the top of the stack
- pop removes the item from the top
- a stack can be used as a recursive data structure
- a stack is either empty or is consists of a top and the rest which is a stack
- underflow occurs when an attempt is made to pop an empty stack or when an attempt is made to push a full stack
Examples of when a stack could be used
- undo and back button
- a subprogram to return addresses (winding back nesting of subprograms)
- recursion values
- reversing a queue / list (LIFO)
what is a queue
operates on the FIFO principle and data items are added at the end of the queue and removed from the front
what happens when there is an attempt is made to add an item to a full queue
returns an appropriate message or condition
(produces an error message)
examples of where a queue could be used in computing and why
- a printer queue
- keyboard buffer
- a download buffer
- a processor scheduling queue
- because the natural/desirable processing order is FIFO so the job waiting the longest should be printed next
what is a linked list (simple)
a set of data elements, where each element contains the data itself and a pointer to the next element
advantages and drawbacks of a linked list compared to an array
advantages:
- new items can be inserted into a linked list without rearranging all the other elements
- if programmed dynamically uses memory more efficiently
disadvantages:
- a linked list is more complex to program/ manipulate than an array
- extra programming is required to access the data in the opposite direction
- can only be accessed in a linear manner
what is an unbalanced binary tree
not the same amount on each branch
example of in order traversal
-searching for a file in the file system
-listing files in alphabetical order
example of post order traversal
delete all the files in the file system (each folder could only be deleted once all the files beneath have been deleted)
example of pre order traversal
create copy files in the file system (each file above has to be copied before the files below)
what is the first node called in a binary tree
root
advantages and disadvantages of using a binary tree
advantages:
- faster to add a value
- faster to search for a value
disadvantages:
-more complex to program/process
-may be slow processing/ traversal if unbalanced
what is a hash table
- a structure that can map keys to values
how are hash tables used
a hash function is used to compute an index ( a hash code) into an array of buckets or slots from which the desired value can be found
examples of where hash tables are used
- to deal with collisions
- many kinds of computer software, particularly for associative arrays, database indexing, caches and sets
