This post is part of a personal study group activity, summarizing the content after reading through the book "Grokking Algorithms".

Studying alone is fine and all, but it's inefficient. I spend most of my time sitting in front of the computer, but if you ask me how much of that is genuinely spent studying, I have to look away awkwardly.

Since I'd just started developing and using my own blog, I decided to join a study group to help with studying too. After selling off my laptop, I'd wanted to join a study group but couldn't — so the moment I heard I could join without a laptop, I signed up right away.

As someone without a formal CS background, foundational knowledge like data structures has always been my Achilles' heel — especially, as I feel painfully whenever I solve Baekjoon problems. I hope that by the end of this study group, I'll at least have a solid grasp of the basics of data structures.

The language used will primarily be JAVA.

This chapter introduces the basics of arrays and their associated operations, giving readers a rough conceptual understanding of arrays.

It covers the concepts of arrays and sets. According to the author, as the chapters progress, there will be an incremental comparison of computational performance, so we'll be able to see how applying algorithms improves performance.

An array is a very basic data structure that exists in nearly every language.

JAVA distinguishes between primitive types like int and boolean, and reference types like String and HashMap.

These types of data can each be used individually, but there are frequent cases where you need to work with multiple pieces of data at once. A collection of such data can form a single array.

A collection of String data becomes a string array, String[], and a collection of int data becomes an integer array, int[].

In JAVA, an array is a data structure that groups together multiple pieces of a specific type of data, and it can only accept elements of the designated data type.

For example, boolean is a data type consisting of true and false. boolean[] is an array made up of multiple boolean values, and an array declared this way can only accept true or false, the values that belong to boolean. In other words, you can't insert something like 1 or the string "A" into it.

Also, arrays have a fixed length. Once an array is allocated, its length never changes unless it's reallocated.

⚠Wait! This only applies to JAVA!
The array characteristics described here are specific to JAVA. Just looking at JavaScript, for instance, arrays don't really have such restrictions. Their length can grow as needed, and elements can be assigned any data type at all.

In JAVA, arrays are reference types.

There are 4 operations that can be performed on an array.

• Read
• Search
• Insert
• Delete

These 4 operations are the most basic array operations. Let's implement each of these 4 operations directly in JAVA and see what steps are involved.

The read operation reads the value stored at a specific index of an array.

In the runtime of nearly every language, allocated data is recorded in memory. The more data that's allocated, the more memory — that is, RAM — a program requires. Games like Battlegrounds or StarCraft II require a large amount of memory, precisely because the volume of data being recorded and processed is so massive.

When data is allocated to memory, it's stored at an available memory address. Since the value you want exists at that memory address, to retrieve the value you access the memory address where it's stored and read it. In most languages, including JAVA, this process happens internally, hidden from the developer. Handling this directly is exactly what makes C's infamous pointers so notorious.

JAVA's memory is managed by the JVM (Java Virtual Machine). Starting from the JVM's memory structure would branch out endlessly, so let's just focus on the essentials.

As mentioned above, arrays are a reference type, and this reference type is managed in the JVM's Heap area. A simplified diagram of memory looks like this.

Let's say one box can hold one piece of data. Suppose we allocate an integer array made up of 5 integers — 6, 43, 14, 9, 94 — into memory. The JVM checks whether it can record the array of that size in memory, and if it can, it records it.

The array gets recorded at an appropriate location in memory, as shown above. Now let's read the 4th element of this array.

The program knows the address of that array — naturally, since it allocated it itself. Assuming the array's address is 0x0404, we can diagram it as follows.

Since we're retrieving the 4th piece of data starting from 0x0404, all we need to do is look up the data at 0x0407.

😒Wait, you said 4th element...
Nearly every computer language starts indexing at 0. The reason lies in memory — relative to memory, the first piece of data in the array requires no shift in address at all.
If the address is 0x0101, the first piece of data is also at 0x0101, meaning there's no address shift, so it's defined as the 0th element. This is a matter of perspective — early programming languages adopted this approach, and the countless languages that followed were influenced by it.

Since we're reading data by adding the index to the array's address, the operation works like this.

Starting from address 0x0404, we access the address of the 4th element, 0x0407. Since we already know both the array's address and the index, we can access it directly without any additional computation. This lets us access the value 9 stored at 0x0407.

JAVA
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;

/**
 * 누구나 자료 구조와 알고리즘 배열 읽기 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/07/10/about-algorithm-chapter01/">자료구조가 중요한 까닭</a>
 * @since 2021.07.09 Fri 22:53:39
 */
public class ArrayRead
{
	// 배열
	private static final int[] ARRAY = { 6, 43, 14, 9, 94 };
	
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 *
	 * @throws IOException 데이터 입출력 예외
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		// 읽을 인덱스
		int index = 4;
		
		int result = read(index);
		
		StringBuilder builder = new StringBuilder();
		builder.append("4번 째 아이템: ");
		builder.append(result);
		
		writer.write(builder.toString());
		writer.newLine();
		writer.flush();
		writer.close();
	}
	
	/**
	 * 배열 읽기 결과 반환 함수
	 *
	 * @param index: [int] 인덱스
	 *
	 * @return [int] 인덱스에 해당하는 값
	 */
	private static int read(int index)
	{
		return ARRAY[index];
	}
}

TC
4번 째 아이템: 9

The JAVA source is shown above. We declare the array array, and calling array[3] assigns the array's 4th value, 94, to the variable four. Since we access the target directly, this task requires only a single step.

As shown above, if we know the exact address value or index, we can retrieve the corresponding value directly, with no additional computation. But in practice, working with arrays doesn't always give you such simple cases.

Suppose we have an array whose structure we don't know. There are plenty of situations where we need to find a desired value within that array. In this case, we don't have the index of the value we want, and we don't even know whether the value even exists inside the array. In this situation, we need to use the search operation to find a value in the array.

Let's bring back the array we declared above.

This time, let's assume we don't have accurate information about this array. We currently have no idea what value exists at what index of this array.

Let's search for the value 14 in this situation.

You could think of search as just a repetition of read operations. The image above clearly demonstrates this nature of search. To find our target value 14, we sequentially read starting from array[0] until we find 14.

If we could somehow reduce the number of reads while still performing a valid search, we could effectively reduce the time required.

JAVA
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;

/**
 * 누구나 자료 구조와 알고리즘 배열 검색 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/07/10/about-algorithm-chapter01/">자료구조가 중요한 까닭</a>
 * @since 2021.07.09 Fri 23:47:03
 */
public class ArrayFind
{
	private static final int[] ARRAY = { 6, 43, 14, 9, 94 };
	
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 *
	 * @throws IOException 데이터 입출력 예외
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		// 목표 숫자
		int target = 14;
		
		int result = find(target);
		
		StringBuilder builder = new StringBuilder();
		builder.append(target);
		builder.append("이 포함된 인덱스: ");
		builder.append(result);
		
		writer.write(builder.toString());
		writer.newLine();
		writer.flush();
		writer.close();
	}
	
	/**
	 * 요소 검색 및 인덱스 반환 함수
	 *
	 * @param target: [int] 목표 숫자
	 *
	 * @return [int] 인덱스
	 */
	private static int find(int target)
	{
		// 인덱스
		int result = -1;
		
		for (int i = 0; i < ARRAY.length; i++)
		{
			// 목표 숫자와 배열의 값이 일치할 경우
			if (target == ARRAY[i])
			{
				result = i;
				break;
			}
		}
		
		return result;
	}
}

TC
14이 포함된 인덱스: 2

However, the code above applies the most basic possible search algorithm. Finding the 3rd element requires 3 steps, and finding the 5,484th element requires 5,484 steps.

However, if the element happens to be at the very end, or unfortunately doesn't exist in the array at all, we might need to search through the entire array. In other words, if the array has $N$ elements, the maximum number of steps a search can require is $N$.

Adding a new element to an array is called the insert operation. Let's learn about the insert operation by walking through the process of inserting 55 into an array.

If we've allocated an array at runtime, we already know its address. If we're adding an element to the very end of the array, we can simply append it.

But things change a bit if we're inserting into the middle of the array. We need to shift every element after the insertion point back by one position, and then insert the value at that position.

In the worst case, if we insert an element at index 0, the very first index of the array, we need to shift every single element back by one position before inserting 55. In other words, if the array has $N$ elements, the amount of work required for an insertion consists of $N$ operations to shift $N$ elements one at a time, plus 1 operation to insert the element at that index — for a maximum of $N + 1$ operations.

JAVA
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Arrays;

/**
 * 누구나 자료 구조와 알고리즘 배열 삽입 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/07/10/about-algorithm-chapter01/">자료구조가 중요한 까닭</a>
 * @since 2021.07.09 Sat 00:27:47
 */
public class ArrayInsert
{
	// 배열
	private static final int[] ARRAY = { 6, 43, 14, 9, 94, -1, -1, -1, -1, -1 };
	
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 *
	 * @throws IOException 데이터 입출력 예외
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		// 삽입할 인덱스
		int index = 2;
		
