A data structure is a data organization, management, and storage format that enables efficient access and modification
Array
• Arrays give us the ability to: - Store a (potentially large) collection of homogeneous data - Have direct access to any one element in the collection by its position
Syntax
type[] array_name = new type[length];
Access the Elements of an Array
String[] cars = {"Volvo", "BMW", "Ford", "Mazda"};
System.out.println(cars[0]);
// Outputs VolvoChange an Array Element
String[] cars = {"Volvo", "BMW", "Ford", "Mazda"};
cars[0] = "Opel";
System.out.println(cars[0]);
// Now outputs Opel instead of VolvoArray Length
To find out how many elements an array has, use the length property:
String[] cars = {"Volvo", "BMW", "Ford", "Mazda"};
System.out.println(cars.length);
// Outputs 4loop to print all elements in Array
String[] cars = {"Volvo", "BMW", "Ford", "Mazda"};
for (int i = 0; i < cars.length; i++) {
System.out.println(cars[i]);}Resize the size of array when you reach capacity, resize to double the size
int count = cars.length;
String [] newitems = new String [count*2];
//copy the elements to new array
for (int i = 0; i < count; i++){
newitems [i] = cars[i];
}
Time
- O(1) to add/remove at end (amortized for allocations for more space), index, or update
- O(n) to insert/remove elsewhere
Space
- contiguous in memory, so proximity helps performance
- space needed = (array capacity, which is >= n) * size of item, but even if 2n, still O(n)
resources
2D Array
A multidimensional array is an array of arrays. Each element of a multidimensional array is an array itself. For example
int[][] a = new int[3][4];
Loop to print 2D array
int[][] board = new int [3] [3];
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
System.out.print(board[i][j] + "\t");
}
}LinkedList
LinkedList is a data structure wherein each element contains both a data value and a pointer to next element in the list
Linkedlists accommodate items of varying sizes and allow easy insertion
and deletion of items.
One potential disadvantage of using a list is that
performance for retrieving a specified item in a list of size n is linear — O(n),
as it requires potentially traversing all n elements in the worst case.
Array V.S Linkedlist
- Size of the array is fixed v.s Linked list allows dynamic memory allocation
- Array elements need contiguous memory locations to store their values v.s Linked list elements don’t need contiguous memory locations
- Inserting an element in an array is performance wise expensive v.s Insert and delete operations in the Linked list are not performance wise expensive because adding and deleting an element from the linked list does’t require element shifting, only the pointer of the previous and the next node requires change.
Funcations
LinkedList al=new LinkedList();
al.add("Ravi");
al.addFirst("First Item");
al.getFirst();
al.getLast();
al.addLast("Last Item");
al.removeFirst();
al.removeLast();
al.remove(2);
al.get(2);
al.size();
// clear the list
al.clear();
// clone al ( returns the exact same copy of the Linked List object )
list2 = (LinkedList) al.clone();Time
- O(1) to add/remove at end (amortized for allocations for more space), index, or update
- O(n) to insert/remove elsewhere
Space
-
The amount of data stored increases linearly with the number of nodes in the list. Therefore, the space complexity of the linked list is linear: O(n)
Stack
A Stack is a sequentially ordered data structure that uses the last in, first out (LIFO) principle for adding and removing items, meaning that the last item placed onto a stack is the first item removed. The operations for inserting and removing items from a stack are known as push and pop, respectively.
Parameters,local variables, and the return address are pushed onto the stack when a function is called; returning from the function call pops those items off the stack.
Creating a Stack
Stack stacks = new Stack<>();example
Stack <String> animals = new Stack<>();
animals.push("Dog");
animals.push("Horse");
System.out.println("Stack: " + animals);When we push an element into the stack the top is increased by 1.
other Funcations
empty() The method checks the stack is empty or not.
push(E item) The method pushes (insert) an element onto the top of the stack.
pop() The method removes an element from the top of the stack and returns the same element as the value of that function.
peek() The method looks at the top element of the stack without removing it.
search(Object o) The method searches the specified object and returns the position of the object
size() to get the size of the Stack
Resources
Queue
Queue is a data structure which follows the principle of FIFO (First-In-First-Out)
items are removed from a queue in the order
in which they were inserted. There are many everyday examples of queues,
including shoppers waiting in a checkout line at a store and cars waiting in line
at a traffic signal. Queues are also quite common in operating systems—jobs
that are sent to a printer are typically printed in the order in which they were
submitted, for example
tasks that are waiting to be run on an available CPU are often organized in queues.
FRONT track the first element of the queue
REAR track the last elements of the queue
initially, set value of FRONT and REAR to -1
Funcations
- Enqueue(): Add an element to the end of the queue (increase the REAR index by 1)
- Dequeue(): Remove an element from the front of the queue (increase the FRONT index by 1)
- IsEmpty(): Check if the queue is empty
- IsFull(): Check if the queue is full
- Peek(): Get the value of the front of the queue without removing it
Complexity Analysis
The complexity of enqueue and dequeue operations in a queue using an array is *O(1).
a bad implementation using linked list where you enqueue at head and dequeue at tail would be O(n) because you'd need the next to last element, causing a full traversal each dequeue
Applications of Queue
- Serving requests on a single shared resource, like a printer, CPU task scheduling etc.
- In real life scenario, Call Center phone systems uses Queues to hold people calling them in an order, until a service representative is free.
Resources
Hash table
Hashtable is a combination of an array and linkedlist inside of it .
Called Dictionary in Python
A hash function takes data as its input, performs a numeric operation on this
data, and returns a numeric value. This numeric value can then be used as an
index into a table (typically an array) to quickly retrieve the data.
Because of this performance, hash functions are used extensively in
operating systems.
One potential difficulty with hash functions is that two inputs can result in the same output value—that is, they can link to the same table location. We can accommodate this hash collision by having a linked list at that table location that contains all of the items with the same hash value. Of course, the more collisions there are, the less efficient the hash function is.
- The Hash Function should be such that the keys generated are uniformly distributed.
- The size of the Hash Table is dependent on the Hash Function. So, the choice of Hash Function should be done perfectly.
- In the case of a collision in the Hash Table, apply proper collision handling technique.
Hashtable<Integer, String> hashtable = new Hashtable<>();
//2. Add mappings to hashtable
hashtable.put(1, "A");
hashtable.put(2, "B" );
hashtable.put(3, "C");
System.out.println(hashtable);
//output
{3 = C, 2 = B, 1 = A}Methods
- Object put(Object key, Object value) : It maps the specified key to the specified value in this hashtable. Neither the key nor the value can be null.
- Object remove(Object key) : It removes the key (and its corresponding value) from hashtable.
- boolean containsValue(Object value) : It returns true if specified value exist within the hash table for any pair, else return false.
- void clear() : It is used to remove all pairs in the hashtable.
- Object get(Object key) : It returns the value to which the specified key is mapped. Returns null if no such key is found.
- void rehash() : It is used to increase the size of the hash table and rehashes all of its keys.
- int size() : It returns the number of entries in the hash table.
Time
The Hash Table will perform the insertion, deletion, and searching operation in O(1) time.
searching for a data item through a list of size n can require up to O(n)
comparisons in the worst case
Resources
Hash tables (CS50)
CS 50 lecture
Hashing with Chaining (MIT lecture)
Tree
A tree is a data structure that can be used to represent data hierarchically. Data
values in a tree structure are linked through parent–child relationships.
In a binary tree, a parent may have at most two children, which we term the left child
and the right child
additionally requires an ordering between the parent’s two children in which lef t child <= right child.
Linux uses a balanced binary search tree as part its CPU-scheduling algorithm.
- Root: Root is the node that is present at the top of the tree. There can be only one root of a particular tree.
- Parent: All the nodes having at least one child is called the parent node.
- Child: The node below the parent node is called the child node of the parent node.
- Leaf: The node having zero children is called the leaf node.
When we search for an item in a binary search tree, the worst-case performance is O(n)
Resources
Introduction To Trees ( Arabic )
Graph
What is a graph?
A graph models a set of connections. For example, suppose you and your friends are playing poker, and you want to model who owes whom money. Here’s how you could say, “Alex owes Rama money.”
That’s all there is to it! Graphs are made up of nodes and edges. A node can be directly connected to many other nodes.
Vertex: Vertices are the point that joints edges. It represents the data. It is also known as a node. It is denoted by a circle and it must be labeled. To construct a graph there must be at least a node. For example, house, bus stop, etc.
Edge: An edge is a line that connects two vertices. It represents the relation between the vertices. Edges are denoted by a line. For example, a path to the bus stop from your house.
resources
