SE_21_Lesson: Data Structure

1. Interface Iterator; Iterator pattern

package org.example;

import java.util.Iterator;

public class MyIterator<T> implements Iterator<T> {

    private T[] objects;
    private int index = 0;

    public MyIterator(T[] objects) {
        this.objects = objects;
    }

    @Override
    public boolean hasNext() {
        return index < objects.length;
    }

    @Override
    public T next() {
        return objects[index++];
    }
}
package org.example;

public class Main {
    public static void main(String[] args) {
        String[] strings = {"Hesen", "Tamerlan", "Nesimi", "Kamran", "Etibar", "Javid", "Vahid",
                "Reshad", "Araz", "Ayaz", "Adil", "Imdad", "Xeyyam"};
        MyIterator<String> myIterator = new MyIterator<>(strings);
        while (myIterator.hasNext()) {
            System.out.println(myIterator.next());
        }
    }
}

Eslinde forEach bu prinsip ile iwlyir. Yeni arxa planda bu tip implementasiya baw verir.


-> Adi Array-in problemleri ve ArrayList klasi bu problemi nece aradan qaldirir

package org.example;

public class Main {
    public static void main(String[] args) {
        String[] students = {"One", "Two", "Three", "Four"};
        for (String s : students) {
            System.out.println(s);
        }

        // yenisi elave olundu
        String[] second = new String[students.length + 1];
        for (int i = 0; i < students.length; i++) {
            second[i] = students[i];
        }
        second[second.length - 1] = "Five";
        students = second;
        for (String s : students) {
            System.out.println(s);
        }

        // biri cixdi
        students[2] = null;
        String[] third = new String[students.length - 1];
        for (int i = 0, j = 0; i < students.length; i++) {
            if (students[i] != null) {
                third[j] = students[i];
                j++;
            }
        }
        students = third;
        for (String s : students) {
            System.out.println(s);
        }
    }
}


2. ArrayList

Step1: Oz Iterable interface-mizi yaradiriq

package org.example.parvin;

public interface MyIterable <T> extends Iterable<T>{

    boolean add(T element);

    boolean delete(int index);

    T get(int index);

    int size();

    boolean update(int index, T element);
}
package org.example.parvin;

import java.util.Iterator;

public class MyArrayList<T> implements MyIterable<T> {

    private T[] array = (T[]) new Object[10];
    private int size = 0;

    public MyArrayList() {
    }

    public MyArrayList(int arraySize) {
        this.array = (T[]) new Object[arraySize];
    }

    @Override
    public boolean add(T element) {
        try {
            check();
            array[size++] = element;
            return true;
        } catch (Exception e) {
            System.out.println("Something went wrong...");
        }
        return false;
    }

    @Override
    public boolean delete(int index) {
        try {
            if (index >= size || index < 0) {
                throw new RuntimeException("Index out of bound exception");
            }
            for (int i = index; i < array.length - 1; i++) {
                array[i] = array[i + 1];
            }
            array[size - 1] = null;
            size--;
            return true;
        } catch (Exception e) {
            e.printStackTrace();
        }
        return false;
    }

    @Override
    public T get(int index) {
        try {
            if (index >= size || index < 0) {
                throw new RuntimeException("Index out of bound exception");
            }
            return array[index];
        } catch (Exception e) {
            e.printStackTrace();
        }
        return null;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean update(int index, T element) {
        try {
            if (index >= size || index < 0) {
                throw new RuntimeException("Index out of bound exception");
            }
            array[index] = element;
            return true;
        } catch (Exception e) {
            e.printStackTrace();
        }
        return false;
    }

    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            private int i = 0;
            @Override
            public boolean hasNext() {
                return i < size;
            }

            @Override
            public T next() {
                return array[i++];
            }
        };
    }

    private void check() {
        if (size == array.length) {
            T[] newArray = (T[]) new Object[array.length + array.length / 2];
            for (int i = 0; i < array.length; i++) {
                newArray[i] = array[i];
            }
            array = newArray;
        }
    }
}


3. Singly LinkedList


package org.example.myArrayList;

public interface MyIterable<T> extends Iterable<T> {
    boolean add(T element);

    T get(int index);

    boolean remove(int index);

    int size();

    boolean set(int index, T element);

    void clear();
}
package org.example.myArrayList;

import java.util.Iterator;

