Ever wondered why React keeps bugging you about using the `key` attribute? Why we need to use this if everything is working perfectly? The answer is rather simple, Performance!

Every time you make a change in a React app your application re-renders entirely right? Actually no! And that's what we are going to understand now!

## The problem

Every time our application renders React create a new tree of react elements. The problem here is updating the UI to match the most recent tree created in render. This problem can be solved in a non efficient way, ending with a a complexity in the order of O(n^3) where n is the number of nodes (elements) in the tree.

React came with a really clever way of handling this, by implementing an algorithm based on two simple assumptions they managed to make this problem go from O(n^3) to O(n).

The two assumptions they made can handle most cases, and they are:

1. If one element changed it's type a new tree will be created.
2. If two elements have the same `key` id in both trees, they are the same element and will not be re-rendered from 0.

## Reconciliation algorithm

The algorithm have some different ways to work depending on the root elements. If the root element changed from one type to another (or one tag to another) the new tree will be created from scratch.

A good way to visualize is checking out this example I got from [react docs](https://reactjs.org/docs/reconciliation.html):

```jsx
<div>
  <Counter />
</div>

<span>
  <Counter />
</span>
```

Here the Counter will not be reused, the Counter will be remounted.

Another case React handles pretty well is when we have DOM elements of the same type. React can update only attributes and have the structure be reused, Check the examples above:

```html

<img src="images/image.svg" className="something" />


<img src="images/image.svg" className="another-something" /> 
```

The tag remains the same and react only updates the `className`.

Another case is with styles:

```html

<div style={{color: "green", padding: "10px"}}></div>


<div style={{color: "orange", padding: "10px"}}></div>
```

React only changes the `color` style, and not `padding.`

## Okay really interesting, but why key?

React differs if a node changed or not using the node type itself or the attributes passed to it. But there's a problematic case that is not resolved by only looking at the node or it's attributes. Lists.

Lists will have the same node types and attributes, so they won't be recognized by the algorithm. 

But we can have cases where the algorithm will work fine, like this:

```html

<ul>
	<li>1</li>	
	<li>2</li>
</ul>


<ul>
	<li>1</li>	
	<li>2</li>
	<li>3</li>
</ul>
```

Here we have two lists, React will match the first two elements (1, 2) and will insert the last one (3) at the end.

But if we have a similar but different implementation.

```html

<ul>
	<li>2</li>	
	<li>3</li>
</ul>


<ul>
	<li>1</li>	
	<li>2</li>
	<li>3</li>
</ul>
```



Here we are inserting something new at the start of the list. React doesn't know how to handle this and will recreate every element, instead of reusing 2 and 3 that remained the same between trees, leading to bad performance.

That's where `keys` are important. Using keys we can have every item in a list have a unique identifier (ID) so React can easily detect who needs to be changed or not, re-rendering only the ones with changes.
## Conclusion
That's my takeaway and what I have understood searching about this underlying implementations react has.
I started searching for curiosity + to have a better understanding of react's big picture. I may write more about how react works underneath the hood in the future, if you have any suggestion please comment down here :) Thanks for reading.

Ever wondered why React keeps bugging you about using the key attribute? Why we need to use this if everything is working perfectly? The answer is rather simple, Performance!

Why we use "key" in React?


# The compiling process

Hello guys, a while back I made some notes about the compiling process. When I finished I thought that I could make some small edits and transform it into a post. So here we are.

The compiling process (turn source code in machine code) is divided in 4 smaller steps:

- preprocessing

- compiling

- assembling

- linking

  ​	

To be sure you will understand everything I will first explain some terms I will be using when describing the compiling process:

**prototype:** Is a function declaration that comes in the start of our programs, so the compiler can understand that there will be a function with this name. We usually declare our functions at the top of our code and write what they to at the end of it.

Example of a prototype:

```c
/*here we only declare name, type and parameters of our function,
we don't say what the function does (aka we don't specify the
function body), that's why it's a prototype.*/
int area( int length, int breadth ); 
```

**Library:** Is a <i>compiled binary file</i> (or a collection of binary files) which can be linked (will explain what is **linked** below in the compiling steps).

**header file:** Is the name of what we include when we start our code (aka `#include<stdio.h>`), header files are files that contain **prototypes** for all the functions from the libraries we include in our code.

Okay Now let's go for the 4 compiling steps.  

### Preprocessing

**Preprocessing** is when the compiler look at the header files we included in our program and replace the "include" lines for the actual prototypes that are inside of these files.

for example:

```c
#include <stdio.h>

int main(void)
{
    printf("hello, world\n");
}
```

will be preprocessed into:

```c
//prototypes from printf function
...
int printf(string format, ...);
...

int main(void)
{
    printf("hello, world\n");
}
```

### Compiling

**Compiling** takes our source code in C, and converts to assembly code.

### Assembling

**Assembling** is the process of converting the assembly code that we have after the last step, **Compiling**, and actually convert it (or assemble it) to binary code (or machine code). Most modern compilers don't have this phase because they jump the assembly code and convert directly your source code to binary, they probably will only convert to assembly first if you ask to. But with old compilers the case will often be that they will convert your code do assembly first and then to binary. 

Extra: When a compiler makes the binary code for you and it still haven't being linked, he actually have produced for you an **Object file**. Here is an good explanation of what it is (link for this explanation in the end).

```
Object code is a portion of machine code not yet linked into a
complete program. It's the machine code for one particular library
or module that will make up the completed product. It may also
contain placeholders or offsets not found in the machine code of a
completed program. The linker will use these placeholders and
offsets to connect everything together.
```

### Linking

Now that we have our program file in binary we need to **link** it to the binary of the libraries we are using so in the end we have only one binary file with all of it inside, that process is called **linking**.

**Additional:** stdio is a part of the <i>standard </i>library, and the linker in the **linking** process already know where this library is, that's why we doesn't have to specify where the binary file of the library is when using stdio and some other standard functions (we still need to specify the header files). 
But when we are using a library that is not standard (for example a library you created) we need to specify it with the linker using a flag when compiling our program. This flag is `-l`, and we use it without the lib prefix to link with the library file. Ex: `-lExampleLibrary`. If your library file is not where `-l` looks by default you have to specify where is it using `-L`. 
Example:

```
if the library code is inside the current folder you are:
gcc test.c -L. -lExampleLibrary -o test 
```

Just to have the notes a little more specific I'm gonna explain some more deep details about the linking process.

**library file:** When the linker go get the binaries of the libraries we are using he doesn't actually get .o files (aka normal binary files), he get's what we call a library file, that can be a static ".a" or a dynamic ".so" one. 

A **static Library** combines all the object code (aka binary code that doesn't have been linked) into a single archive with a ".a" file extension, that's what our linker actually goes get to link with your source code. 

A **dynamic Library** have their object codes linked together forming a single piece of object code that is loaded into memory and only the address in memory of where the library function (being used in source code) is, is added to the executable file (after linked).

### Links

- [static VS dynamic libraries](https://medium.com/@dkwok94/the-linking-process-exposed-static-vs-dynamic-libraries-977e92139b5f)

- [-l and -L flags in gcc compiler](https://www.rapidtables.com/code/linux/gcc/gcc-l.html)

- [object code in C](https://stackoverflow.com/questions/7718299/whats-an-object-file-in-c)
- [object code X assembly code X Machine code](https://stackoverflow.com/questions/466790/assembly-code-vs-machine-code-vs-object-code)



My notes on the compiling process transformed in an article. Read about the four steps for compiling code.

The compiling process


Hello guys, this is gonna be a small post about git bash customization, so by the end of it you will know how to change some aspects of your git terminal, for example making it like mine:

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ht25lmlvuzj46ltnd6br.png)

so let's dive in!

## Finding and Editing git-prompt

Open your git bash terminal and type this commands:

```bash
cd /etc/profile.d/
explorer .
```

The first command is to change your current directory to the `/etc/profile.d/` that is where the file we need to edit is. The other command just open the explorer in the current directory, so you will se something like this:

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/r50gpsse84pkx3rsuxnq.png)

Here is our git-prompt.sh. Now we can open it and see what we have there.

```shell
if test -f /etc/profile.d/git-sdk.sh
then
	TITLEPREFIX=SDK-${MSYSTEM#MINGW}
else
	TITLEPREFIX=$MSYSTEM
fi

if test -f ~/.config/git/git-prompt.sh
then
	. ~/.config/git/git-prompt.sh
else
	PS1='\[\033]0;$TITLEPREFIX:$PWD\007\]' # set window title
	PS1="$PS1"'\n'                 # new line
	PS1="$PS1"'\[\033[32m\]'       # change to green
	PS1="$PS1"'\u@\h '             # user@host<space>
	PS1="$PS1"'\[\033[35m\]'       # change to purple
	PS1="$PS1"'$MSYSTEM '          # show MSYSTEM
	PS1="$PS1"'\[\033[33m\]'       # change to brownish yellow
	PS1="$PS1"'\w'                 # current working directory
	if test -z "$WINELOADERNOEXEC"
	then
		GIT_EXEC_PATH="$(git --exec-path 2>/dev/null)"
		COMPLETION_PATH="${GIT_EXEC_PATH%/libexec/git-core}"
		COMPLETION_PATH="${COMPLETION_PATH%/lib/git-core}"
		COMPLETION_PATH="$COMPLETION_PATH/share/git/completion"
		if test -f "$COMPLETION_PATH/git-prompt.sh"
		then
			. "$COMPLETION_PATH/git-completion.bash"
			. "$COMPLETION_PATH/git-prompt.sh"
			PS1="$PS1"'\[\033[36m\]'  # change color to cyan
			PS1="$PS1"'`__git_ps1`'   # bash function
		fi
	fi
	PS1="$PS1"'\[\033[0m\]'        # change color
	PS1="$PS1"'\n'                 # new line
	PS1="$PS1"'$ '                 # prompt: always $
fi

MSYS2_PS1="$PS1"               # for detection by MSYS2 SDK's bash.basrc
```

Here we have a lot of different things, but let's focus on the important part, this one:

```shell
	PS1='\[\033]0;$TITLEPREFIX:$PWD\007\]' # set window title
	PS1="$PS1"'\n'                 # new line
	PS1="$PS1"'\[\033[32m\]'       # change to green
	PS1="$PS1"'\u@\h '             # user@host<space>
	PS1="$PS1"'\[\033[35m\]'       # change to purple
	PS1="$PS1"'$MSYSTEM '          # show MSYSTEM
	PS1="$PS1"'\[\033[33m\]'       # change to brownish yellow
	PS1="$PS1"'\w'                 # current working directory
```

Here is where we are gonna customize it. The nice thing about git bash, is that there are already some pretty comments that help us understand what each thing does.

To customize it we are gonna need to understand two things: The special backslash characters and the ANSI color escape codes.

The first one is pretty simple, there are some of them and they each represent something that can be seeing in our terminal, here are some of them:

\u => username

\h => hostname until the first '.'

\w => current working directory

So for example the line `PS1="$PS1"'\u@\h'` Would be `username@hostname`.

The last thing is the color codes. Those are used before the line we want to color it, so:

```shell
PS1="$PS1"'\[\033[32m\]'       # change to green
PS1="$PS1"'\u@\h '             # user@host<space>
```

Here we are changing the `username@hostname` to green. There are a few color codes we can use in bash such as:

```
Black        30  
Red          31     
Green        32     
Brown/Orange 33     
Blue         34     
Purple       35     
Cyan         36
Light Gray   37 
```

There are some special codes that change the style of the text too:

```
Normal        0
Bold text     1
Faint text    2
Italic        3
Underlined    4
```

So we can make some pretty cool customization combining those together, here is an example:

```shell
PS1="$PS1"'\[\033[1;36m\]'       # change to bold 1() and cyan (36)
```

There are some other lines that you can customize. Basically every line that is changing PS1 represents a customization for some part, and all of them have good comments to guide you. I only focused in the first ones to be easier to understand, since you are focusing in only a couple lines, instead of the entire file. But if you prefer that I point out them, they are these lines here:

This one changes the part that indicates in which branch you are

```shell
PS1="$PS1"'\[\033[1;33m\]'  # change color to bold yellow
PS1="$PS1"'`__git_ps1`'   # bash function
```

And this ones defines the second line, where you write the commands (in case is only the "$")

```shell
PS1="$PS1"'\[\033[1;31m\]'     # change color to bold red
PS1="$PS1"'\n'                 # new line
PS1="$PS1"'$ '                 # prompt: always $
```

And that's it, with this knowledge you can make some more customizations in your git bash :). If you liked how mine feel free to get the code for you here:

```shell
if test -f /etc/profile.d/git-sdk.sh
then
	TITLEPREFIX=SDK-${MSYSTEM#MINGW}
else
	TITLEPREFIX=$MSYSTEM
fi

if test -f ~/.config/git/git-prompt.sh
then
	. ~/.config/git/git-prompt.sh
else
	PS1='\[\033]0;Terminal Dir:$PWD\007\]' # set window title
	PS1="$PS1"'\n'                 # new line
	PS1="$PS1"'\[\033[1;35m\]'       # change to bold purple
	PS1="$PS1"'GMkonan '             # user@host<space>
	PS1="$PS1"'\[\033[1;32m\]'       # change to bold green
	PS1="$PS1"'in '          # show MSYSTEM
	PS1="$PS1"'\[\033[1;36m\]'       # change to bold cyan
	PS1="$PS1"'\W'                 # directory without the path
	if test -z "$WINELOADERNOEXEC"
	then
		GIT_EXEC_PATH="$(git --exec-path 2>/dev/null)"
		COMPLETION_PATH="${GIT_EXEC_PATH%/libexec/git-core}"
		COMPLETION_PATH="${COMPLETION_PATH%/lib/git-core}"
		COMPLETION_PATH="$COMPLETION_PATH/share/git/completion"
		if test -f "$COMPLETION_PATH/git-prompt.sh"
		then
			. "$COMPLETION_PATH/git-completion.bash"
			. "$COMPLETION_PATH/git-prompt.sh"
			PS1="$PS1"'\[\033[1;33m\]'  # change color to bold yellow
			PS1="$PS1"'`__git_ps1`'   # bash function
		fi
	fi
	PS1="$PS1"'\[\033[1;31m\]'        # change color to bold red
	PS1="$PS1"'\n'                 # new line
	PS1="$PS1"'$ '                 # prompt: always $
fi

MSYS2_PS1="$PS1"               # for detection by MSYS2 SDK's bash.basrc

# Evaluate all user-specific Bash completion scripts (if any)
if test -z "$WINELOADERNOEXEC"
then
	for c in "$HOME"/bash_completion.d/*.bash
	do
		# Handle absence of any scripts (or the folder) gracefully
		test ! -f "$c" ||
		. "$c"
	done
fi

MSYS2_PS1="$PS1"               # for detection by MSYS2 SDK's bash.basrc
```

### Useful Links

- [customize git bash](https://blog.devgenius.io/how-to-customize-the-git-bash-shell-prompt-336f6aefcf3f)

A small Post about customizing git bash in Windows.

Customizing Git Bash in Windows


If you saw my article about **Selection Sort** it means that you already know at least one sorting algorithm. Now that you have a sorted list (or can create one) we are gonna dive in an algorithm that can **search** for an element in this sorted list, that's gonna be the **Binary Search** algorithm. We are gonna talk about two approach's to this algorithm, **iterative** and **recursive** and about it's **time complexity** too.

Like I did in all my [A&DS Implementation articles with java](https://dev.to/gmkonan/series/10529) until now we are gonna create two files.

### Iterative Search

Let's start creating the `BinarySearch.java` file.

This file is gonna hold both our Iterative and recursive search methods. But first we will make the iterative one, `iterativeSearch`

```java
	void iterativeSearch(int[] arr, int key) {
		
		
		//just a placeholder
		int index = 0;
		
		//defines the first one in the array
		int first = 0;
		//defines last one in the array
		int last = arr.length - 1;
		//defines the mid point of this array
		int mid = (first + last)/2;
    }
```

The first thing we do is create two parameters for our method, the array and the key (or value) we want to search inside this array, the we create the variables we are gonna be using, the `index` is gonna be the variable that stores the position of the value we are searching (the index of the key). The `first` variable is the index for the first value in the array (which is 0 because every array starts at 0). The `last` is the index of the last value in the array which we can get by subtracting one from the size of our array. And finally the ` mid` variable that stores the mid point of our array.

**IMPORTANT:** Why we get the mid point of the array by using the sum of the first with the last divided by two instead of just getting the `last/2` ? We need to make a sum with the first because when we start iterating, the `first` position of the array is gonna start to change, incrementing every time the loop is completed, making the mid point of the array change too.

 Now that we have our variables all set we are going to create the logic to search for the key

```java
	//while	the array is not the size of zero
	while(first <= last) {
		if (arr[mid] < key) {
			//shifts to the right since is greater and we already checked mid
			first = mid + 1;
		}
		//if item in mid make it equal index, break the loop and return at the end
		else if (arr[mid] == key) {
			//define index as mid
			index = mid;
			//print result
			System.out.println("The position of " + key + " is " + index);
			//break from the while loop
			break;
		}
		else {
			//shifts the end point to the left of mid
			//since the value is smaller and we already checked the mid
			last = mid - 1;
		}
		// make new count now with the new value to first or last
		mid = (first + last)/2;
	}
```

Okay, here we have a basic while loop that iterates until the variable `first`(that stores the start of the array) is bigger than the `last` which means that we are gonna iterate until the end of the list. Inside the loop we start creating our conditions to find our element. The way binary search is by dividing the list by half until it finds the number (that's why we make the `mid` variable) and here is where our conditions play. in the first `if statement` we make so if the number in the mid is **smaller** than the key (element we are searching) we will update the variable `first` to be the position after the mid position, which means we are gonna now search only the right half of the list, because everything to the left is smaller than our key so the key is not gonna be there.

Example images (taken from **tutorialPoint**)

In this example 31 is the key

![Binary search](https://www.tutorialspoint.com/data_structures_algorithms/images/binary_search_0.jpg)

After we defined our key we define the mid point of the list (in this case 27)

![Binary search](https://www.tutorialspoint.com/data_structures_algorithms/images/binary_search_1.jpg)

Then we enter in our loop and met our first condition, comparing if mid value is lower than key

![Binary search](https://www.tutorialspoint.com/data_structures_algorithms/images/binary_search_2.jpg)

The condition is met so we define first to be the element left to mid (in this case the 31 itself, or position 5) and we repeat the loop

The next condition is if the mid point value is equal to key, if it is the element was found and we can break the loop, here we use the `index` variable just to get more understandable in `print`.

Last but not least we make our final condition that is really similar to our first condition, in this case (although not explicitly told in the statement ) checks if the mid value is greater than the key, if it is we are gonna search only the left half of the list, by defining last as the value before the mid point.

The last thing we have in our `while loop` that is executed in every loop is the `mid = (first + last)/2;` , This is necessary because every time the loop is executed we make new comparisons with mid and update what we are searching in the list, and if we update the `first` variable and `last` variable but don't update our `mid` variable we will continue with the same mid point every time so the loop is going to make the same comparisons every time.

```java
if (first > last) {
			System.out.println("Not found");
		}
	}
```

The last thing in out `iterativeSearch` method is just a simple condition to make sure that, if the loop ends and the key wasn't found, the key is not in the list so we print "not found".

Okay now that we created our method lets create our `BinarySearchMain.java` to run it!

```java
public class BinarySearchMain {
	public static void main(String args[]) {
		BinarySearch binary = new BinarySearch();
		int[] arr = {10, 6, 4, 8, 2};
		int key = 8;
		
		binary.iterativeSearch(arr,key);
    }
}
```

Here we just make a main method and call our `iterativeSearch` passing the array and key we defined,now everything is working! Just try to run it and play around with different arrays.

In the above case the output should be this

```markdown
The position of 8 is 3
```

#### Time Complexity

The **time complexity** of **iterative search** is O(log n) because in the worst case scenario (if the number we are looking for is at the end of the list or is not in the list) we will have to divide the list in half repeatedly until we get to the end of the list. The best case scenario would be O(1) ( or Ω(1) ) and it would be if the element we are looking for is already in the mid point of the array.



### Recursive Search

Since we already covered the **iterative** approach I'm gonna be more to the point in the recursive one

```java
	int recursiveSearch(int[] arr, int key, int first, int last) {
		
		//just a placeholder
		int index = 0;
		
		int mid = (first + last)/2;
		
		//base case
		if (first > last) {
			return -1;
		}
		
		if(arr[mid] < key) {
			//return recursive but with first being shifted right from 				
            //mid getting only the right half of the array 
			return recursiveSearch(arr,key,mid + 1, last);
		}
		else if (arr[mid] == key) {
			//recursive is gonna end up here at the end
			index = mid;
			//return the value
			return index;
		}
		else {
			//return recursive but with last being shifted left from mid
            //getting only the left half of the array
			return recursiveSearch(arr,key,first, mid - 1);
		}
	}
```

The recursive search is pretty simple, we start by making our `recursiveSearch` method  . The difference is that this time instead of making it a void we make it as an **int**, so we can use the returns to make our recursion. The other difference in the method is that we add more two parameters: the `int first` and the `int last`.

Inside the method we have a base case that comes at the top of the code that if our first is higher than the last our element is not in this list. After that we have our set of conditions similar to what we have done in the **iterative search**. But inside this if statements we have our return statements. Here is where we are gonna use the power of recursion, we call the same `recursiveSearch` again in our first **if statement** and pass the same array,key and last. But we pass our first as `mid + 1` making it shift the start of the array to only the right half of the array.

In our next if we do basically the same thing to check if our key is in mid.

Our last check in **else** is where we use the same concept of our first **if** but we shift the last to the left half of the array.

And we are done with the **recursive search**, now we only need to add to main to run it.

```java
int first = 0;
int last = arr.length - 1;


int recursive = binary.recursiveSearch(arr, key, first, last);

if(recursive == -1) {
	System.out.println("Not found");
}
else {
	System.out.println("Found at position " + recursive);
}
```

if it returns -1 as we defined in our base case, we print "Not found". else, we found the position so we just print it!

and this is the output (used the same test I used to iterative search)

```markdown
Found at position 3
```

#### Time complexity

Maybe you realized something peculiar about it but... The **time complexity** of **recursive search** is the same O(log n) of our **iterative search**! In the worst case scenario we are still dividing the list by half multiple times. And the best case scenario is still O(1) or ( Ω(1) )

So, you may be asking yourself "What is the difference?" Honestly the only difference is in **Space complexity** but that is some content for another whole article. So in the end is a matter of choice, which one you find easier to understand? Go and use it!

If you want to see the full code you can see it here in this [github repo](https://github.com/GMkonan/A-DS_Java/tree/master/src/binarySearch) 

This is a post I have started writing in the end of 2020 but I got back to it only in 2021. Because of that I felt like it wasn't good enough and wasn't sure if I should post it or not. I decided to post because if it really bad, the worst thing it can happen is not be useful for someone, if it's not that bad it can still help someone. But just letting stay inside my computer for no reason just doesn't even have a chance to help someone.  

If you have any suggestions or critics about what I should write or/and how I should write (more detailed? less detailed?) or even how is my grammar (not a native English speaker) feel free to put it in the comments, It would help me a lot!



### Links

- [2 implementations in java](https://www.softwaretestinghelp.com/binary-search-in-java/)

- [other 2 implementations in java](https://www.baeldung.com/java-binary-search)

- [CS50 short video about binary search](https://video.cs50.io/T98PIp4omUA)

- [geeks for geeks explanation](https://www.geeksforgeeks.org/binary-search/)


If you saw my article about Selection Sort it means that you already know at least one sorting algorithm. Now that you have a sorted list (or can create one) we are gonna dive in an algorithm that can search for an element in this sorted list

Implementing Binary Search in Java


**Selection Sort** is a simple sorting algorithm. In this article we are gonna implement it using java to sort an array from smallest to largest element. We are gonna talk about it's **time complexity** too. Let's dive into it!



Let's start by creating our first java file `SelectionSort.java`

In this file we are going to create a method called `sort` that returns an array of ints.

```java
int[] sort(int[] arr) {
	int index;
    //looping the unsorted list
	for (int first = 0; first < arr.length; first++) {

	}
}
```

Here we start by creating a integer variable called `index` (that we are going to use later) and a loop that iterates through all the array. Then we are going to make `index` have the same value as `first`, make another loop and implement our condition... Yeah that's a lot! Allow me to explain.

```java
int[] sort(int[] arr) {
	int index;
    //looping the unsorted list
	for (int first = 0; first < arr.length; first++) {
		
        //index starts at first but changes in every loop
		index = first;	
			
		//then every loop the index is compared with all numbers
		//except the one we are comparing to (the index)
		for (int i = first + 1; i < arr.length; i++) {
			//check if value is lower
			if (arr[i] < arr[index]) {
				//if it is, change index to it
				index = i;
            }
        }
	}
}			
```

Let's start explaining this second loop we made. This loop is inside the first loop, so every time we iterate the first loop once, we get a value of the list and go through all the elements in the array using the second loop, so we can compare the value we got in the first loop with all the elements in the array with the second loop.

IMPORTANT: In the second loop we make `int i = first + 1` because we are looping every item in the list EXCLUDING only the one we are actually comparing, because the value we have is never gonna be smaller than itself.

After the two loops were made we make a condition inside the second loop, where we check if the the items in the for loop (`arr[i]`) is smaller than the value we got with the first loop (`arr[index]`) . If the condition is true we make the index, that holds our smaller number so far, be the index of the smaller number found. The if condition checks every number in the second loop until the end, getting the smaller number in the array and saving its index with the `index = i` .

Now that our second loop got to the end and we have the index of our smallest number we need to swap the position he is in

```java
int[] sort(int[] arr) {
    int index;
    //looping the unsorted list
    for (int first = 0; first < arr.length; first++) {

        //index starts at first but changes in every loop
        index = first;


        //then every loop the index is compared with all numbers
        //except the one we are comparing to (the index)
        for (int i = first + 1; i < arr.length; i++) {
            //check if value is lower
            if (arr[i] < arr[index]) {
                //if it is, change index to it
                index = i;
            }
        }

        //holds the value of the minimum we found
        int temp = arr[index];
        //places the value that was in the start at the place we found our index
        arr[index] = arr[first];
        //puts the value from the index in the start
        arr[first] = temp;
    }
    //terminate the loop and return array sorted
    return arr;

}
```

Here I we have all the sort method ready, I put it all completed here so you don't get confused on where the pieces of code are in the big picture, but we are going to be talking about the end, the swap and return part:

```java
        //holds the value of the minimum we found
        int temp = arr[index];
        //places the value that was in the start at the place we found our index
        arr[index] = arr[first];
        //puts the value from the index in the start
        arr[first] = temp;
    }
    //terminate the loop and return array sorted
    return arr;

}
```

I'm gonna talk about this giving an example that was made in CS50 algorithms part (highly recommend), you have two cups, one with a blue liquid and the other with a red liquid. You want to swap the blue liquid of the 1 cup to be in the 2 cup and the red liquid of the 2 cup to be in the 1 cup without mixing. What do you do? A good way to do this is have a **"Temporary cup"**, a 3 cup that will hold your blue liquid, so you can put the red liquid in the 1 cup, and then put the blue liquid in the 2 cup.

![Swap Two Numbers Program in C - C Programs](https://www.sitesbay.com/program/images/swap-two-numbers-ex.gif)

In code we are doing the same thing! We are making a temporary variable `int temp` and assigning the value of the smallest number we found to it. Then we make the value of `arr[index]`, that is current the smallest number, be the value of the first loop, and we make the value of the first loop be the temporary variable, the smallest number.

With that we made our swap! So after that the first iteration of the first loop finally ends and repeats itself again until we looked at every number and compared, choose and swap then. Now we just need to return the sorted array with `return arr` .

### Time complexity

Before we print make our print method and then execute our code to see everything working let's explain the time complexity of this algorithm. We start the algorithm making a loop that goes through every number in the array. which means that we have a `O(n)` because `n` is the number of steps and is = to the number of elements we have in the array. After that we have a second loop, inside the first loop, that iterate through every number in the array too, so that's another `O(n`). So we have a `O(n)` that for every n inside of it there's another `O(n)`, that makes `O(n X n)` or `O(n^2)`. So the time complexity of this algorithm is `O(n^2)` !

#### Wait a second...

Maybe you are questioning yourself "But every time we make our second loop we make it be the position of the first loop + 1, so we don't check n entirely in the second loop, so it would be n-1,n-2..." and yes, you are actually right! at the end of the second loop we would be checking just one element, so the time complexity should be something like `O(n X 1/2 X n)`. This is correct, but in the **Big O notation** we ignore constants like 1/2, so in the end we just have O(n X n) and that's why it stays like that!



Okay that was a mouthful, but we are almost at the end! now we are just going to create the last method, `printArray`:

```java
	void printArray(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " | ");
		}
	}
```

Here we don't need to return anything, we are just making a for loop that goes through all the array and prints the values with a pipe `|` separating them.



Now we are gonna create a java file to execute and test this algorithm! Let's create a file called `SelectionSortMain.java`

```java
package selectionSort;

public class SelectionSortMain {
	public static void main(String args[]) {
	SelectionSort selection = new SelectionSort();
	
	//create the array
	int[] arr = {10, 6, 4, 8, 2};
	
	//This is gonna print the original array
	System.out.println("Unsorted array: ");
	selection.printArray(arr);
	
	//sort the array
	selection.sort(arr);
	
	//used println here just to make a space since we used print in the printArray
	System.out.println();
	
	//print sorted array
	System.out.println("Sorted array: ");
	selection.printArray(arr);
	}
	
}

```

Here we just create an array, print it unsorted (with our printArray method) and then we use our sort method and print it again, so our output should be this:

```
Unsorted array: 
10 | 6 | 4 | 8 | 2 | 
Sorted array: 
2 | 4 | 6 | 8 | 10 | 
```

And that's pretty much it! Hope this article helped you in some what way. You can check out the repo I made in Github with all the code and with more implementations of DS&A. I'm new to making articles and writing in general but I'm trying to improve! Any questions or suggestions are pretty much appreciated. Good luck on your learning journey!

### Some useful links

-  [Grokking Algorithms book](https://www.amazon.com/Grokking-Algorithms-illustrated-programmers-curious/dp/1617292230/ref=sr_1_1?crid=3TOXYOE3D8OAZ&dchild=1&keywords=grokking+algorithm&qid=1607583227&sprefix=grokking%2Caps%2C317&sr=8-1)

- [CS50 notes about selection sort](https://cs50.harvard.edu/college/2020/fall/notes/3/#selection-sort)

- [javatpoint selection sort implementation](https://www.javatpoint.com/selection-sort-in-java)



Selection Sort is a simple sorting algorithm. In this Article we are gonna implement it in java. A post from the series A&DS in java.

Implementing Selection Sort in Java


Linked lists are really important data structures, they let us store values in different parts of the memory and find them by their addresses. Today in this article I'm gonna go on how to implement a Singly Linked List in java.



lets create our first java file `SinglyLinkedList.java`

Inside lets start by making a class that will represent the `Node` 

```java
package singlyLinkedList;

class Node {
	//thats the value(data) that is inside the Node
	public int data;
	//Thats the pointer inside the Node, every Node
	//has a pointer that store the address of the next node
	//Here we call this pointers "next"
	public Node next;
	
	public void displayNodeData() {
		System.out.print( data +  " -> ");
	}
	
}
```

This class will represent the Node, every Node in a liked list stores a value, represent by our `public int data` in code, and a pointer to the next Node that will be represented by our `public Node next` in our code. Inside this class we made a method that will just print the data so that in the end we can see our results.



Okay now inside our class `SinglyLinkedList` we are gonna start by defining a Node that represents the start of our list, a `head` node.

```java
public class SinglyLinkedList {
	//Its private because we only need to reference head
	//inside this class
	private Node head; //here head == null
```

IMPORTANT: `head = null` even if we don't write it explicitly, java does that for us.

We are gonna use head in our methods to reference the beginning of our list  (aka our first node) and for iterations, we will see this now.

Our first method is gonna be a simple insert,We are gonna use this method to insert a value at the beginning of the list

```java
	public void insertFirst(int data) {
		Node newNode = new Node();
		newNode.data = data;
		newNode.next = head;
		head = newNode;
	}
```

Here we first create a new Node called node `Node node = new Node();` then we set the data of this node to the parameter `data` that we will pass as argument later when we call it. In the end we make the `newNode` point to the head (which is null) and then make head points to the `newNode` so now head is holding the address of this `newNode` and `newNode` is pointing to null, which is the end of the list.

IMPORTANT: Just to clear things out, if we `insertFirst` two times (like we are gonna do later) the second `newNode` is gonna start pointing to head which is the address of the first `newNode` and then head is gonna point to the second `newNode` making this:

```markdown
 head
  ↓
newNode -> null
```

be this:

```markdown
 head
  ↓
newNode2 -> newNode -> null
```



Now lets make our `deleteFirst` method

```java
	public void deleteFirst() {
		//shifts the first node (head) to be where 
		//it was pointing (second node)
		head = head.next;
	}
```

This one is more simple and to the point, head points to what is next to the head. Basically shifts head to be the second node, making it the first node.

Before we continue with building our other methods lets make a `printLinkedList` method so you can see the results and have a better visualization of what the code is doing too.

Here is our `printLinkedList` method

```java
	public void printLinkedList() {
		Node current = head;
		while (current != null) {
			current.displayNodeData();
			current = current.next;
			
		}
		System.out.print("NULL");

	}
```

We just make a Node called `current` that starts at head,which means that the node current starts pointing to the address of the first node. Then we loop the `current` node so that every loop we Displays our node data (with the `displayNodeData()` we made in our node class) and shifts  the current node to the next node, passing through all the nodes in the linked list until we find null (which is the end), after the loop we just print "NULL" to indicate end of the list and make a nicer representation with the print.

Now lets create another java file called `LinkedListMain.java` . This is the file we will execute.

```java
package singlyLinkedList;

public class LinkedListMain {
	public static void main(String args[]) {
		SinglyLinkedList linkedList = new SinglyLinkedList();
		linkedList.insertFirst(1);
		linkedList.insertFirst(8);
		linkedList.insertFirst(5);
        linkedList.insertFirst(3);
        linkedList.deleteFirst();
		//its gonna be 5 -> 8 -> 1 -> NULL
		linkedList.printLinkedList();
	}
}
```

Here we are gonna call our methods, when you run it the output should be `be 5 -> 8 -> 1 -> NULL`

Now you can test the methods the way you want! Lets get back to creating our other methods.



We created methods for inserting in the first place and deleting the first place, but if we want to put something at the last place? Well lets create methods for it, starting with `insertLast`

```java
	public void insertLast(int data) {
		Node current = head; //start from the first node
		//loop until current == null because you are looping
		//all the nodes until you find the end (null)
		while(current.next != null) {
			current = current.next;
		}
		//insert the newNode next to current
		//which now is the final node
		Node newNode = new Node();
		newNode.data = data;
		current.next = newNode;
	}
```

Okay, here we start by doing something pretty similar to what we did in the `printLinkedList` method, we start by the head and loop, but here we loop until the current is pointing to null and not IS equal null. Because with this we will have current as the last node, because the last node is the one that points to null. Then we create a `newNode` and make the `current` point to the `newNode` so now it is the last node because the order changed from 

`current -> null` 

to

 `current -> newNode -> null` .



After that we can create our `deleteLast` method

```java
	public void deleteLast() {
		Node current = head;
		Node temp = head;
		while (current.next != null) {
			temp = current;
			current = current.next;
		}
		current = temp;
		current.next = null;
	}
```

Here we make like the `insertLast` method and make the exact same loop, but we have something different. That is the Node `temp`, so we can move current to the last position with our loop, but we also move the temp alongside so that in the end we have current in the last position `current -> null` but we have temp before that `temp -> current -> null` . Then we make current shift to temp position and make current point to null.



Okay, that`s great and all but... what if we want to put something in the middle for example? Or delete it? Well we can make a method to put a node anywhere AFTER another node.

Lets start with the `insertAfter` 
```` java
	public void insertAfter(Node after,int data) {
		Node current = head;
		Node temp = head;
		while (temp.data != after.data ) {
			temp = current;
			current = current.next;
		}
		Node newNode = new Node();
		newNode.data = data;
		temp.next = newNode;
		newNode.next = current;
	}
````
In the `insertAfter` we again use `temp` and we make a similar loop, but the condition is different. Now we want to match the `temp.data` that we are looping with the `after.data` that is a node we are gonna pass to our method. When the loop finishes we have `temp` in the place of our `after` node, which means we are gonna insert our `newNode` after the `temp` node where our `current` node is. After the loop we create the `newNode` and we make temp point to the `newNode` and make `newNode` point to the `current` node.



Now we have our last method, the `deleteAfter` method

````java
	public void deleteAfter(Node after) {
		Node current = head; 
		while (current.data != after.data) {
			current = current.next;
		}
		current.next = current.next.next;
	}
````

Here we check if the `current.data` is != to `after.data` so we can have the position of the `after` node (the same way we made with `temp` in the last one). Then we just make the current point to what the it was pointing before was pointing to. Example:

`current -> node1 -> node2`

After the `current.next = current.next.next`:

`current -> node2` 



And that`s all our  methods implemented and explained. Now we can test all of them

```java
package singlyLinkedList;

public class LinkedListMain {
	public static void main(String args[]) {
		SinglyLinkedList linkedList = new SinglyLinkedList();
		linkedList.insertFirst(1);
		linkedList.insertFirst(8);
		linkedList.insertFirst(5);
		//its gonna be 5 -> 8 -> 1 -> NULL
		
		linkedList.insertLast(3);
		//now its gonna be 5 -> 8 -> 1 -> 3 -> NULL
		Node node = new Node();
		node.data = 1;
		linkedList.insertAfter(node, 10);
		// now its gonna be 5 -> 8 -> 1 -> 10 -> 3 -> NULL
		
		
		Node node2 = new Node();
		node2.data = 8;
		linkedList.deleteAfter(node2);
		// now its gonna be 5 -> 8 -> 10 -> 3 -> NULL
		linkedList.deleteFirst();
		//now its gonna be 8 -> 10 -> 3 -> NULL
		linkedList.insertFirst(14);
		//now its gonna be 14 -> 8 -> 10 -> 3 -> NULL
		linkedList.insertLast(40);
		// now its gonna be 14 -> 8 -> 10 -> 3 -> 40 -> NULL
		linkedList.deleteFirst();
		//now its gonna be 8 -> 10 -> 3 -> 40 -> NULL
		linkedList.insertLast(56);
		//now its gonna be 8 -> 10 -> 3 -> 40 -> 56 -> NULL
		linkedList.deleteLast();
		// now its gonna be 8 -> 10 -> 3 -> 40 -> NULL
		linkedList.printLinkedList();
	}
}
```



I hope you understood or at least I could help just a little bit in your learning. This is my first article so I may or may not have explained or write in a good way but I will try to improve as I write more! If you want the source code you can check my [repository](https://github.com/GMkonan/A-DS_Java/tree/master/src/singlyLinkedList) in [Github](https://github.com/GMkonan) where I'm trying to make a list of Data Structures and Algorithms implemented in java (and maybe later in C ) with everything up to date or the source below that is the exact same code as above, I will let some links that you can check more about linked lists and that's it. Good studying and good luck!



`SinglyLinkedList.java`

```java
package singlyLinkedList;

class Node {
	//thats the value(data) that is inside the Node
	public int data;
	//Thats the pointer inside the Node, every Node
	//has a pointer that store the address of the next node
	//Here we call this pointers "next"
	public Node next;
	
	public void displayNodeData() {
		System.out.print( data +  " -> ");
	}
	
}

public class SinglyLinkedList {
	//Its private because we only need to reference head
	//inside this class
	private Node head; //here head == null
    
    public void insertFirst(int data) {
        Node newNode = new Node();
        newNode.data = data;
        newNode.next = head;
        head = newNode;
	}
    
	public void deleteFirst() {
		//shifts the first node (head) to be where 
		//it was pointing (second node)
		head = head.next;
	}
    
	public void insertLast(int data) {
		Node current = head; //start from the first node
		//loop until current == null because you are looping
		//all the nodes until you find the end (null)
		while(current.next != null) {
			current = current.next;
		}
		//insert the newNode next to current
		//which now is the final node
		Node newNode = new Node();
		newNode.data = data;
		current.next = newNode;
	}
    
	public void deleteLast() {
		Node current = head;
		Node temp = head;
		while (current.next != null) {
			temp = current;
			current = current.next;
		}
		current = temp;
		current.next = null;
	}
    
	public void insertAfter(Node after,int data) {
		Node current = head;
		Node temp = head;
		while (temp.data != after.data ) {
			temp = current;
			current = current.next;
		}
		Node newNode = new Node();
		newNode.data = data;
		temp.next = newNode;
		newNode.next = current;
	}
    
	public void deleteAfter(Node after) {
		Node current = head; 
		while (current.data != after.data) {
			current = current.next;
		}
		current.next = current.next.next;
	}
    
	public void printLinkedList() {
		Node current = head;
		while (current != null) {
			current.displayNodeData();
			current = current.next;
			
		}
		System.out.print("NULL");

	}
}
```



`LinkedListMain.java`

```java
package singlyLinkedList;

public class LinkedListMain {
	public static void main(String args[]) {
		SinglyLinkedList linkedList = new SinglyLinkedList();
		linkedList.insertFirst(1);
		linkedList.insertFirst(8);
		linkedList.insertFirst(5);
		//its gonna be 5 -> 8 -> 1 -> NULL
		
		linkedList.insertLast(3);
		//now its gonna be 5 -> 8 -> 1 -> 3 -> NULL
		Node node = new Node();
		node.data = 1;
		linkedList.insertAfter(node, 10);
		// now its gonna be 5 -> 8 -> 1 -> 10 -> 3 -> NULL
		
		
		Node node2 = new Node();
		node2.data = 8;
		linkedList.deleteAfter(node2);
		// now its gonna be 5 -> 8 -> 10 -> 3 -> NULL
		linkedList.deleteFirst();
		//now its gonna be 8 -> 10 -> 3 -> NULL
		linkedList.insertFirst(14);
		//now its gonna be 14 -> 8 -> 10 -> 3 -> NULL
		linkedList.insertLast(40);
		// now its gonna be 14 -> 8 -> 10 -> 3 -> 40 -> NULL
		linkedList.deleteFirst();
		//now its gonna be 8 -> 10 -> 3 -> 40 -> NULL
		linkedList.insertLast(56);
		//now its gonna be 8 -> 10 -> 3 -> 40 -> 56 -> NULL
		linkedList.deleteLast();
		// now its gonna be 8 -> 10 -> 3 -> 40 -> NULL
		linkedList.printLinkedList();
	}
}
```



### Some Links that you may find interesting

- [cs50 notes about DS](https://cs50.harvard.edu/college/2020/fall/notes/5/)

- [insert node at beginning linked list by log2base2](https://www.log2base2.com/data-structures/linked-list/inserting-a-node-at-the-beginning-of-a-linked-list.html)

- [Grokking Algorithms book](https://www.amazon.com/Grokking-Algorithms-illustrated-programmers-curious/dp/1617292230/ref=sr_1_1?crid=3TOXYOE3D8OAZ&dchild=1&keywords=grokking+algorithm&qid=1607583227&sprefix=grokking%2Caps%2C317&sr=8-1)

Linked lists are really important data structures, they let us store values in different parts of the memory and find them by their addresses. In this article I'm gonna go on how to implement a Singly Linked List in java.

Why we use "key" in React?

07/13/2021

The compiling process

06/28/2021

Customizing Git Bash in Windows

05/21/2021

Implementing Binary Search in Java

01/25/2021

Implementing Selection Sort in Java

12/11/2020

Implementing Singly Linked Lists in Java

12/10/2020