5.2 Abstract Data Structures Flashcards
What is a variable?
A memory location to hold a specific size and type of data.
What is an array?
A declared size of memory space that can store related data.
What is important about arrays?
They are static - can’t be expanded
What are the advantages of arrays?
Easier to predict performance
Easier to predict how the program will run
more organised
static - so no unnecessary data stored.
What isa multi dimensional array?
2 or more data types saved in a certain spot. They have to be the same data type.
Code a multi dimension al array?
What is a tuple?
A special type of array with
An ordered set of values
Of mixed types
That can’t be changed
What is important to remember with a tuple?
Can’t be changed or expanded.
Code a tuple?
What are records?
A special type of array like tuples but that can be implemented like an object.
What are dynamic data structures?
Lists or Records that can grow or shrink as requested.
Record, Array, Tuple
Which are static?
Array and Tuple are static
Record, Array, Tuple
Which can grow and shrink?
None.
Record, Array, Tuple
Which can have multiple data types?
Array and Tuple
Record, Array, Tuple
Which must have a fixed number of items?
All of them.
Record, Array, Tuple
Which can have more than one dimension?
Array.
Record, Array, Tuple
Which can hold an item of the other two structures?
Array
What are stacks?
A stack is an abstract data type that holds an ordered, linear sequence of items. However it is a push pop structure.
How is data added to the stack?
It is pushed into the top end.
push(item)
How is data removed from a stack?
It is popped from the top end.
pop(item)
What is overflow?
Attempting to push onto a stack that is full.
What is underflow?
Attempting to pop from a stack that is empty.
How do you check if a stack is full?
isFull()
How do you check if a stack is empty?
isEmpty()
What is peek()?
Returns top item from the stack without removing it?
How do you check the number of items in the stack?
size()
What is a queue?
A queue is a type of array which is limited to only allow data to be inserted from one end and retrieved from the other. But can be infinitely long.
What is another name for a queue?
FIFO - first in, first out
How is data added to a queue?
Data is pushed from the back. This is called enQueue
enQueue(item)
How is data removed from a queue?
Popped out from the front. This is called deQueue
deQueue()
How do you check if the queue is full?
isFull()
How do you check if a queue is empty?
isEmpty()
Is a queue static or dynamic?
Static - has a set length
What is a list?
A collection of data that can grow in size.
How does a List grow in size?
List will create a static array in another part of the memory twice the size of the item and copy that data over. Until it is needed.
Why are Lists good?
They do not have to be declared.
Why are Lists bad?
Lists use random access memory
Programs with lots of data will cause programming times to be long.
What are Linked lists?
A linked list is a linear data structure, in which the elements are linked using pointers.
What is the first item in a Linked List called?
Head
What is the last item in a Linked List called?
Null
How do you get from the head to the null?
You need to traverse to each place.
What is an item in a Linked List called?
A node
How do you delete an item from a linked list?
The item would be cleared from the space and become blank.
So the pointed would move over the space to the next item. Leaving the space null.
What are Linked Lists useful for?
Effective insertion and deletion - it takes a lot less time and complexity than other structures.
And it is simple and can be used to implement a stack, queue, record or tuple.
What are the advantages of linked lists?
Can implement a variety of ADTs
Dynamic memory allocation - no memory wasted.
Good to represent trees and graphs.
Expanded in a constant time.
Insertion and deletion is efficient.