public class SinglyLinkedList<T> implements MyIterable<T> {

    private Node<T> head;
    private Node<T> tail;
    private int size = 0;

    @Override
    public boolean add(T element) {
        return addLast(element);
    } 

    public boolean addFirst(T element) {
        try {
            Node<T> node = new Node<>(element);
            node.next = head;
            head = node;
            if (tail == null)
                tail = head;
            size++;
            return true;
        } catch (Exception e) {
            System.out.println("Something went wrong");
        }
        return false;
    } 

    public boolean addLast(T element) {
        try {
            if (tail == null) addFirst(element);
            else {
                Node<T> node = new Node<>(element);
                tail.next = node;
                tail = node;
                size++;
            }
            return true;
        } catch (Exception e) {
            System.out.println("Something went wrong");
        }
        return false;
    }

    @Override
    public T get(int index) {
        Node<T> node = head;
        for (int i = 1; i <= index; i++) {
            node = node.next;
        }
        return node.value;
    } 

    @Override
    public boolean remove(int index) {
        try {
            if(size == 1) removeFirst();
            if (index == 0) removeFirst();
            if(index == size - 1) removeLast();
            else {
                Node<T> node = getNodeByIndex(index - 1);
                node.next = node.next.next;
                size--;
                return true;
            }
        } catch (Exception e) {
            System.out.println("Something went wrong");
        }
        return false;
    } 

    public boolean removeFirst() {
        try {
            head = head.next;
            if(head == null) {
                tail = null;
            }
            size--;
            return true;
        } catch (Exception e) {
            System.out.println("Something went wrong");
        }
        return false;
    }

    public boolean removeLast() {
        try {
            Node<T> lastSecond = getNodeByIndex(size - 2);
            tail = lastSecond;
            tail.next = null;
            size--;
            return true;
        } catch (Exception e) {
            System.out.println("Something went wrong");
        }
        return false;
    }

    @Override
    public int size() {
        return size;
    } 

    @Override
    public boolean set(int index, T element) {
        try {
            Node<T> node = getNodeByIndex(index);
            node.value = element;
            return true;
        } catch (Exception e) {
            System.out.println("Something went wrong");
        }
        return false;
    } 

    @Override
    public void clear() {
        head = null;
        tail = null;
    } 

    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            int i = 0;

            @Override
            public boolean hasNext() {
                return i < size;
            }

            @Override
            public T next() {
                Node<T> node = getNodeByIndex(i++);
                return node.value;
            }
        };
    } 

    public void display() {
        Iterator<T> iterator = iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
    }

    private Node<T> getNodeByIndex(int index) {
        Node<T> node = head;
        for (int i = 1; i <= index; i++) {
            node = node.next;
        }
        return node;
    } 

    private class Node<T> {
        private T value;
        private Node<T> next;

        public Node(T value) {
            this.value = value;
        }

        public Node(T value, Node<T> next) {
            this.value = value;
            this.next = next;
        }
    }
}


4. DoublyLinkedList

package org.example.myArrayList;

public class DoublyLinkedList<T> {

    private Node<T> head;
    private Node<T> tail;
    private int size = 0;

    public void insertFirst(T value) {
        Node<T> node = new Node<>(value);
        node.next = head;
        node.prev = null;
        if (head != null) {
            head.prev = node;
        }
        head = node;
        if (tail == null) {
            tail = head;
        }
        size++;
    }

    public void insertLast(T value) {
        if (tail == null) {
            insertFirst(value);
            return;
        }
        Node<T> node = new Node<>(value);
        node.prev = tail;
        tail.next = node;
        tail = node;
        size++;
    }

    public void insert(int index, T value) {
        if (index == 0) {
            insertFirst(value);
            return;
        }
        Node<T> found = findByIndex(index - 1);
        Node<T> node = new Node<>(value, found.next, found);
        found.next = node;
        node.next.prev = node;
    }

    public void display() {
        Node<T> node = head;
        while (node != null) {
            System.out.print(node.value + " -> ");
            node = node.next;
        }
        System.out.println("END");
    }

    private class Node<T> {
        T value;
        Node<T> next;
        Node<T> prev;

        public Node(T value) {
            this.value = value;
        }

        public Node(T value, Node<T> next, Node<T> prev) {
            this.value = value;
            this.next = next;
            this.prev = prev;
        }
    }

