LinkList
Linked List is a part of the Collection framework present in java.util package. This class is an implementation of the LinkedList data structure which is a linear data structure where the elements are not stored in contiguous locations and every element is a separate object with a data part and address part. The elements are linked using pointers and addresses. Each element is known as a node.
package com.example.demo1.LinkedList;
public class LinkedList {
Node head;
class Node {
Node next;
int data;
public Node(int d) {
this.data = d;
this.next = null;
}
}
public void push(int data) {
Node node = new Node(data);
node.next = head;
head = node;
}
public void printList() {
Node node = head;
int position = 0;
while (node != null) {
System.out.println(" Position " + position++ + " Data " + node.data);
node = node.next;
}
}
void deleteNode(int position) {
Node node = head;
if (position == 0) {
head = node.next;
return;
}
for (int i = 0; i < position - 1; i++) {
if (node == null) {
throw new RuntimeException("Out of Bounds");
}
node = node.next;
}
Node temp = node.next.next;
node.next = temp;
}
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
linkedList.push(4);
linkedList.push(12);
linkedList.push(10);
linkedList.printList();
linkedList.deleteNode(1);
linkedList.printList();
}
}
ArrayList
Resizable-array implementation of the List interface. Implements all optional list operations, and permits all elements, including null. In addition to implementing the List interface, this class provides methods to manipulate the size of the array that is used internally to store the list. (This class is roughly equivalent to Vector, except that it is unsynchronized.)
package com.example.demo1.LinkedList;
import java.util.Arrays;
public class ArrayList<E> {
private static final Integer DEAFULT = 10;
private Object[] list = new Object[DEAFULT];
private int size = 0;
public void add(E e) {
if (size == list.length) {
addSize(list);
}
list[size++] = e;
}
private void addSize(Object[] list2) {
list = Arrays.copyOf(list2, size* 2);
}
public E get(int position) {
if (position < 0 || position >= list.length) {
throw new RuntimeException(" Out Of Bounds");
}
return (E)list[position];
}
public static void main(String[] args) {
ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("Jones");
arrayList.add("Alapat");
System.out.println(" Print the ArrayList " + arrayList.get(11));
}
}
HashMap
Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.
This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets. Iteration over collection views requires time proportional to the “capacity” of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings). Thus, it’s very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.
An instance of HashMap has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created. The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.
As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put). The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.
package com.jonesjalapat.blog.tradesman.controller;
public class CustomHashMap<K, V> {
private static final int DEFAULT_CAPACITY = 10;
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
private int capacity;
private float loadFactor;
private int size;
private Node<K, V> []table;
public CustomHashMap() {
this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public CustomHashMap(int capacity, float loadFactor) {
this.capacity = capacity;
this.loadFactor = loadFactor;
table = new Node[capacity];
}
public V get(K key) {
int index = hashcode(key);
Node<K, V> node = table[index];
while (node != null){
if (key.equals(node.key)) {
return node.value;
}
node = node.next;
}
return null;
}
public void put(K key, V value) {
int index = hashcode(key);
Node<K, V> node = table[index];
while (node != null){
if (key.equals(node.key)) {
node.value = value;
return;
}
node = node.next;
}
Node<K,V> newNode = new Node<>(key, value);
newNode.next = table[index];
table[index] = newNode;
size++;
if (size > (int) (capacity * loadFactor)) {
resize();
}
}
private void resize() {
int newCapacity = this.capacity * 2;
Node<K, V> []newTable = new Node[newCapacity];
for (int i = 0; i< capacity; i++) {
Node<K, V> node = table[i];
while (node != null) {
Node<K, V> next = node.next;
int index = hashcode(node.key);
node.next = newTable[index];
newTable[index] = node;
node = next;
}
table = newTable;
capacity = newCapacity;
}
}
public void remove(K key) {
int index = hashcode(key);
Node<K, V> node = table[index];
Node<K, V> prev = null;
while (node != null){
if (key.equals(node.key)) {
if ( prev == null) {
table[index] = node.next;
} else {
prev.next = node.next;
}
size--;
return;
}
prev = node;
node = node.next;
}
}
public int hashcode(K key) {
return key.hashCode() % capacity;
}
private static class Node<K,V> {
public K key;
public V value;
public Node<K,V> next;
public Node(K key, V value) {
this.key = key;
this.value = value;
}
}
public static void main(String[] args) {
CustomHashMap customHashMap = new CustomHashMap();
for (int i=0; i< 12;i++) {
customHashMap.put(i, "Jones");
}
System.out.println(customHashMap.get(11));
customHashMap.put(11, "Anu");
System.out.println(customHashMap.get(11));
}
}
Stack
The Stack class represents a last-in-first-out (LIFO) stack of objects. It extends class Vector with five operations that allow a vector to be treated as a stack. The usual push and pop operations are provided, as well as a method to peek at the top item on the stack, a method to test for whether the stack is empty, and a method to search the stack for an item and discover how far it is from the top.
When a stack is first created, it contains no items.
package com.jonesjalapat.java.collection;
import java.util.EmptyStackException;
public class Stack<T> {
private class CustomStack<T> {
T data;
CustomStack<T> next;
public CustomStack(T data) {
this.data = data;
}
}
CustomStack<T> top;
public void push(T data) {
CustomStack<T> stack = new CustomStack<>(data);
stack.next = top;
top = stack;
}
public T peek() {
if (top == null) {
throw new EmptyStackException();
}
return top.data;
}
public T pop() {
if (top == null) {
new RuntimeException(" run time exception");
}
T temp = top.data;
top = top.next;
return temp;
}
public boolean isEmpty() {
return top == null;
}
}
Queue
A collection designed for holding elements prior to processing. Besides basic Collection operations, queues provide additional insertion, extraction, and inspection operations.
package com.jonesjalapat.java.collection;
import java.util.NoSuchElementException;
public class Queue<T> {
private static class CustomQueue<T> {
private T data;
private CustomQueue<T> next;
public CustomQueue(T data) {
this.data = data;
}
}
private CustomQueue<T> first;
private CustomQueue<T> last;
public void add(T data) {
CustomQueue<T> newLast = new CustomQueue<>(data);
if (last != null) {
last.next = newLast;
}
last = newLast;
if (first == null) {
first = last;
}
}
public T remove() {
if (first != null) {
throw new NoSuchElementException();
}
T data = first.data;
first = first.next;
if (first == null) {
last = null;
}
return data;
}
public T peek() {
if (first == null) {
throw new NoSuchElementException();
}
return first.data;
}
public boolean isEmpty() {
return first == null;
}
}
