CS- data structures

data structures

what is an array?

a variable that contains more than one data item/ static/ only one data type

What is a record?

a collection of different fields which can be of different data types

What is a list?

a data structure that consists of a number of items where the items can occur more than once

What is a tuple?

an ordered set of values of any type

What is a linked list?

a linear data structure made up of nodes, where each node contains data and a pointer to the next node in the list

What is a dictionary?

an abstract data type made up of associated pairs

What is a hash table?

an associative array which is coupled with a  hash function

What is a stack?

a linear data structure that follows LIFO principle 

What is a queue?

a linear data structure/ enqueue + dequeue / items removed from top of queue

What is a graph?

a set of nodes that are connected by edges

ADV of adjacency matrix in graphs

1. convenient to work with

2. adding an edge is simple

DIS of adjacency matrix in graphs

1. a sparse graph (not many connections) will leave most cells empty and this is not storage efficient

2. uses O(n²) space

What is a tree?

• A connected undirected form of a graph with nodes and pointers 

• An abstract data type

how is a directed graph different to an undirected graph?

in directed graphs, edges can only go in one direction

in undirected graphs edges can go in both directions

ADV + DIS of declaring an array as a global variable?

ADV = can be accessed anywhere in the program

DIS = increases memory usage as it is used until full program execution is over

How to add an item to a linked list

create new node containing data

set the new nodes pointer to point to the next node

update the previous nodes pointer to point to the new node

How to REMOVE from a linked list

traverse the list to find the node to be removed

change the previous node’s pointer to skip the node

delete the removed node

How TRAVERSAL takes place in a linked list

start at head node

read the data stored in the current node

follow pointer to the next node

repeat until the pointer is null

How does a dictionary work

each key is passed through a hash function

the hash function generates a hash value

the value determines where the data is stored in memory

the value is retrieved using the same key

this gives fast access

ADV of dictionaries

very fast lookup

efficient for large data sets

DIS of dictionaries

uses more memory

collisions might occur which takes longer

data not stored in order

How does a hash table work

a key is passed into a hash function

the hash function produces an index

the value is stored at that index in the table

this allows fast access to data

ADV of hash table

very fast to access data

search time is O(1) on average

efficient for large data sets

DIS of hash tables

collisions can occur - could decrease performance

uses extra memory

data is unordered

Why hash tables are faster than arrays/lists

direct access using an index

no need to search sequentially

average look up time is constant O(1)

Describe how a stack works

items are added using push

items removed using pop

only the top item can be accessed

earlier items can’t be accessed directly