    public Node<T> findByIndex(int index) {
        Node<T> node = head;
        for (int i = 1; i <= index; i++) {
            node = node.next;
        }
        return node;
    }
}


5. CircularLinkedList

package org.example.myArrayList;

public class CircularLinkedList<T> {

    private Node<T> head;
    private Node<T> tail;
    private int size = 0;

    public void insert(T value) {
        Node<T> node = new Node<>(value);
        if (head == null) {
            head = node;
            tail = node;
            return;
        }
        tail.next = node;
        node.next = head;
        tail = node;
    }

    public void display() {
        Node<T> node = head;
        if (head != null) {
            do {
                System.out.print(node.value + " -> ");
                node = node.next;
            } while (node != head);
            System.out.println("HEAD");
        }
    }

    private class Node<T> {
        private T value;
        private Node<T> next;

        public Node(T value) {
            this.value = value;
        }

        public Node(T value, Node<T> next) {
            this.value = value;
            this.next = next;
        }
    }
}



6. HashMap



Her bir bir xana burada "bucket"-dir. Ve her bir bucket bir node-dir. Yeni bucket-ler linked listdir




Put metodu:






*Hash Collision




Overall:



Get method in HashMap:



* Null-un hash code = 0

*** Treeify threshold


****equals hashCode contract

-> Ne equals() ne de hashCode metodlari override olmadiqda ne bash verir

Meselen biz Person class yaratdiq. Bu zaman JVM ozu mueyyen alqoritm iwledib bir hashCode generate edir.  Biz 2 ferqli Person class-inin obyektini yaratdiq ve ola biler ki JVM bu iki muxtelif obyektler ucun eyni hashCode yarada. Mes:

String s1 = "AaAaAa";
String s2 = "AaAaBB";
System.out.println(s1.hashCode());
System.out.println(s2.hashCode());

Bu zaman map-a put etdike problemler baw verir. Cunki equals metodu da oz novbesinde hash-larin beraberliyini yoxlayir. Onda bele cixir ki, biz map-a ferqli obyektler yerlewdirmek isteyirik lakin bu zaman map ikincisini birinci ile evez edecek.


-> hashCode() metodu override olunur lakin equals() metodu override olunmur

package org.example.myHashMap;

import java.util.Objects;

public class Person {
    public Integer id;
    public String name;

    public Person(Integer id, String name) {
        this.id = id;
        this.name = name;
    }

//    @Override
//    public boolean equals(Object o) {
//        if (this == o) return true;
//        if (o == null || getClass() != o.getClass()) return false;
//        Person person = (Person) o;
//        return Objects.equals(id, person.id) && Objects.equals(name, person.name);
//    }

    @Override
    public int hashCode() {
//        return Objects.hash(id, name);
        return 1;
    }
}
package org.example.myHashMap;

import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        HashMap<Person, Integer> map = new HashMap<>();
        Person one = new Person(1, "Parvin");
        Person two = new Person(1, "Parvin");

        map.put(one, 100);
        map.put(two, 200);
    }
}

Bu zaman ise bawqa problem baw verir. Biz iki eyni obyekt yaratdiq ve tebiiki hashlari eynidir. Bu zaman map-a put etdikde equals() override etmediyimiz ucun arxa planda Object-in equals metodunu cagirilir, o da bildiymiz kimi hashlari muqayise edir. Ve neticede map-da identik obyektler put olunur. Bu da yol verilmezdi.


-> hashCode() metodu override olunmur lakin equal() metodu override olunur

package org.example.myHashMap;

import java.util.Objects;

public class Person {
    public Integer id;
    public String name;

    public Person(Integer id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return Objects.equals(id, person.id) && Objects.equals(name, person.name);
    }

//    @Override
//    public int hashCode() {
////        return Objects.hash(id, name);
//        return 1;
//    }
}
package org.example.myHashMap;

import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        HashMap<Person, Integer> map = new HashMap<>();
        Person one = new Person(1, "Parvin");
        Person two = new Person(1, "Parvin");

        map.put(one, 100);
        map.put(two, 200);

        System.out.println(map.get(one));
        System.out.println(map.get(two));
    }
}

Bu zaman yene map-a eyni parametrli ferqli obyektler yazilacaq. Bu da yol verilmezdi.

