Data Structures Flashcards
Disadvantages of a LinkedList
- We have to access elements sequentially
- Extra memory space for a pointer is required
What is a data structure?
- is a data organization, management, and storage format
- is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.
What is a DoubleLinkedList?
It’s a datastructure in which each node has a pointer to the previous and next node.
- Non contigous allocation
- The element previous to the head is null
What is a HashMap?
It’s a data structure which consists of a pair of sets of a key and a value.
It takes advantage of the hashCode function to map a key into an specific index, where the value will be stored.
What is a linked list?
Data stucture of a linear collection of nodes
- They are stored in non-contiguous locations
- Instead each node has a pointer to the next node
What is an array?
Is a datastructure that consists of a collection of elements, each identified by an index.
- The most common form of arrays are one-dimensional.
- The elements are stored at contigous locations.
Advantages of a LinkedList
- Dynamic Size
2. Ease of insertion/deletion
What is a Stack?
It’s a collection of elements that implements the mechanism LIFO.
Methods
- pop() deletes the element from the top of the stack and returns it
- push() inserts an element on the top of the stack
- peek() returns the element at the top of the stack without deleting it
What is a queue?
It’s a linear data structure which follows the FIFO order.
Methods
- enqueue() adds an item to the beginning of the end of the queue
- dequeue() removes the item at the beginning of the queue and returns it
- front() get the front item of the queue
- rear() get the last item from queue
How does a HashMap inserts a set of key-value?
- It uses a method put which takes a key and a value as parameters
- It uses the hashCode function to map the key into an index
- If the index is empty it stores the value in a single element linked list.
Else, it stores the value at the end of the linked list
What is Big O’ Notation
Big O notation is special notation that tells you how fast an algorithm is
What is the complexity of accessing an element in an array?
Array lookup is always O(1) (constant)
What is the complexity of adding a new element to an array?
Trick question. Adding a new element to an existing array it’s not possible
A use case for a double linked list
Undo Redo operations.
Surfing the internet and going to the previous website and then coming back.
What is a binary tree
A tree data structure in which each node has at most two children
