Tag: data structure

Binary Search | Search Algorithm

The theory

A binary search algorithm is a search algorithm that uses the concept of divide and conquer in order to find a target value’s position. Basically, this search algorithm compares the target value with the middle element of the collection.

If it is equal, return the position. If it is not equal, then we will need to check if the value is either greater or less than the target value. This is to know what side of the collection we need to split.

Binary Search Requirements

There’s a condition applied to the binary search array, which is that the array must be sorted. This is because it uses the value (in our case an integer), to compare and check if the selected position has the target value or check where to go.

Binary Search Array Algorithm

Implementation

First things first, we will create our binary search class with the search methods.

public class BinarySearch { public int search(int[] array, int number) { return search(array, number, 0, array.length); } private int search(int[] array, int target, int start, int end) { int mid = (start + end) / 2; if (end < start) { return -1; } if (array[mid] == target) { return mid; } else if (array[mid] > target) { return search(array, target, 0, mid - 1); } else { return search(array, target, mid + 1, end); } } } Read more...

Linked List | Data Structures

A brief introduction

Linked List is a linear collection of objects, which is composed of nodes pointing to the next node. Each node contains a value and a reference to the next node in the sequence. Most of the operations applied in a linked list (add, remove, search, etc.) will require sequencial scanning most of the time.

single-linked-list
As you can notice, each node will always have a pointer to the next node and a value, this is called a single linked list. If a node has a link to the previous and to the next one, it is called a double linked list or a circular linked list.

Implementation

The first step will be creating a node class:

public class Node<T>{

    private Node next;
    private T value;

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

    public void setNext(Node next) {
        this.next = next;
    }

    public T getValue() {
        return value;
    }

    public void setValue(T value) {
        this.value = value;
    }
}

This is a POJO (Plain Old Java Object) of a Node class, which contains a value and another Node that will be the “Next” node. If you ask yourself about the “T” I have in there, I am declaring the Node class as Generic, enabling the option to choose what datatype to use. Now, we will be creating varios operations used, starting with the add.

public class MyLinkedList<T>{ private Node head; private static int counter; public void add(T value){ if (head == null) { head = new Node(value); } else { Node temp = new Node(value); Node current = head; while (current.getNext() != null) { current = current.getNext(); } current.setNext(temp); } counter++; } } Read more...