One gore de biz equals hashCode contract-ina sadiq qalmaliyiq ve mutleq wekilde override etmeliyik. 

Override olundugu teqdirde eyni parametrli obyektler map-a yazilmir.


7. HashSet:

HashSet-in add metodu daxilinde HashMap-in put metodunu iwledir. Bu zaman key kimi ele obyektin ozunu iwledir, value kimi ise   private static final PRESENT = new Object(); yeni bow object gonderir. 




------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

MyArrayList

package org.example.myCustomArrayList;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.function.Consumer;

public class MyArrayList<T> implements MyIterable<T> {

    private T[] array = (T[]) new Object[10];
    private int size = 0;

    public MyArrayList() {
    }

    public MyArrayList(int size) {
        this.array = (T[]) new Object[size];
    }

    @Override
    public boolean add(T t) {
        check();
        array[size++] = t;
        return true;
    }

    @Override
    public void add(int index, T element) {
        checkIndex(index);
        array[index] = element;
    }

    @Override
    public boolean addAll(Collection<? extends T> collection) {
        for (T element : collection)
            array[size++] = element;
        return true;
    }

    @Override
    public boolean addAll(int index, Collection<? extends T> collection) {
        checkIndex(index);
        int newSize = 0;
        T[] newArray = (T[]) new Object[array.length + collection.size()];
        for (int i = 0; i <= index; i++) {
            newArray[newSize++] = array[i];
        }
        Object[] objects = collection.toArray();
        for (int i = 0; i < objects.length; i++) {
            newArray[newSize++] = (T) objects[i];
        }
        for (int i = index + 1; i < array.length; i++) {
            newArray[newSize++] = array[i];
        }
        size = newSize;
        array = newArray;
        return true;
    }

    @Override
    public T get(int index) {
        checkIndex(index);
        return array[index];
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public T set(int index, T element) {
        checkIndex(index);
        array[index] = element;
        return element;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            int i = 0;

            @Override
            public boolean hasNext() {
                return i < size;
            }

            @Override
            public T next() {
                return array[i++];
            }
        };
    }

    @Override
    public void forEach(Consumer<? super T> action) {
        for (int i = 0; i < size; i++)
            action.accept(array[i]);
    }

    @Override
    public void clear() {
        size = 0;
        array = (T[]) new Object[10];
    }

    @Override
    public boolean contains(Object o) {
        for (T t : array) {
            if (t != null && t.equals(o))
                return true;
        }
        return false;
    }

    @Override
    public boolean containsAll(Collection<?> collection) {
        boolean flag = false;
        Object[] objects = collection.toArray();
        for (int i = 0; i < collection.size(); i++) {
            flag = false;
            for (int j = 0; j < size; j++) {
                if (objects[i].equals(array[j]))
                    flag = true;
            }
        }
        return flag;
    }

    @Override
    public int indexOf(Object o) {
        int result = -1;
        for (int i = 0; i < size; i++) {
            if (array[i].equals(o)) {
                result = i;
                break;
            }
        }
        return result;
    }

    @Override
    public int lastIndexOf(Object o) {
        int result = -1;
        for (int i = 0; i < size; i++) {
            if (array[i].equals(o)) {
                result = i;
            }
        }
        return result;
    }

    @Override
    public boolean remove(Object o) {
        int index = indexOf(o);
        if (index < 0) return false;
        remove(index);
        return true;
    }

    @Override
    public T remove(int index) {
        checkIndex(index);
        for (int i = index; i < size - 1; i++) {
            array[i] = array[i + 1];
        }
        array[--size] = null;
        return null;
    }

    @Override
    public boolean removeAll(Collection<?> collection) {
        boolean flag = containsAll(collection);
        Object[] objects = collection.toArray();
        if (flag) {
            for (Object o : objects)
                remove(o);
        }
        return flag;
    }

    @Override
    public List<T> sublist(int fromIndex, int toIndex) {
        checkIndex(fromIndex);
        checkIndex(toIndex);
        List<T> list = new ArrayList<>();
        for (int i = fromIndex; i < toIndex; i++) {
            list.add(array[i]);
        }
        return list;
    }

    @Override
    public Object[] toArray() {
        Object[] objects = new Object[size];
        for (int i = 0; i < size; i++) {
            objects[i] = array[i];
        }
        return objects;
    }

    @Override
    public String toString() {
        StringBuilder result = new StringBuilder("[");
        for (int i = 0; i < size - 1; i++) {
            result.append(array[i]);
            result.append(", ");
        }
        result.append(array[size - 1]);
        result.append("]");
        return result.toString();
    }

    private void checkIndex(int index) {
        if (index < 0 || index >= size)
            throw new RuntimeException("Index out of bound");
    }

    private void check() {
        if (size == array.length) {
            T[] newArray = (T[]) new Object[array.length + array.length / 2];
            int i = 0;
            for (T t : array)
                newArray[i++] = t;
            array = newArray;
        }
    }
}




                                                            STACK


package se34;

public class MyStack<T> {

    private T[] data = (T[]) new Object[10];
    int size;
    int pointer = -1;

    public MyStack() {
    }

    public MyStack(int size) {
        data = (T[]) new Object[size];
    }

    public boolean push(T item) {
        if (isFull()) {
            T[] newArr = (T[]) new Object[data.length + data.length / 2];
            for (int i = 0; i < data.length; i++) {
                newArr[i] = data[i];
            }
            data = newArr;
        }
        data[++pointer] = item;
        return true;
    }

    public T pop() {
        if (isEmpty()) throw new RuntimeException("Stack is empty");
        return data[pointer--];
    }

    public T peek() {
        if (isEmpty()) throw new RuntimeException("Stack is empty");
        return data[pointer];
    }

    private boolean isFull() {
        return pointer >= data.length - 1;
    }

    private boolean isEmpty() {
        return pointer == -1;
    }

}









 










Комментарии

Отправить комментарий

Популярные сообщения из этого блога

Lesson1: JDK, JVM, JRE

Изображение
1. Compiler - takes the entire programming code written in high language and translates the whole of it into machine code at once. After this process the an executable file will be ready to run. The translation takes some times to be done, but after that execution is so fast. 2. Interpreter - takes each single instructions of the code translates it and then executes it on its own. The translation step is before the program runs is fast, but execution is slow. JDK = JRE + development tools JRE = JVM + library class JDK -> Java Development Kit. A kit which provides the environment to develop and execute (run) Java program. JRE -> Java Runtime Environment. Provides environment to only run. JVM -> Java Virtual Machine f * Compiled: Fortran, C, C++, Pascal, Haskell, Rust, Go * Interpreted: JavaScript, PHP, Python, Ruby Java both compiled and interpreted language. Terminalda : javac Main.java yazdiqda, source fayli(.java) bytecode(.class) faylina cevirir. Terminalda: java Main (bu z
Далее...

SE_21_Lesson_11: Inheritance, Polymorphism

->  instanceof anlayishi, misallarla izahi   package org.example.lesson_13 ; public class Ulubaba { public String ad ; public String soyad ; public Integer yash ; public void odunDogramaq () { System . out .println( "Ulubaba 50 kq odunu 1 saata dograyir" ) ; } } package org.example.lesson_13 ; public class Baba extends Ulubaba { public String hobbi ; public void otBicmek () { System . out .println( "Baba 1 hektar otu 1 gune bicir" ) ; } } package org.example.lesson_13 ; public class Main { public static void main ( String [] args ) { Baba baba = new Baba() ; System . out .println( baba instanceof Ulubaba ) ; System . out .println( baba instanceof Object ) ; } } -> Upcasting package org.example.lesson_13 ; public class Main { public static void main ( String [] args ) { Ulubaba u = new Baba() ; } } -> Downcasting Problemsiz situasiya: package org.example.lesson_13
Далее...

SE_21_Lesson_9: Initialization Blocks, Wrapper types, String class

Изображение
-> static block: package org.example.test3 ; public class Blocks { static { System . out .println( "In static block" ) ; } public static void method () { System . out .println( "In static method" ) ; } } package org.example.test3 ; public class Main { public static void main ( String [] args ) { Blocks . method () ; } } -> Class.forName() metodunu ishe salmaq: package org.example.test3 ; public class Blocks { static { System . out .println( "In static block" ) ; } } package org.example.test3 ; public class Main { public static void main ( String [] args ) throws Exception { Class . forName ( "org.example.test3.Blocks" ) ; } } -> non-static (instance) block: package org.example.test3 ; public class Blocks { static { System . out .println( "in static block" ) ; } { System . out .println( "in non static (instance) block
Далее...