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 Volvo

Change an Array Element

String[] cars = {"Volvo", "BMW", "Ford", "Mazda"};
cars[0] = "Opel";
System.out.println(cars[0]);
// Now outputs Opel instead of Volvo

Array 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 4

loop 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

1. Arrays (Video)
2. Arrays (CS50)
3. Dynamic Arrays (resize array)
4. CS50 lecture

   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");
    } 
  }

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.

Lists are sometimes used directly by kernel algorithms

Array V.S Linkedlist

1. Size of the array is fixed v.s Linked list allows dynamic memory allocation
   
2. Array elements need contiguous memory locations to store their values v.s Linked list elements don’t need contiguous memory locations
   
3. 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)

  Resources

• Website

• CS 61B Lecture

• Lists vs. Arrays

• Why you should avoid Linked Lists

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.

operating system often uses a stack when invoking function calls.

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

• Stacks (CS 50)
  
• Stacks(Coursera)

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

• Queue (video)
  

• Queue (CS50)
  

• Website
  

• Code Resources
  

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)

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.

Time

When we search for an item in a binary search tree, the worst-case performance is O(n)

Resources
Introduction To Trees ( Arabic )

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

1. Graph