		// 삽입할 요소
		int item = 55;
		
		insert(index, item);
		
		StringBuilder builder = new StringBuilder();
		builder.append(index);
		builder.append("번 째 요소에 ");
		builder.append(item);
		builder.append(" 삽입: ");
		builder.append(Arrays.toString(ARRAY));
		
		writer.write(builder.toString());
		writer.newLine();
		writer.flush();
		writer.close();
	}
	
	/**
	 * 배열 삽입 함수
	 *
	 * @param index: [int] 삽입 위치
	 * @param item: [int] 삽입할 요소
	 */
	@SuppressWarnings("ManualArrayCopy")
	private static void insert(int index, int item)
	{
		// 배열의 값이 -1(빈 요소)가 아닐 경우
		if (ARRAY[index] != -1)
		{
			for (int i = ARRAY.length - 1; i > index; i--)
			{
				ARRAY[i] = ARRAY[i - 1];
			}
		}
		
		ARRAY[index] = item;
	}
}

TC
2번 째 요소에 55 삽입: [6, 43, 55, 14, 9, 94, -1, -1, -1, -1]

The insertion source is shown above.

What is @SuppressWarnings?
IDEs like Eclipse and IntelliJ notify developers of errors or warnings while analyzing code, encouraging them to eliminate potential risks. Sometimes, even when behavior is intentional, the IDE's optimization settings trigger a warning anyway. In that case, the @SuppressWarnings annotation lets you suppress that warning. Removing @SuppressWarnings has no effect on how the code runs.

As mentioned above, JAVA arrays have a fixed length. Since performing an insert operation necessarily requires the array to be at least one element larger than the current data, unlike before, I declared an array with a total length of 10. If an array element is -1, that element is considered unallocated and empty.

A List with variable length
There are plenty of cases in JAVA too where you need a variable-length array. In that case, you can use List data types like ArrayList. A List has a variable length, making it well-suited for handling unstructured array data.

Starting from the last element of the array down to just before the index we want to insert at, we sequentially assign each element's value to the value of the previous element, shifting elements over. Then, by assigning the value to the target insertion index, the insertion is complete.

Since we can insert, we may also need to do the opposite: delete. The delete operation removes the element at a desired index. Simply put, it's the exact opposite process of insertion.

Likewise, if we're deleting the element at the very end of the array, all we need to do is remove that last element.

But if we're deleting from the middle of the array, similar work is required. We delete the element at the target position, and then need to shift the remaining elements over by one position.

In the worst case, if we delete the element at index 0, the very first index of the array, we need to delete that element and then shift every remaining element forward by one position. In other words, if the array has $N$ elements, the amount of work required for a deletion consists of 1 operation to delete the element at that index, plus $N - 1$ operations to shift the remaining $N - 1$ elements one at a time — for a maximum of $N$ operations.

JAVA
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Arrays;

/**
 * 누구나 자료 구조와 알고리즘 배열 삭제 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/07/10/about-algorithm-chapter01/">자료구조가 중요한 까닭</a>
 * @since 2021.07.09 Sat 00:59:02
 */
public class ArrayDelete
{
	// 배열
	private static final int[] ARRAY = { 6, 43, 14, 9, 94 };
	
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 *
	 * @throws IOException 데이터 입출력 예외
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		// 삭제할 인덱스
		int index = 2;
		
		remove(index);
		
		StringBuilder builder = new StringBuilder();
		builder.append(index);
		builder.append("번째 요소 삭제 ");
		builder.append(Arrays.toString(ARRAY));
		
		writer.write(builder.toString());
		writer.newLine();
		writer.flush();
		writer.close();
	}
	
	/**
	 * 배열 삭제 함수
	 *
	 * @param index: [int] 삭제 위치
	 */
	@SuppressWarnings("ManualArrayCopy")
	private static void remove(int index)
	{
		// 배열의 값이 -1(빈 요소)가 아닐 경우
		if (ARRAY[index] != -1)
		{
			for (int i = index; i < ARRAY.length - 1; i++)
			{
				ARRAY[i] = ARRAY[i + 1];
			}
			
			ARRAY[ARRAY.length - 1] = -1;
		}
	}
}

TC
2번째 요소 삭제 [6, 43, 9, 94, -1, -1, -1, -1, -1, -1]

The deletion source is shown above.

Unlike insertion, deletion doesn't require the array to grow in size. Likewise, if an array element is -1, that element is considered a deleted, empty element.

