Java - data structures Flashcards
primitive data types
data types from which more advanced data structures are made: include ints, doubles, longs, floats, shorts, booleans, and chars
Int
whole number (32 bits) - most commonly used
Float
decimal (32 bits)
Short
whole number (16 bits)
Long
whole number (64 bits)
Double
decimal (32 bits) - most commonly used
reference types
more complex data types
String
sequence of chars
array
a list that has both an index (number in the list) and data for what’s at that index
multidimensional array
an array of arrays – the data at the first index has an array, so the index therefore has two points (0,0). 0 for the first slot in the array, and then the next 0 represents the slot in the array for that data
jagged array
a multidimensional array where the number of columns is not fixed. some index positions might have an array of 5, the next an array of 20, the next just 1
resizable array
an array whose length you can change as needed
how do you search an array
for loop
Big O Notation
Describe the performance or complexity of an algorithm
O(1) time
consistent duration of algorithm execution in same time (or space) regardless of the size of the input. Also called constant time.
O(n) time
if the size of the input increases, the computation time directly increases in proportion to the input’s increase. Sample tasks would be for loops that have to look through everything.
common operations you might do with lists
access, update, insert, search, and delete
linked list
Like an array, but not necessarily contiguous. Uses pointers to refer to other list items. Doesn’t have to use contiguous locations in memory but can link to any memory slot. Just need a memory address, or rather the next pointer. You just indicate what is next and use that to sort your list.
Array class in Java
ArrayList class
Linked list class in Java
LinkedList class
Stack
An ordered series of objects. You can only add or remove items from the top. You push objects onto a stack and pop objects off of it. Think of a stack of pancakes. You remove from the top. You add a pancake by placing it on top of the stack. Stacks follow a last in, first out (LIFO) policy. The first item pushed onto the stack will be the last item popped off.
Pop
Removing an item is called popping the item off. To get an item further down the stack, you have to pop off the upper items.
When to use stacks
great for reversing actions. also for keeping track of state.
Queue
A list with front and back. Designed to have a front and back. Queues follow a first in, first out policy (FIFO)
Enque
the process of adding an item to the queue.
Dequeue
the process of removing an item from the queue
What are queues good for
Queues are good for storing the order of things that need to happen. often used to share system resources. For example, everyone sending a job to the printer. They keep track of waiting which tasks need to be performed.
Shift
moves all elements down by one
LIFO
last in, first out (refers to stacks)
FIFO
first in, first out (refers to queues)
difference between stacks and queues
In one word, the difference between Stack and Queue comes in how they consume elements, In Stack, we remove the most recently added element, while in Queue we remove least recently added element.
Poll
removing the top element (first item) in a queue
Priority queue
Items with higher priority can be moved to the top of the list.
DEQUEK
items can be removed from either end of the queue. But you can’t do anything with items in the middle
Peek
see what’s at the top of the list
are stacks and queues good data structures for pulling information from the middle of the list?
no, if you’re pulling lots of items from the middle of the queue, then they are not the right data structure.
associative array
a collection of key-value pairs. example, Sacramento: California. Each key-value pair always stays together. The keys must always be unique in associative arrays.
Dictionaries
Python term for hashes. A dictionary is a key-value pair. Internally, this is stored as an array with a hash function on the keys.
Hashing
taking raw data and taking it together to create some simplified form. Like making hashbrowns. Different ingredients combined to form some final. The raw data goes through a hashing function (cooking) to arrive at the final value. Basically, you start with some text, and the hash algorithm creates some scrambled form of that original.
differences between hashing and encryption
Hash functions are not reversible. One way. You can’t feed the function into some reverse algorithm to get the original values. Just like you can’t get the original ingredients to the hash browns. encryption, on the other hand, is reversible
Collision
when two keys have same hash value.
Purpose of hashing
let you store a value at a certain location in a secure way.
Hash table
A hash table is a way to implement an associative array.
A “bucket” is each place for a key-value pair to be stored in the hash table. Key will go through hash function, and then an integer will pop out.
hashCode
hashes the value you pass it
Set
A collection of unique items. Order doesn’t matter, but none of the elements are duplicated. Grouped with a common property. No key, no index to look up value. You only care about the set as a whole. You’re testing to see if the test has a given number, character, or string.
Tree data structure
Unlike with linked lists that just have links to next items, the tree data structure can link to multiple different nodes.
In a tree structure, there’s a root node. You can have parent and child nodes down the tree. A node can be a parent and child at the same time. Child nodes with the same parent are siblings.
Binary tree
A special type of tree. Each node has two child nodes (left and right nodes). The left child node and right child node could be null, both have values.
BST = Binary Search Tree. In the BST, you keep track of order to keep track of left, right, etc. this data structure naturally stays sorted.
Binary search trees often store key-value pairs.
If you get a match, you remove any need to keep going down the tree.
A recursive data structure where each node can have 2 children at most. a common type of binary tree is a binary search tree, in which every node has a value that is greater than or equal to the node values in the left sub-tree, and less than or equal to the node values in the right sub-tree
The basic idea is that by sorting the values, when you want to retrieve a particular value, it’s a lot easier to do so because you can eliminate whole branches of the tree.
TreeMap
Java class for binary trees
Heap
two meanings. area of memory where you allocate objects. in reference to data structures, a heap is a data structure implemented as a binary tree.
A heap is a collection of objects. As you add items to the heap, they are always added top to bottom, left to right. We care about min and max values.
The heap swap nodes to keep itself organized. Nodes get swapped around so that the parent nodes are smaller than child nodes. Every child must be less than its parent, so you always bubble up the larger values to the top. The max value will always be on top.
Order doesn’t matter. Instead, it’s more like a size sorting. Used for priority queues and certain sorting algorithms.
when to use a binary tree
One reason to use trees might be because you want to store information that naturally forms a hierarchy. For example, the file system on a computer:
