SLR 14 - DATA STRUCTURES Flashcards
What is an array?
a variable that can contain more than 1 data item (a variation of a list)
What is the difference between lists and arrays?
lists are not contiguous whilst arrays are
What does contiguous mean?
all the data is stored together 1 element after the other
What is a record data structure?
- a collection of related fields (a variable
- each field in a record can have a different data type
What is a tupule?
a list that cant be changed once created (immutable)
What are the key properties of a list?
- mutable
- items can be changed or replaced
- can store more than 1 data type
What are the key properties of an array?
- mutable
- items can be changed or replaced
- can only store 1 data type
- length cant be changed (static)
What are the key properties of a tuple?
- immutable
- items cant be changed or replaced
- can store more than 1 data type
- length cant be changed (static)
What is a linked list?
- a data structure constructed from nodes and pointers
- provides a foundation upon which other structures can be built such as stacks, queues, graphs and trees
What identifies the first node in a linked list?
a start pointer
What does each node contain in a linked list?
- data
- a pointer to the next node
How are doubly linked lists made?
adding an extra pointer which causes the nodes to point to the previous and next items
How are circular linked lists made?
making the last node point to the 1st node
How are doubly circular linked lists made?
each node in a circular linked list has an additional pointer pointing to the previous item
How can a linked list be implemented?
- using an array
- using objects
What are the applications of linked lists?
- used by OS managing a processor to store process blocks in a ready state
- used by image viewers to switch between previous and next images
- used by music players to store tracks in a playlist
- used by web browsers to navigate backwards and forwards
- used for hash table collision resolution as an overflow
- used for maintaining a file allocation table of linked clusters on secondary storage
What operations can be performed on a linked list?
- add (adds a node to the linked list)
- delete (removes a node from the linked list)
- next (moves to the next item in the list)
- previous (moves to the previous item in a doubly linked list)
- traverse (a linear search through the linked list)
What is a graph?
a data structure consisting of nodes/vertices and pointers/edges
How does a graph differ from a linked list and binary tree?
each vertex can have more than 2 edges and point to any vertex in the data structure
What is a directed graph?
a graph in which the edges point in 1 direction
What is an undirected graph?
a graph in which the edges don’t point in a specified direction
What does it mean if a graph is weighted?
each edge has a value representing a relationship between the vertices
How can graphs be stored?
- typically stored as objects/using a dictionary (known as adjacency lists)
- can also be stored as an array (known as an adjacency matrix) (a 1 represents an edge existing between 2 vertices)
What are the applications of a graph?
- mapping road networks for navigation systems
- storing social network data
- resource allocation in operating systems
- representing molecular structures and geometry
What is abstraction?
using only the necessary detail and discarding unnecessary detail
What is a stack?
- a data structure
- items are pushed onto the top of a stack when they are added to it and popped off the top when they are deleted from it
- it is also possible to peek at the top of a stack without deleting it
- LIFO structure
What is a LIFO structure?
- last in, first out structure
- last item pushed onto the stack is the first item to be popped off the stack
What points to the node at the top of a stack?
stack pointer
What is a stack overflow?
an attempt to push an item onto a full stack
What is a stack underflow?
an attempt to pop an item off of an empty stack
How are stacks implemented?
- often using an array
- can be created using object orientated techniques
What are stacks used for?
- used by processors to track the flow of programs
- performing depth-first searches on graph data structures
- keeping track of user inputs for undo operations
- backtracking algorithms
- evaluating mathematical expressions without brackets (using a shunting yard algorithm and reverse polish notation)
What operations can be performed on a stack?
- push (adding an item to the top of a stack)
- pop (removing an item from the top of a stack)
- peek (returning the value from the top of the stack without removing it)
What is a queue?
- a linear data structure
- items are enqueued at the back of the queue and dequeued from the front
- its also possible to peek at the front of the queue without deleting it
- FIFO structure
What is a priority queue?
new items joining at the front of the queue
What is a FIFO structure?
- first in, first out structure
- first item enqueued is the first item to be dequeued
What is a tail pointer?
the back pointer in a queue which always points to the last item
What is a head pointer?
the front pointer in a queue which always points to the first item
What is a queue overflow?
an attempt to enqueue an item in a full queue
What is a queue underflow?
an attempt to dequeue an item from an empty queue
How can queues be implemented?
- using an array
- using object orientated techniques
What is the problem when implementing a queue using an array?
the array will quickly run out of space as both the back and front pointers are moving in the same direction as items are added and removed from the queue
How is the problem that occurs when using an array to implement a queue solved?
cycle the back pointer to the front of the array when it reaches the end (creating a circular queue)
Why are circular queues useful?
- ideal if you want to restrict the no. of items and have a known memory footprint
- particularly useful in game design where no. of sprites on screen affects framerate
What are the applications of a queue?
- process scheduling
- transferring data between processors and printer spooling
- performing breadth-first searches on graph data structures
What operations can be performed on a queue?
- enqueue (adding an item to the back of the queue)
- dequeue (removing an item from the front of the queue)
- peek (returning the value from the front of the queue without removing it)
What is a tree?
a data structure consisting of nodes and pointers
What is the root node of a tree?
- the node at the top of a tree
- connects to 0, 1 or more child nodes
What are nodes at the bottom of the tree called?
leaf nodes
How are nodes connected in a tree?
pointers/edges
What is a subtree?
a set of nodes and edges from any single node down through all of its descendants
What are the applications of a tree?
- storing and managing file and folder structures
- implementations of the A* pathfinding algorithm
- storing and manipulating any form of hierarchical data that requires a parent node to have 0, 1 or more child nodes (eg: family tree/corporate structure)
What is a binary tree?
a tree where each node can only have 0/1/2 pointers with each pointer connecting to a different node
How can binary trees be implemented?
can be stored as arrays/objects
What are the applications of binary trees?
- database applications where efficient searching and sorting is required without moving items which is slow
- wireless networking and router tables
- OS scheduling processes
- Huffman coding (used for compression algorithms (eg: JPEG and MP3))
- cryptography
What is a hash table?
- a data structure that implements an associative array (a dictionary). In an associative array, data is stored as a collection of key-value pairs.
- the position of the data within the array is determined by applying a hashing algorithm to the key - a process called hashing. The hashing algorithm is called a hash function
Why do collisions occur in hash tables?
2 items cant occupy the same position in the hash table
How is the chance of a collision minimised in a hash table?
the hash table is significantly large to minimise chances of the algorithm returning the same value for more than 1 item (collision)
What are properties of a good hashing function?
- calculated quickly
- result in as few collisions as possible
- use as little memory as possible
How are collisions from hashing functions resolved?
- repeatedly check next available space in hash table until an empty position is found and store the item there (known as open addressing). to find the item later, the hashing function delivers the start position from which a linear search can then be applied until the item is found (known as linear probing)
- using a 2 dimensional hash table. it is then possible for more than 1 item to be placed at the same position (known as chaining)
- using a second table (overflow table)/linked list for collisions which can then be searched sequentially
What is a disadv of linear probing?
- prevents other items from being stored at their current location in the hash table
- also results in clustering (several positions being filled around common collision values)
What is rehashing?
the process of finding an alternative position for items in a hash table
What are applications of a hash table?
- used in situations where items in a large data set need to be found quickly (eg: file systems linking a file name to the path of the file, identifying key words in a programming language during compilation)
What operations can be performed on a hash table?
- add
- delete
- retrieve (retrieves an item from a hash table using its hash value)
