Beginner DS Flashcards
Data Structure
A particular way of organizing data in a computer so that it can be used effectively.
Access, Insertion, Deletion, Search
Big O
Mathematical notation represents the worst case run time or space requirements as input size increases
Constant time
Regardless of the input size the runtimes stays the same
Linear time
As the input size grows the runtime grows linearly
Quadratic time
As the input size grows the runtime grows quadratically
Logarithmic Time
As the input size grows the runtime grows logarithmically
Array
Think?
Think eggs – A linear data structure of fixed size that is used to store the same type of elements at a contiguous location. The location is called indexes, which represents the location of the object in memory.
Linked list
Think?
Think a chain with links – Consists of nodes where each node contains a data field and a reference(pointers; they are what chain the nodes together that is what constitutes the linked part of a linked list. The pointers are the address or location in memory of the connected nodes)to the next node in the list.
Stack
Think?
Think Pringles – Containers distinguished by last in first out (LIFO) retrieval order. Pop - take it out from the top; push - put it back at the top
Queue Think?
Think Food Truck serving customers – Waiting for something FIFO (First in first out). On queue meaning you add it to the back
Graph
Each node is called vertex and each vertex is connected to other vertices through edges
Strength
Weakness
Trees
A collection of vertices and edges, However, there can only be one edge between two vertices.
Arrays Strength and Weaknesses
Strengths:
Access happens in constant time(search, insertion, deletion)
Weakness:
A fixed size cannot change size unless you have a dynamic array or an arrayList
Searching for an element is really slow and happens in linear time
Linked List S&W
Strength
Insertion and deletion in constant time
Dynamic Size
Weakness
Search in linear time
Additional memory for pointer