Opposite to insertion, starting from the index to delete and going up through the end of the array, we sequentially assign each element's value to the value of the following element, shifting elements over. Then, by clearing the final element of the array, the deletion is complete.

With an array, as long as the element type matches, nothing else is really enforced. That means duplicate elements aren't handled either. But sometimes there's a need for an array that doesn't allow duplicate values. The book explains this using the concept of a set.

When inserting an element into an array, checking for duplicates requires a search to be performed first. Insertion only proceeds once the search confirms the element doesn't already exist in the set.

The two images above diagram the results of inserting the non-existent value 55 and the existing value 14 into an array with set semantics applied.

For 55, since it didn't previously exist, insertion succeeds; but for 14, since the same value already exists at index 2, insertion is not possible.

Once the verification step is complete, the insertion process itself is the same as a regular insertion. However, the amount of work involved differs — the work required for the search is added on top of the existing insertion workload.

The worst case is inserting a non-duplicate arbitrary value at index 0 of the array. For an array with $N$ elements, this requires $N$ operations to search through $N$ elements, $N$ operations to shift $N$ elements one at a time, and 1 operation to insert the element at that index — for a maximum of $2N + 1$ operations.

JAVA
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;

/**
 * 누구나 자료 구조와 알고리즘 집합 배열 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/07/10/about-algorithm-chapter01/">자료구조가 중요한 까닭</a>
 * @since 2021.07.10 Sat 01:30:56
 */
public class UniqueArray
{
	// 배열
	private static final int[] ARRAY = { 6, 43, 14, 9, 94 };
	
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 *
	 * @throws IOException 데이터 입출력 예외
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		// 삽입할 인덱스
		int index = 2;
		
		// 삽입할 요소
		int item = 55;
		
		boolean result = hasInserted(index, item);
		
		StringBuilder builder = new StringBuilder();
		builder.append(index);
		builder.append("번 째 인덱스에 ");
		builder.append(item);
		builder.append(" 삽입 결과: ");
		builder.append(result);
		
		writer.write(builder.toString());
		writer.newLine();
		writer.flush();
		writer.close();
	}
	
	/**
	 * 집합 배열 삽입 결과 반환 함수
	 *
	 * @param index: [int] 삽입 위치
	 * @param item: [int] 삽입할 요소
	 *
	 * @return [boolean] 삽입 결과
	 */
	private static boolean hasInserted(int index, int item)
	{
		int result = find(item);
		
		// 중복되지 않을 경우
		if (result == -1)
		{
			insert(index, item);
			
			return true;
		}
		
		// 중복될 경우
		else
		{
			return false;
		}
	}
	
	/**
	 * 요소 검색 및 인덱스 반환 함수
	 *
	 * @param target: [int] 목표 숫자
	 *
	 * @return [int] 인덱스
	 */
	private static int find(int target)
	{
		// 인덱스
		int result = -1;
		
		for (int i = 0; i < ARRAY.length; i++)
		{
			// 목표 숫자와 배열의 값이 일치할 경우
			if (target == ARRAY[i])
			{
				result = i;
				break;
			}
		}
		
		return result;
	}
	
	/**
	 * 배열 삽입 함수
	 *
	 * @param index: [int] 삽입 위치
	 * @param item: [int] 삽입할 요소
	 */
	@SuppressWarnings("ManualArrayCopy")
	private static void insert(int index, int item)
	{
		// 배열의 값이 -1(빈 요소)가 아닐 경우
		if (ARRAY[index] != -1)
		{
			for (int i = ARRAY.length - 1; i > index; i--)
			{
				ARRAY[i] = ARRAY[i - 1];
			}
		}
		
		ARRAY[index] = item;
	}
}

TC
2번 째 인덱스에 55 삽입 결과: true

The insertion source for a set array is shown above.

The find and insert functions use the same logic used in the search and insert sections. Since a set array must only insert unique elements, we construct a hasInserted function to verify there's no duplicate before proceeding with insertion.

The find function returns -1 if the searched element doesn't exist. In other words, a number that gets -1 returned is a unique number. If find returns -1, insertion proceeds via the insert function.

Set objects don't allow duplicates
By default, JAVA arrays don't care about duplicate elements. Because of this, detecting duplicate elements requires building separate verification logic.
However, using a Set object such as HashSet lets you always insert only unique values.

This chapter explains things focused as much as possible on concepts, without incorporating much specific algorithmic knowledge, it seems. In keeping with the author's apparent intent, I also tried to use as many basic data types as possible in my own logic and avoided complex logic wherever possible. I designed the source strictly around the fundamental principles of how each operation works.

The next chapter will get into the real substance of algorithms.