자료구조 입문하기
Data Structures with Java
자료 구조는 데이터를 효율적으로 저장하고, 조직하며 처리하는 방법론입니다. 이는 프로그래밍에서 중요한 역할을 하며, 배열, 연결 리스트, 스택, 큐, 힙, 트리, 그래프 등 다양한 형태가 있습니다. 이들 각각은 특성과 사용 용도가 다르므로, 해결하려는 문제에 따라 최적의 자료 구조를 선택하는 것은 개발자에게 필수적인 능력입니다.
Linear Data Structures
선형 자료구조(Linear Data Structure)는 데이터 요소가 순차적으로 연결되어 있는 구조를 말합니다. 배열(Array), 연결 리스트(Linked List), 스택(Stack), 큐(Queue) 등이 이에 속하며, 데이터를 일렬로 나열하여 관리합니다. 각 요소가 선형으로 연결되어 있기 때문에, 데이터의 추가, 삭제, 접근이 간단하고 직관적인 연산으로 수행됩니다.
선형 자료구조는 기본적이고 직관적인 구조로서, 복잡한 비선형 자료구조나 해시 기반 자료구조의 기초를 형성합니다. 선형 자료구조를 깊이 이해하면 더 복잡한 자료구조의 작동 원리를 파악하는 데 중요한 기반이 될 것입니다.
Arrays
배열(Array)은 동일 유형의 데이터 요소들을 연속적인 메모리 위치에 저장하는 기본적인 자료구조입니다. Java에서 배열은 객체 형태로 구현되며, 각 요소는 0 부터 시작하는 인덱스로 식별됩니다.
이런 특성 덕분에, 배열은 데이터에 빠르게 접근할 수 있으며, 특히 정적인 데이터 집합을 다루거나 데이터에 순차적으로 접근해야 할 때 매우 효율적입니다.
| 🚥 | Features | Descriptions |
|---|---|---|
| 🟢 | Direct Index Access | 각 요소는 인덱스를 통해 직접 접근이 가능하므로, 데이터 검색이 매우 빠르며 O(1)의 시간 복잡도를 가집니다. |
| 🟢 | Data Handling Efficiency | 연속적인 메모리 레이아웃 덕분에 CPU 캐시의 효율을 높여 데이터 처리 속도가 빨라질 수 있습니다. |
| 🟢 | Optimized Memory Access | 배열은 메모리 상에서 연속된 공간을 차지하기 때문에 메모리 관리가 용이하고, 메모리 접근 시간이 최소화됩니다. |
| 🚸 | Fixed Size | 배열은 생성 시점에 크기가 고정되며, 이후 크기를 변경할 수 없어서 동적으로 크기를 조정할 필요가 있는 경우 부적합할 수 있습니다. |
| 🚸 | Inefficiency in Insertion and Deletion | 중간에 있는 요소를 삽입하거나 삭제할 때 나머지 요소들을 이동해야 하므로, 이러한 작업들이 O(n)의 시간 복잡도를 가지게 됩니다. |
| 🚸 | Lack of Flexibility | 배열은 크기 조정이 자유롭지 않으며, 요소의 데이터 타입도 일관되어야 하므로 다양한 타입의 데이터를 하나의 자료구조에서 관리하기 어려울 수 있습니다. |
Java에서 배열을 사용하기 위해서는 먼저 배열을 선언하고 초기화해야 합니다. 배열 선언은 배열이 저장할 데이터 유형과 배열의 크기를 지정합니다.
public static void main(String[] args) {
int[] arr = new int[5];
System.out.println("init: " + Arrays.toString(arr));
}
배열의 길이를 명시적으로 지정하여 생성하면, Java는 모든 요소를 해당 데이터 타입의 기본값으로 자동 초기화합니다.
init: [0, 0, 0, 0, 0]
하지만, 필요에 따라 초기 값들을 직접 바로 할당할 수도 있습니다.
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5}
System.out.println("init: " + Arrays.toString(arr));
}
Inserting Elements into Arrays
배열의 기존 데이터를 유지하면서 새로운 요소를 추가하는 작업은 배열의 특정 위치에 따라 다양한 접근 방식과 복잡도를 가집니다.
배열의 시작 부분에 요소를 추가하는 작업은 배열 내의 모든 요소를 한 칸씩 오른쪽으로 이동시켜야 합니다.
이는 배열의 길이에 비례하는 시간이 소요되므로 O(n)의 시간 복잡도를 갖습니다.
public static void main(String[] args) {
int[] arr = {2, 3, 4, 5, 0};
System.out.println("prev: " + Arrays.toString(arr));
int newValue = 1;
for (int i = arr.length - 1; i > 0; i--) {
arr[i] = arr[i - 1];
}
arr[0] = newValue;
System.out.println("next: " + Arrays.toString(arr));
}
위 코드는 배열의 모든 요소를 오른쪽으로 이동시켜 첫 번째 자리인 인덱스 0에 새로운 요소 1을 추가합니다.
prev: [2, 3, 4, 5, 0]
next: [1, 2, 3, 4, 5]
배열의 중간에 요소를 추가하기 위해서는 지정된 인덱스 위치에서 시작하여 그 이후의 모든 요소를 오른쪽으로 이동시켜야 합니다.
이 작업은 추가하려는 위치에 따라 O(n)의 시간 복잡도를 가질 수 있습니다.
public static void main(String[] args) {
int[] arr = {1, 2, 4, 5, 0};
System.out.println("prev: " + Arrays.toString(arr));
int index = 2;
int newValue = 3;
for (int i = arr.length - 1; i > index; i--) {
arr[i] = arr[i - 1];
}
arr[index] = newValue;
System.out.println("next: " + Arrays.toString(arr));
}
위 예제는 배열의 2번 인덱스에 새로운 값 3을 삽입하여 배열의 요소를 업데이트하고 있습니다.
prev: [1, 2, 4, 5, 0]
next: [1, 2, 3, 4, 5]
배열의 마지막에 요소를 추가하는 작업은 다른 위치에 요소를 추가할 때와 달리 기존 요소들을 이동시킬 필요가 없습니다. 이 때문에 이 작업은 비교적 간단하고 빠릅니다.
배열의 크기에 상관없이 이 과정의 시간 복잡도는 O(1)입니다.
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 0};
System.out.println("prev: " + Arrays.toString(arr));
int newValue = 5;
arr[arr.length - 1] = newValue;
System.out.println("next: " + Arrays.toString(arr));
}
배열의 마지막 인덱스는 배열의 길이에서 1을 뺀 값입니다. 이 인덱스를 활용하면 배열의 마지막 위치에 새로운 데이터를 쉽게 추가할 수 있습니다.
prev: [1, 2, 3, 4, 0]
next: [1, 2, 3, 4, 5]
Removing Elements from Arrays
배열에서 요소를 제거하는 작업은 추가하는 작업과 반대로, 배열 내의 요소를 왼쪽으로 이동시켜야 하는 작업을 포함합니다. 이 과정은 배열에서 특정 요소를 제거하고 남은 요소들을 조정함으로써, 배열의 연속성을 유지합니다. 하지만 배열에서 요소를 제거하는 것은 배열의 크기를 자동으로 줄이지 않으며, 배열의 고정된 크기는 그대로 유지됩니다.
다음은 배열에서 특정 요소를 제거하는 과정입니다:
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
System.out.println("prev: " + Arrays.toString(arr));
int removeIndex = 2;
for (int i = removeIndex; i < arr.length - 1; i++) {
arr[i] = arr[i + 1];
}
arr[arr.length - 1] = 0;
System.out.println("next: " + Arrays.toString(arr));
}
위 코드는 배열의 2번 인덱스 이후 요소들을 한 칸씩 왼쪽으로 이동한 후, 배열의 마지막 위치에는 해당 데이터 타입의 기본값을 할당하여 데이터를 정리합니다.
prev: [1, 2, 3, 4, 5]
next: [1, 2, 4, 5, 0]
Searching for Elements in Arrays
배열에서 특정 요소를 검색하는 두 가지 주요 방법은 인덱스 기반 검색과 값 기반 검색입니다.
배열의 요소들은 연속적인 메모리 구조로 저장되기 때문에 각 요소는 고유한 메모리 주소를 가지게 됩니다. 이러한 메모리 주소를 활용하여 인덱스를 기반으로 배열 요소에 접근할 수 있습니다. 배열의 인덱스는 0부터 시작하여 순차적으로 증가하며, 이를 통해 특정 요소에 매우 빠르게 접근할 수 있습니다. 인덱스 기반 접근 방식은 O(1)의 시간 복잡도를 가지며, 이는 특정 요소를 즉시 찾을 수 있다는 의미입니다.
배열의 메모리 구조, 데이터 타입, 그리고 인덱스를 활용하여 각 요소의 메모리 주소를 다음 공식을 통해 계산할 수 있습니다:
Address of N-th Element = BASE_ADDRESS + (ELEMENT_DATA_SIZE * N)
BASE_ADDRESS: 배열의 시작 주소입니다.ELEMENT_DATA_SIZE: 각 요소의 메모리 크기입니다.
이 공식으로 계산된 메모리 주소를 통해 해당 인덱스에 위치한 요소에 즉시 접근할 수 있습니다. 이 방식은 배열의 각 요소가 메모리 상에서 연속적으로 위치하는 특성을 활용하여, 특정 요소를 빠르고 효율적으로 검색할 수 있는 기술적 장점을 제공합니다.
예를 들어, Java에서 int 타입의 배열에서는 각 정수가 4byte를 차지하므로, 배열의 시작 주소가 0x100이라면, N번째 엘리먼트의 주소는 0x100 + (4 * N)의 계산을 통해 위치를 찾을 수 있습니다.
public static void main(String[] args) {
int[] arr = {10, 20, 30, 40, 50};
int index = 3;
int element = arr[index];
System.out.printf("Element at index %d: %d", index, element);
}
위 코드는 정수형 배열에 저장된 다섯 개의 엘리먼트 중 3번 인덱스에 위치한 엘리먼트를 직접 조회하고, 실행 결과를 콘솔에 출력합니다:
Element at index 3: 40
이 접근법은 배열의 구조적 특성을 적극 활용하여 실행 속도를 극대화합니다. 따라서 정확하고 신속한 데이터 접근이 필수적인 다양한 응용 프로그램에서 배열의 활용이 이상적입니다.
인덱스 기반 검색과 달리 값 기반 검색은 배열 내 특정 값을 찾기 위해 엘리먼트들을 순차적으로 탐색하는 방법입니다. 이 방식은 인덱스 기반 검색과 달리 특정 값의 위치를 미리 알지 못하는 상황에서 사용됩니다. 값 기반 검색은 배열 전체를 조사해야 할 수도 있기 때문에, 최악의 경우 시간 복잡도는 O(n)이 됩니다.
다음은 배열에서 특정 값 40을 찾고 그 위치의 인덱스를 반환하는 과정입니다:
public static void main(String[] args) {
int[] arr = {10, 20, 30, 40, 50};
int element = 40;
int index = -1;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == element) {
index = i;
break;
}
}
System.out.printf("Index of Element %d: %d", element, index);
}
배열의 처음부터 끝까지 순회하면서, 특정 값이 저장된 위치의 인덱스를 조회합니다. 이 검색 과정은 배열의 크기에 따라 성능이 결정되므로, 큰 배열에서는 상당한 시간이 소요될 수 있습니다.
실행 결과는 다음과 같습니다:
Index of Element 40: 3
값 기반 검색은 배열이 정렬되지 않았거나, 데이터의 정확한 위치를 모를 때 사용합니다. 하지만 이 방법은 성능 이슈가 발생할 수 있어, 데이터의 양이 많거나 검색이 빈번한 경우에는 다른 자료 구조를 고려하는 것이 좋습니다.
Expanding Arrays
배열을 초기화할 때 크기를 지정하고, 이 크기에 맞춰 메모리가 할당됩니다. 배열의 크기가 고정되어 있기 때문에, 추가적인 요소를 포함시키기 위해서는 더 큰 새 배열을 생성하고 기존 배열의 요소들을 이로 옮겨야 합니다.
기존 배열의 전체 엘리먼트를 순회하면서 새로운 배열로 데이터를 복사해야 하기 때문에 시간 복잡도가 O(n)으로 증가합니다.
public static void main(String[] args) {
int[] prevArr = {1, 2, 3, 4, 5};
int[] nextArr = new int[prevArr.length + 1];
for (int i = 0; i < prevArr.length; i++) {
nextArr[i] = prevArr[i];
}
int newElement = 6;
nextArr[nextArr.length - 1] = newElement;
System.out.println("prev: " + Arrays.toString(prevArr));
System.out.println("next: " + Arrays.toString(nextArr));
}
- 기존 배열의 크기보다 더 큰 새 배열을 생성합니다. 일반적으로 배열의 크기를 두 배로 늘리는 것이 효율적입니다.
- 기존 배열의 모든 요소를 새 배열로 복사합니다.
- 새 배열의 끝에 새로운 요소를 추가합니다.
prev: [1, 2, 3, 4, 5]
next: [1, 2, 3, 4, 5, 6]
배열 자료구조는 실무에서 광범위하게 활용되지만, 고정된 크기는 데이터의 확장이나 축소 시 새로운 배열을 생성하고 기존 데이터를 복사해야 하는 번거로움을 초래합니다. 이 문제를 해결하기 위해 Java는 ArrayList<E>를 제공합니다. ArrayList는 내부적으로 배열을 사용하되, 데이터의 추가나 삭제 시 자동으로 크기를 조절하여 배열을 재생성합니다. 이는 개발자로 하여금 데이터 구조의 복잡한 관리 작업보다는 비즈니스 로직의 구현에 집중할 수 있게 합니다.
또한, ArrayList는 데이터 삽입, 검색과 같은 다양한 편의 기능과 함께 예외 상황을 효과적으로 관리하는 설계를 갖추고 있어, 동적 데이터 처리의 불편함을 효과적으로 해소합니다. 이러한 특성 덕분에 ArrayList는 배열의 고정 크기 문제를 극복하고, 보다 유연한 데이터 관리를 가능하게 합니다.
ArrayList는 내부적으로 System.arraycopy() 메서드를 통해 기존 배열의 데이터를 새로운 배열로 이동합니다. 이는 메모리 블록을 통째로 옮기는 방식으로 작동하며, 시스템 수준에서 최적화된 고속 메모리 연산을 통해 수행되므로 일반적인 배열 복사보다 훨씬 효율적입니다. System.arraycopy()는 본질적으로 네이티브 메서드로, 자바의 표준 라이브러리가 아닌 하드웨어 수준에서의 메모리 복사를 수행합니다. 이를 통해 자바 언어 내에서 구현된 루프를 통해 요소를 하나씩 복사하는 방식보다 훨씬 빠른 성능을 발휘합니다.
다음과 같이 ArrayList를 활용할 수 있습니다:
import java.util.ArrayList;
public static void main(String[] args) {
ArrayList<Integer> arrayList = new ArrayList<>();
System.out.println("init: " + arrayList);
for (int i = 1; i <= 5; i++) {
arrayList.add(i);
}
System.out.println("prev: " + arrayList);
arrayList.add(6);
System.out.println("next: " + arrayList);
}
배열과 달리 ArrayList는 별도의 크기 지정 없이 생성되었으며, 데이터가 추가됨에 따라 자동으로 크기가 조절됩니다. 초기화 시 사이즈를 지정하지 않으면 JDK 버전에 따라 설정된 기본 용량과 확장 로직이 적용됩니다.
init: []
prev: [1, 2, 3, 4, 5]
next: [1, 2, 3, 4, 5, 6]
배열 자료구조는 매우 유용하지만, 크기 변경이 빈번하게 필요한 경우 성능 저하의 원인이 될 수 있습니다. 이러한 상황에서는 다른 자료 구조를 고려하는 것이 효과적입니다.
Linked Lists
링크드 리스트(Linked List)는 각 요소가 노드(Node)로 구성되며, 각 노드는 데이터와 다음 노드를 가리키는 참조(포인터)를 포함하는 동적 자료구조입니다. 링크드 리스트는 배열과 달리 요소의 삽입 및 삭제가 용이하고, 크기를 동적으로 조정할 수 있습니다.
배열은 메모리가 연속적으로 할당되어 크기 변경이 어렵지만, 연속된 메모리 구조 덕분에 인덱스를 통한 요소 접근이나 일반적인 쓰기 속도가 상대적으로 빠릅니다. 반면, 링크드 리스트는 노드가 필요할 때마다 메모리를 할당받아 분산된 메모리 위치를 가질 수 있어 유연한 메모리 사용이 가능하지만, 요소 접근 시에는 순차적으로 탐색해야 하므로 속도가 느릴 수 있습니다.
링크드 리스트는 노드의 관계에 따라 크게 두 가지 유형으로 나뉩니다:
- 단일 링크드 리스트(Singly Linked List): 각 노드는 다음 노드에 대한 참조만을 가집니다. 단일 링크드 리스트는 구조가 단순하지만, 특정 위치의 노드를 삭제하거나 삽입할 때 이전 노드를 찾아야 하는 단점이 있습니다.
- 더블 링크드 리스트(Doubly Linked List): 각 노드는 다음 노드와 이전 노드에 대한 참조를 모두 가집니다. 더블 링크드 리스트는 단일 링크드 리스트보다 메모리를 더 많이 사용하지만, 노드의 삽입 및 삭제가 더 효율적입니다.
단일 링크드 리스트는 한계가 크기 때문에, 실무에서는 주로 더블 링크드 리스트를 사용합니다.
더블 링크드 리스트의 특징은 다음과 같습니다:
| 🚥 | Features | Descriptions |
|---|---|---|
| 🟢 | Dynamic Size | 더블 링크드 리스트는 동적으로 크기를 조절할 수 있어, 요소의 삽입과 삭제가 자유롭습니다. |
| 🟢 | Efficient Insertions/Deletions | 요소를 삽입하거나 삭제할 때 기존 요소를 이동할 필요가 없으므로, 이러한 작업들이 O(1)의 시간 복잡도를 가집니다. |
| 🟢 | Bidirectional Traversal | 각 노드가 이전 노드와 다음 노드를 참조하므로, 양방향으로 리스트를 순회할 수 있어 탐색이 유연합니다. |
| 🚸 | Sequential Access | 특정 요소에 접근하기 위해 첫 노드 또는 마지막 노드부터 순차적으로 탐색해야 하므로, 임의 접근의 시간이 O(n)이 될 수 있습니다. |
| 🚸 | Extra Memory Space | 각 요소가 데이터와 두 개의 포인터(이전 노드와 다음 노드)를 포함해야 하므로, 배열이나 단일 링크드 리스트보다 더 많은 메모리를 사용합니다. |
Java의 java.util.LinkedList 클래스도 더블 링크드 리스트로 구현되어 있어 양방향으로 노드를 탐색할 수 있으며, 노드의 삽입 및 삭제가 더욱 효율적으로 이루어집니다.
import java.util.LinkedList;
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
transient int size = 0;
/**
* Pointer to first node.
*/
transient Node<E> first;
/**
* Pointer to last node.
*/
transient Node<E> last;
/**
* Links e as first element.
*/
private void linkFirst(E e) {...}
...
}
링크드 리스트 자료구조는 Java에서 제공하는 이 LinkedList<E>를 활용하여 데이터 구조와 다양한 기능을 살펴보겠습니다.
Adding Nodes into Linked Lists
링크드 리스트에 노드를 추가하는 방법에는 리스트의 시작, 끝, 또는 특정 위치에 추가하는 방법이 있습니다.
리스트의 시작 부분에 노드를 추가할 때는 addFirst() 메서드를 사용합니다. 이 메서드는 다음과 같이 정의되어 있습니다:
public void addFirst(E e) {
linkFirst(e);
}
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
addFirst() 메서드는 리스트의 시작 부분에 노드를 추가하는 역할을 합니다. 이 메서드는 내부적으로 linkFirst() 메서드를 호출하여 실제로 노드를 연결합니다. linkFirst() 메서드는 새로운 노드를 생성하고 이를 리스트의 첫 번째 위치에 삽입합니다.
구체적인 동작은 다음과 같습니다:
- 현재 첫 번째 노드를 참조합니다.
- 새로운 노드를 생성하고, 이 노드의 다음 노드를 기존의 첫 번째 노드로 설정합니다.
- 리스트의 첫 번째 노드를 새로운 노드로 업데이트합니다. 리스트가 비어있었다면 새로운 노드를 마지막 노드로 설정하고, 기존의 첫 번째 노드가 존재했다면 그 노드의 이전 노드를 새로운 노드로 설정합니다.
- 리스트의 크기를 증가시킵니다.
- 구조 변경을 나타내는
modCount를 증가시킵니다.
이 addFirst() 메서드를 활용하여 리스트의 시작 부분에 새로운 노드를 추가할 수 있습니다:
import java.util.LinkedList;
public class LinkedListAddFirst {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.addFirst(3);
list.addFirst(2);
list.addFirst(1);
System.out.println("List after adding nodes at the beginning: " + list);
}
}
실행 결과는 다음과 같습니다:
List after adding nodes at the beginning: [1, 2, 3]
리스트의 끝 부분에 노드를 추가할 때는 addLast() 또는 add() 메서드를 사용합니다.
두 메서드 모두 내부적으로 linkLast() 함수를 호출하여 신규 노드를 리스트의 마지막에 연결합니다:
public void addLast(E e) {
linkLast(e);
}
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
이제 addLast() 메서드를 활용한 예제를 살펴보겠습니다:
import java.util.LinkedList;
public class LinkedListAddLast {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.addLast(1);
list.addLast(2);
list.addLast(3);
System.out.println("List after adding nodes at the end: " + list);
}
}
위 코드는 리스트의 끝 부분에 노드 1, 2, 3을 차례대로 추가하며, 실행 결과는 다음과 같습니다:
List after adding nodes at the end: [1, 2, 3]
특정 위치에 노드를 추가할 때는 add(int index, E element) 메서드에 특정 인덱스를 매개인자로 전달합니다. 이 메서드는 다음과 같이 정의되어 있습니다:
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
void linkBefore(E e, Node<E> succ) {
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
링크드 리스트 자료 구조에서 특정 위치에 노드를 추가하는 과정은 다음과 같은 단계로 이루어집니다:
- 주어진 인덱스가 유효한지 확인합니다.
- 유효하다면, 인덱스가 리스트 크기와 같은지 확인합니다.
- 인덱스가 리스트 크기보다 작다면,
linkBefore()함수를 호출하여 새로운 노드를 지정된 인덱스의 기존 노드 앞에 추가합니다. 만약, 인덱스가 리스트 크기와 같다면,linkLast()를 통해 새로운 노드를 리스트의 끝에 추가합니다.
- 기존 노드의 이전 노드를 새로운 노드로, 새로운 노드의 다음 노드를 기존 노드로 설정하여 연결합니다.
- 리스트의 크기를 증가시킵니다.
- 구조 변경을 나타내는
modCount를 증가시킵니다.
이 과정을 통해 리스트의 특정 위치에 새로운 노드를 효율적으로 추가할 수 있습니다. 이제 add(int index, E element) 메서드를 활용한 예제를 살펴보겠습니다:
import java.util.LinkedList;
public class LinkedListInsertAt {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(1);
list.add(3);
list.add(4);
System.out.println("List before inserting a node at index 1: " + list);
list.add(1, 2);
System.out.println("List after inserting a node at index 1: " + list);
}
}
리스트를 생성하여 엘리먼트를 여러개 추가한 다음, 인덱스 1에 노드 2를 삽입하여 리스트를 업데이트합니다. 실행 결과는 다음과 같습니다:
List before inserting a node at index 1: [1, 3, 4]
List after inserting a node at index 1: [1, 2, 3, 4]
Removing Nodes from Linked Lists
링크드 리스트에서 노드를 제거하는 과정은 리스트의 구조를 유지하면서 특정 노드를 삭제하는 작업을 포함합니다. 이는 새로운 노드를 추가하는 과정의 반대 작업입니다. 특정 값을 가진 노드를 제거하려면 remove(Object o) 메서드를 사용할 수 있습니다. 이 메서드는 다음과 같이 정의되어 있습니다:
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
E unlink(Node<E> x) {
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = null;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
이 메서드는 리스트의 엘리먼트를 순회하면서 주어진 매개변수와 일치하는 첫 번째 노드를 찾고, 이를 제거합니다. 매개변수가 null인 경우에는 첫 번째로 null 값을 가진 노드를 찾아 제거합니다. 노드를 제거할 때는 unlink(Node<E> x) 메서드를 호출하여 노드 연결을 재구성합니다. unlink() 메서드는 삭제할 노드의 이전 노드와 다음 노드를 서로 연결하고, 노드를 리스트에서 제거하여 리스트의 크기를 줄입니다.
특정 인덱스의 노드를 제거하는 경우에는 remove(int index) 메서드를 사용합니다. 이 메서드는 다음과 같이 정의되어 있습니다:
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
이 메서드는 주어진 인덱스가 유효한지 확인한 후, 해당 인덱스의 노드를 찾아 unlink(Node<E> x) 메서드를 호출하여 노드를 제거합니다.
이제 remove(int index) 메서드를 활용한 예제를 살펴보겠습니다:
import java.util.LinkedList;
public class LinkedListRemoveNode {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
System.out.println("List before removing node at index 2: " + list);
list.remove(2); // 인덱스 2의 노드를 제거합니다.
System.out.println("List after removing node at index 2: " + list);
}
}
이 예제에서는 LinkedList를 생성하고, 여러 개의 노드를 추가한 다음, 인덱스 2의 노드를 제거합니다. 리스트의 인덱스를 기준으로 노드를 찾아 제거한 후, 결과를 출력합니다.
List before removing node at index 2: [1, 2, 3, 4]
List after removing node at index 2: [1, 2, 4]
이 외에도 LinkedList는 다양한 편의 함수를 제공합니다:
removeFirst(): 리스트의 첫 번째 노드를 제거합니다.removeLast(): 리스트의 마지막 노드를 제거합니다.removeFirstOccurrence(): 리스트에서 특정 값의 첫 번째 발생 노드를 제거합니다.removeLastOccurrence(): 리스트에서 특정 값의 마지막 발생 노드를 제거합니다.
Searching for Nodes in Linked Lists
링크드 리스트에서 특정 값을 가진 노드를 찾기 위해 리스트를 순차적으로 탐색합니다. 특정 값을 가진 노드를 검색하려면 contains() 메서드를 사용할 수 있습니다. 이 메서드는 다음과 같이 정의되어 있습니다:
public boolean contains(Object o) {
return indexOf(o) != -1;
}
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}
contains() 메서드는 리스트에 특정 값이 존재하는지 여부를 확인합니다. 이 메서드는 내부적으로 indexOf() 메서드를 호출하여 값을 검색하고, 값이 존재하면 true를, 존재하지 않으면 false를 반환합니다.
이제 contains() 메서드를 활용한 예제를 살펴보겠습니다:
import java.util.LinkedList;
public class LinkedListSearchNode {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
boolean isFound = list.contains(3); // 노드 3의 존재 여부를 확인합니다.
System.out.println("Is 3 in the list? " + isFound);
isFound = list.contains(5); // 노드 5의 존재 여부를 확인합니다.
System.out.println("Is 5 in the list? " + isFound);
}
}
위 코드는 값 3과 5의 존재 여부를 리스트에서 확인합니다. 실행 결과는 다음과 같습니다:
Is 3 in the list? true
Is 5 in the list? false
특정 인덱스의 노드를 검색하려면 get(int index) 메서드를 사용할 수 있습니다. 이 메서드는 다음과 같이 정의되어 있습니다:
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
Node<E> node(int index) {
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
get(int index) 메서드는 주어진 인덱스가 유효한지 확인한 후, 해당 인덱스의 노드를 반환합니다.
- 인덱스가 유효한지
checkElementIndex()를 호출하여 확인합니다. - 인덱스가 리스트 크기의 절반보다 작은지 확인합니다.
- 작으면 리스트의 첫 번째 노드부터 인덱스까지 순차적으로 탐색합니다. 크거나 같으면 리스트의 마지막 노드부터 인덱스까지 역순으로 탐색합니다.
- 해당 인덱스의 노드를 반환합니다.
이제 get(int index) 메서드를 활용한 예제를 살펴보겠습니다:
import java.util.LinkedList;
public class LinkedListGetNode {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
int element = list.get(2); // 인덱스 2의 노드를 가져옵니다.
System.out.println("Element at index 2: " + element);
try {
element = list.get(5); // 유효하지 않은 인덱스를 조회합니다.
} catch (IndexOutOfBoundsException e) {
System.out.println("Index out of bounds.");
}
}
}
위 코드는 인덱스 2의 노드와 유효하지 않은 인덱스 5의 노드를 조회하는 예제를 보여줍니다. 실행 결과는 다음과 같습니다:
Element at index 2: 3
Index out of bounds.
이 외에도 LinkedList는 조회를 위한 다양한 편의 함수를 제공합니다:
getFirst(): 리스트의 첫 번째 노드를 반환합니다.getLast(): 리스트의 마지막 노드를 반환합니다.peekFirst(): 리스트의 첫 번째 노드를 반환하되, 리스트가 비어있을 경우null을 반환합니다.peekLast(): 리스트의 마지막 노드를 반환하되, 리스트가 비어있을 경우null을 반환합니다.indexOf(): 리스트에서 특정 값의 첫 번째 발생 인덱스를 반환합니다.lastIndexOf(): 리스트에서 특정 값의 마지막 발생 인덱스를 반환합니다.
이와 같은 편의 함수를 통해 다양한 상황에서 링크드 리스트의 노드를 효율적으로 검색할 수 있습니다.
Stacks
스택(Stack)은 후입선출(LIFO, Last In First Out) 원칙에 따라 동작하는 자료구조입니다. 가장 최근에 추가된 요소가 가장 먼저 나갑니다. 이는 컴퓨터 과학에서 매우 중요한 역할을 하며, 특히 운영체제의 프로세스 관리에서 필수적입니다. 예를 들어, 함수 호출 시 스택 프레임에 호출 정보를 저장하고, 함수가 반환될 때 이 정보를 스택에서 꺼내어 이전 상태로 복원합니다. 이러한 방식은 재귀 호출 관리에도 매우 유용합니다.
또한, 스택은 역순 문자열 처리, 깊이 우선 탐색(DFS) 등의 알고리즘에서 사용됩니다. 역순 문자열 처리는 문자열을 스택에 하나씩 쌓은 다음, 꺼내어 역순으로 출력하는 방식으로 구현할 수 있습니다. 깊이 우선 탐색은 그래프의 노드를 방문할 때 스택을 사용하여 경로를 추적하고, 백트래킹을 수행합니다.
스택은 배열 기반과 링크드 리스트 기반으로 구현될 수 있습니다. 배열 기반 구현은 고정된 크기의 배열을 사용하여 스택을 구현하며, 크기 변경이 필요할 때 배열을 동적으로 확장할 수 있습니다. 링크드 리스트 기반 구현은 동적으로 크기를 조절할 수 있는 노드 기반의 구조를 사용합니다.
자바의 java.util.Stack 클래스는 Vector 클래스를 상속받아 배열 기반으로 스택을 구현합니다. 주요 연산으로는 요소 추가, 요소 삭제, 요소 검색 등이 있습니다. 이 연산들은 스택의 맨 위에서만 이루어지며, 이는 스택의 LIFO 특성을 잘 나타냅니다.
Java Collections: Stack vs. Deque
Java에서Stack클래스는Vector를 기반으로 하고 있으며, 이는 동기화된(synchronized) 방식으로 구현되어 있기 때문에 멀티스레딩 환경에서는 안전하지만, 단일 스레드 환경에서는 성능 면에서 비효율적일 수 있습니다. Java 1.0 버전에서 제공되어 지금까지 하위 버전 호환을 위해 남겨져 있는 것으로 짐작되며, 대신 더 현대적인 대안으로Deque인터페이스를 사용하는 것이 권장됩니다.Deque는 Double Ended Queue의 줄임말로, 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조입니다.Deque는 스택(LIFO)과 큐(FIFO) 두 가지 자료구조의 기능을 모두 제공하며, 성능 면에서 매우 효율적입니다.
/**
* The {@code Stack} class represents a last-in-first-out
* (LIFO) stack of objects. It extends class {@code Vector} with five
* operations that allow a vector to be treated as a stack. The usual
* {@code push} and {@code pop} operations are provided, as well as a
* method to {@code peek} at the top item on the stack, a method to test
* for whether the stack is {@code empty}, and a method to {@code search}
* the stack for an item and discover how far it is from the top.
* <p>
* When a stack is first created, it contains no items.
*
* <p>A more complete and consistent set of LIFO stack operations is
* provided by the {@link Deque} interface and its implementations, which
* should be used in preference to this class. For example:
* <pre> {@code
* Deque<Integer> stack = new ArrayDeque<Integer>();}</pre>
*
* @param <E> Type of component elements
*
* @author Jonathan Payne
* @since 1.0
*/
public class Stack<E> extends Vector<E> {
/**
* Creates an empty Stack.
*/
public Stack() {
}
/**
* Pushes an item onto the top of this stack. This has exactly
* the same effect as:
* <blockquote><pre>
* addElement(item)</pre></blockquote>
*
* @param item the item to be pushed onto this stack.
* @return the {@code item} argument.
* @see java.util.Vector#addElement
*/
public E push(E item) {
addElement(item);
return item;
}
/**
* Removes the object at the top of this stack and returns that
* object as the value of this function.
*
* @return The object at the top of this stack (the last item
* of the {@code Vector} object).
* @throws EmptyStackException if this stack is empty.
*/
public synchronized E pop() {
E obj;
int len = size();
obj = peek();
removeElementAt(len - 1);
return obj;
}
...
Push
스택에 요소를 추가하려면 push(E item) 메서드를 사용합니다. 스택은 새로운 요소가 계속해서 위로 쌓이는 구조여서 배열과 같이 특정 위치에 요소를 추가하는 것과는 개념적으로 다릅니다. 이 메서드는 다음과 같이 정의되어 있습니다:
public E push(E item) {
addElement(item);
return item;
}
public synchronized void addElement(E obj) {
modCount++;
add(obj, elementData, elementCount);
}
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
elementCount = s + 1;
}
스택에 새로운 요소를 추가하는 과정은 다음과 같습니다.
- 스택에 새로운 요소를 추가하려는 요청이 들어오면, 해당 요소를 추가하기 위한 준비가 시작됩니다. 이 요청은 보통
push()메서드를 통해 이루어집니다. - 요소를 추가하기 전에, 스택의 구조적 변경 사항이 기록됩니다. 이는 스택의 일관성을 유지하기 위한 중요한 단계입니다.
- 스택은 내부적으로 배열을 사용하여 요소를 저장합니다. 새로운 요소는 이 배열의 끝에 추가됩니다. 만약 내부 배열이 꽉 찼다면, 배열의 크기를 동적으로 확장하여 더 많은 요소를 저장할 수 있도록 합니다.
- 마지막으로, 새로운 요소가 추가되면, 스택의 요소 개수를 나타내는 값이 증가합니다. 이를 통해 현재 스택에 몇 개의 요소가 있는지 정확하게 추적할 수 있습니다.
이제 push(E item) 메서드를 활용한 예제를 살펴보겠습니다:
import java.util.Stack;
public class StackPush {
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println("Stack after pushes: " + stack);
}
}
위 코드는 스택에 1, 2, 3을 순서대로 추가합니다. 실행 결과는 다음과 같습니다:
Stack after pushes: [1, 2, 3]
Pop
스택에서 요소를 제거하려면 pop() 메서드를 사용합니다. 이 메서드는 요소를 제거하고, 제거된 요소를 반환합니다. 스택의 특성상, 항상 최상단의 요소를 하나씩 꺼내게 되며, 가장 최근에 추가된 요소가 가장 먼저 제거됩니다. pop() 메서드는 다음과 같이 정의되어 있습니다:
public synchronized E pop() {
E obj;
int len = size();
obj = peek();
removeElementAt(len - 1);
return obj;
}
스택에서 요소를 제거하는 과정은 다음과 같습니다.
- 스택에서 요소를 제거하려는 요청이 들어오면, 해당 요소를 제거하기 위한 준비가 시작됩니다. 이는 보통
pop()메서드를 통해 이루어집니다. - 스택의 맨 위 요소를 확인하기 위해
peek()메서드를 호출합니다.peek()메서드는 스택의 맨 위 요소를 반환하되, 요소를 제거하지는 않습니다. peek()메서드가 반환한 요소를 저장한 후, 스택의 맨 위 요소를 제거합니다. 이는 내부 배열의 마지막 요소를 제거하는 방식으로 이루어집니다.- 마지막으로, 제거된 요소를 반환합니다. 이 과정을 통해 스택의 맨 위 요소가 제거되며, 스택의 LIFO(Last In, First Out) 특성이 유지됩니다.
이제 pop() 메서드를 활용한 예제를 살펴보겠습니다:
import java.util.Stack;
public class StackPop {
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println("Stack before pops: " + stack);
int top = stack.pop();
System.out.println("Popped element: " + top);
System.out.println("Stack after one pop: " + stack);
top = stack.pop();
System.out.println("Popped element: " + top);
System.out.println("Stack after two pops: " + stack);
}
}
위 코드는 스택에 1, 2, 3을 순서대로 추가한 후, 두 번의 pop() 연산을 수행합니다. 실행 결과는 다음과 같습니다:
Stack before pops: [1, 2, 3]
Popped element: 3
Stack after one pop: [1, 2]
Popped element: 2
Stack after two pops: [1]
Peek
스택의 맨 위에 있는 요소를 제거하지 않고 확인하려면 peek() 메서드를 사용합니다. 이 메서드는 스택의 최상단 요소를 확인할 수 있게 해주며, 스택의 상태를 변경하지 않습니다. peek() 메서드는 다음과 같이 정의되어 있습니다:
public synchronized E peek() {
int len = size();
if (len == 0)
throw new EmptyStackException();
return elementAt(len - 1);
}
스택에서 요소를 검색하는 과정은 다음과 같습니다.
- 스택의 맨 위 요소를 확인하려는 요청이 들어오면,
peek()메서드를 호출하여 해당 요소를 확인합니다. - 먼저, 스택의 크기를 확인합니다. 만약 스택이 비어있다면,
EmptyStackException을 발생시킵니다. - 스택이 비어있지 않다면, 내부 배열의 마지막 요소, 즉 스택의 최상단 요소를 반환합니다. 이 과정에서 요소를 제거하지는 않습니다.
이제 peek() 메서드를 활용한 예제를 살펴보겠습니다:
import java.util.Stack;
public class StackPeek {
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println("Stack: " + stack);
int top = stack.peek();
System.out.println("Top element: " + top);
System.out.println("Stack after peek: " + stack);
}
}
위 코드는 스택에 1, 2, 3을 순서대로 추가한 후, peek() 연산을 수행합니다. 실행 결과는 다음과 같습니다:
Stack: [1, 2, 3]
Top element: 3
Stack after peek: [1, 2, 3]
Queues
큐(Queue)는 선입선출(FIFO, First In First Out) 원칙에 따라 동작하는 자료구조입니다. 가장 먼저 추가된 요소가 가장 먼저 나갑니다. 이는 컴퓨터 과학과 다양한 시스템에서 중요한 역할을 하며, 특히 운영체제의 작업 스케줄링, 프린터 스풀링, 네트워크 패킷 처리 등 순차적으로 작업을 처리해야 하는 상황에 필수적입니다.
큐는 배열 기반과 링크드 리스트 기반으로 구현될 수 있습니다. Java에서는 java.util.Queue 인터페이스와 이를 구현한 여러 클래스를 통해 큐를 사용할 수 있습니다.
package java.util;
public interface Queue<E> extends Collection<E> {
/**
* Inserts the specified element into this queue if it is possible to do so
* immediately without violating capacity restrictions, returning
* {@code true} upon success and throwing an {@code IllegalStateException}
* if no space is currently available.
*
* @param e the element to add
* @return {@code true} (as specified by {@link Collection#add})
* @throws IllegalStateException if the element cannot be added at this
* time due to capacity restrictions
* @throws ClassCastException if the class of the specified element
* prevents it from being added to this queue
* @throws NullPointerException if the specified element is null and
* this queue does not permit null elements
* @throws IllegalArgumentException if some property of this element
* prevents it from being added to this queue
*/
boolean add(E e);
/**
* Inserts the specified element into this queue if it is possible to do
* so immediately without violating capacity restrictions.
* When using a capacity-restricted queue, this method is generally
* preferable to {@link #add}, which can fail to insert an element only
* by throwing an exception.
*
* @param e the element to add
* @return {@code true} if the element was added to this queue, else
* {@code false}
* @throws ClassCastException if the class of the specified element
* prevents it from being added to this queue
* @throws NullPointerException if the specified element is null and
* this queue does not permit null elements
* @throws IllegalArgumentException if some property of this element
* prevents it from being added to this queue
*/
boolean offer(E e);
/**
* Retrieves and removes the head of this queue. This method differs
* from {@link #poll() poll()} only in that it throws an exception if
* this queue is empty.
*
* @return the head of this queue
* @throws NoSuchElementException if this queue is empty
*/
E remove();
/**
* Retrieves and removes the head of this queue,
* or returns {@code null} if this queue is empty.
*
* @return the head of this queue, or {@code null} if this queue is empty
*/
E poll();
/**
* Retrieves, but does not remove, the head of this queue. This method
* differs from {@link #peek peek} only in that it throws an exception
* if this queue is empty.
*
* @return the head of this queue
* @throws NoSuchElementException if this queue is empty
*/
E element();
/**
* Retrieves, but does not remove, the head of this queue,
* or returns {@code null} if this queue is empty.
*
* @return the head of this queue, or {@code null} if this queue is empty
*/
E peek();
}
Enqueue
큐에 새로운 요소를 추가하는 연산을 Enqueue라고 합니다. Java에서는 Queue 인터페이스의 offer() 메서드를 사용하여 이 연산을 수행합니다. offer() 메서드는 큐의 끝에 새로운 요소를 추가하는 역할을 합니다. 내부적으로 큐는 배열이나 링크드 리스트로 구현될 수 있지만, Enqueue 연산은 큐의 개념에 맞게 항상 자료구조의 맨 마지막에 요소를 추가하는 방식으로 이루어집니다.
Java의 LinkedList 클래스의 offer() 구현부를 살펴보면 내부적으로 add() 함수를 호출하여 리스트의 마지막에 새로운 노드를 추가하는 것을 확인할 수 있습니다.
/**
* Adds the specified element as the tail (last element) of this list.
*
* @param e the element to add
* @return {@code true} (as specified by {@link Queue#offer})
* @since 1.5
*/
public boolean offer(E e) {
return add(e);
}
/**
* Appends the specified element to the end of this list.
*
* <p>This method is equivalent to {@link #addLast}.
*
* @param e element to be appended to this list
* @return {@code true} (as specified by {@link Collection#add})
*/
public boolean add(E e) {
linkLast(e);
return true;
}
큐에 새로운 요소를 추가하는 과정은 다음과 같습니다:
- 새로운 요소가 큐에 추가될 준비를 합니다. 이는
offer()메서드를 통해 이루어집니다. - 큐에 새로운 요소를 추가할 수 있는 공간이 있는지 확인합니다. 배열 기반 큐의 경우, 배열이 꽉 찼다면 배열의 크기를 동적으로 확장합니다.
- 새로운 요소를 큐의 끝에 추가합니다. 링크드 리스트 기반 큐의 경우, 새로운 노드를 생성하여 리스트의 끝에 연결합니다.
- 큐의 상태를 갱신합니다. 요소의 개수를 증가시키고, 새로운 요소가 추가된 위치를 갱신합니다.
큐에 새로운 요소를 다음과 같이 추가할 수 있습니다:
import java.util.LinkedList;
import java.util.Queue;
public class QueueOffer {
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
System.out.println("Queue after offers: " + queue);
}
}
위 코드는 큐에 1, 2, 3을 순서대로 추가합니다. 실행 결과는 다음과 같습니다:
Queue after offers: [1, 2, 3]
Dequeue
큐에서 요소를 제거하는 연산을 Dequeue라고 합니다. Java에서는 Queue 인터페이스의 poll() 메서드를 사용하여 이 연산을 수행합니다. poll() 메서드는 큐의 앞에서 요소를 제거하고 반환하는 역할을 합니다. 만약 큐가 비어있는 경우, poll() 메서드는 null을 반환합니다.
Java의 LinkedList 클래스의 poll() 구현부를 살펴보면 내부적으로 unlinkFirst() 함수를 호출하여 리스트의 첫 번째 노드를 제거하는 것을 확인할 수 있습니다.
/**
* Retrieves and removes the head (first element) of this list.
*
* @return the head of this list, or {@code null} if this list is empty
* @since 1.5
*/
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
/**
* Unlinks non-null first node f.
*/
private E unlinkFirst(Node<E> f) {
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
큐에서 요소를 제거하는 과정은 다음과 같습니다:
- 큐가 비어있는지 확인합니다. 비어있다면
null을 반환하거나 예외를 던집니다. - 큐의 맨 앞 요소를 제거할 준비를 합니다. 이는
poll()메서드를 통해 이루어집니다. - 큐의 맨 앞 요소를 제거하고 반환합니다. 배열 기반 큐의 경우, 맨 앞 요소를 제거하고 나머지 요소들을 앞으로 한 칸씩 이동시킵니다. 링크드 리스트 기반 큐의 경우, 맨 앞 노드를 제거하고, 두 번째 노드를 새로운 맨 앞 노드로 설정합니다.
- 큐의 상태를 갱신합니다. 요소의 개수를 감소시키고, 새로운 맨 앞 요소의 위치를 갱신합니다.
다음과 같이 큐에서 첫 번째 요소를 제거하고 반환할 수 있습니다:
import java.util.LinkedList;
import java.util.Queue;
public class QueuePoll {
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
System.out.println("Queue before poll: " + queue);
int dequeuedElement = queue.poll();
System.out.println("Dequeued element: " + dequeuedElement);
System.out.println("Queue after poll: " + queue);
}
}
위 코드는 큐에서 첫 번째 요소를 제거합니다. 실행 결과는 다음과 같습니다:
Queue before poll: [1, 2, 3]
Dequeued element: 1
Queue after poll:
[2, 3]
Peek
큐의 앞에 있는 요소를 제거하지 않고 확인하려면 peek() 메서드를 사용합니다. 큐가 비어있는 경우 null을 반환할 수 있습니다.
Java의 LinkedList 클래스의 peek() 구현부를 살펴보면 리스트의 첫 번째 노드를 반환하는 것을 확인할 수 있습니다.
/**
* Retrieves, but does not remove, the head (first element) of this list.
*
* @return the head of this list, or {@code null} if this list is empty
* @since 1.5
*/
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
큐의 맨 앞 요소를 확인하는 과정은 다음과 같습니다:
- 큐가 비어있는지 확인합니다. 비어있다면
null을 반환하거나 예외를 던집니다. - 큐의 맨 앞 요소를 조회할 준비를 합니다. 이는
peek()메서드를 통해 이루어집니다. - 큐의 맨 앞 요소를 제거하지 않고 반환합니다. 이를 통해 큐의 상태를 변경하지 않고도 맨 앞 요소를 확인할 수 있습니다.
이 메서드를 활용하여 다음과 같이 큐의 첫 번째 요소를 확인할 수 있습니다:
import java.util.LinkedList;
import java.util.Queue;
public class QueuePeek {
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
System.out.println("Queue: " + queue);
int frontElement = queue.peek();
System.out.println("Front element: " + frontElement);
System.out.println("Queue after peek: " + queue);
}
}
위 코드는 큐의 앞에 있는 요소를 조회합니다. 실행 결과는 다음과 같습니다:
Queue: [1, 2, 3]
Front element: 1
Queue after peek: [1, 2, 3]
Non-linear Data Structures
비선형 자료구조(Non-linear Data Structure)는 트리나 그래프와 같이 데이터 요소가 계층적 또는 네트워크 형태로 연결된 구조를 말합니다. 이러한 자료구조는 복잡한 관계를 표현하거나 데이터 간의 다양한 연결 상태를 나타내는 데 적합합니다.
Trees
트리(Tree)는 계층적으로 데이터를 조직하는 구조로, 루트 노드에서 시작하여 자식 노드로 분기됩니다. 트리의 주요 특징은 계층적 구조로 데이터를 명확하게 정리하고 탐색할 수 있다는 점입니다. 이로 인해 데이터의 상위 및 하위 관계를 명확하게 표현할 수 있습니다.
트리의 주요 이점 중 하나는 빠른 탐색입니다. 트리 구조는 데이터의 삽입, 삭제, 검색을 효율적으로 수행할 수 있습니다. 평균적으로 탐색, 삽입, 삭제 모두 O(log n)의 시간 복잡도를 가지며, 이는 데이터가 정렬된 배열보다 효율적입니다. 또한, 트리는 계층적 데이터를 시각적으로 명확하게 표현할 수 있어, 데이터의 구조적 관계를 이해하고 관리하는 데 유용합니다.
트리 구조는 다양한 응용 분야에서 중요한 역할을 하며, 데이터베이스 인덱스, 파일 시스템 구조, HTML DOM, 조직 구조, 네트워크 라우팅, 게임 개발 등에서 널리 사용됩니다. 트리의 계층적 특성 덕분에 복잡한 데이터 구조를 간단하고 효율적으로 관리할 수 있습니다.
트리 구조의 기본 구성은 다음과 같습니다:
- Node: 노드는 트리의 각 요소를 말하며, 데이터와 다른 노드로의 링크를 포함합니다.
- Root Node: 루트 노드는 트리의 시작점인 노드로, 부모 노드가 없습니다.
- Parent Node: 부모 노드는 하나 이상의 자식 노드를 가지는 노드입니다.
- Child Node: 자식 노드는 부모 노드를 가지는 노드입니다.
- Leaf Node: 리프 노드는 자식 노드가 없는 노드로, 트리의 끝을 나타냅니다.
- Sibling Node: 형제 노드는 같은 부모를 가지는 노드들입니다.
- Height: 높이는 트리의 최대 깊이를 나타내며, 루트 노드부터 리프 노드까지의 가장 긴 경로입니다.
- Depth: 깊이는 루트 노드부터 특정 노드까지의 거리입니다.
트리 자료 구조는 이진 트리(Binary Tree), 이진 탐색 트리(BST, Binary Search Tree), B-트리(B-Tree), 힙(Heap) 등 여러 가지 형태로 확장될 수 있습니다. 이진 검색 트리는 각 노드의 왼쪽 자식 노드가 부모 노드보다 작고, 오른쪽 자식 노드가 부모 노드보다 큰 구조를 가지며, 여러 트리 자료 구조의 기초가 됩니다. 여기서는 이진 탐색 트리를 중심으로 살펴보겠습니다.
Adding Nodes into Trees
이진 탐색 트리에 노드를 추가하는 과정은 트리의 규칙을 준수하며 새 노드를 적절한 위치에 삽입하는 것입니다. Java는 이진 탐색 트리에 대응하기 위해 TreeSet을 제공합니다. TreeSet은 내부적으로 이진 탐색 트리의 한계를 개선한 레드-블랙 트리(Red-Black Tree) 구조를 사용하여 정렬된 집합을 유지합니다. 레드-블랙 트리는 자가 균형 이진 탐색 트리로, 노드 삽입 및 삭제 시 트리의 균형을 자동으로 유지하여 성능을 최적화합니다.
노드를 삽입하는 첫 단계는 값을 가지는 새 노드를 생성하는 것입니다. 그 다음, 트리의 루트 노드에서 시작하여 삽입할 값을 비교합니다. TreeSet은 첫 번째로 추가되는 값을 루트 노드로 설정합니다. 이후, 삽입할 값이 현재 노드의 값보다 작으면 왼쪽 자식 노드로, 크면 오른쪽 자식 노드로 이동합니다. 이를 통해 새로운 노드는 적절한 위치에 배치됩니다.
package java.util;
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable
{
/**
* The backing map.
*/
private transient NavigableMap<E,Object> m;
/**
* Returns {@code true} if this set contains the specified element.
* More formally, returns {@code true} if and only if this set
* contains an element {@code e} such that
* {@code Objects.equals(o, e)}.
*
* @param o object to be checked for containment in this set
* @return {@code true} if this set contains the specified element
* @throws ClassCastException if the specified object cannot be compared
* with the elements currently in the set
* @throws NullPointerException if the specified element is null
* and this set uses natural ordering, or its comparator
* does not permit null elements
*/
public boolean contains(Object o) {
return m.containsKey(o);
}
/**
* Adds the specified element to this set if it is not already present.
* More formally, adds the specified element {@code e} to this set if
* the set contains no element {@code e2} such that
* {@code Objects.equals(e, e2)}.
* If this set already contains the element, the call leaves the set
* unchanged and returns {@code false}.
*
* @param e element to be added to this set
* @return {@code true} if this set did not already contain the specified
* element
* @throws ClassCastException if the specified object cannot be compared
* with the elements currently in this set
* @throws NullPointerException if the specified element is null
* and this set uses natural ordering, or its comparator
* does not permit null elements
*/
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
/**
* Removes the specified element from this set if it is present.
* More formally, removes an element {@code e} such that
* {@code Objects.equals(o, e)},
* if this set contains such an element. Returns {@code true} if
* this set contained the element (or equivalently, if this set
* changed as a result of the call). (This set will not contain the
* element once the call returns.)
*
* @param o object to be removed from this set, if present
* @return {@code true} if this set contained the specified element
* @throws ClassCastException if the specified object cannot be compared
* with the elements currently in this set
* @throws NullPointerException if the specified element is null
* and this set uses natural ordering, or its comparator
* does not permit null elements
*/
public boolean remove(Object o) {
return m.remove(o)==PRESENT;
}
...
}
이진 탐색 트리에 새로운 노드가 추가되는 과정을 통해 트리 구조의 기본 동작 원리를 살펴보겠습니다:
- 먼저, 새로운 트리에 노드 27을 추가하면 루트 노드가 됩니다. 루트 노드가 설정된 후, 노드 17을 추가하면 27보다 작기 때문에 왼쪽 자식 노드로 배치됩니다.
- 다음으로, 노드 35를 추가하면 27보다 크므로 오른쪽 자식 노드로 배치됩니다.
- 그리고, 노드 23을 추가하게 되면, 이는 27보다 작고 17보다 크기 때문에 17의 오른쪽 자식 노드로 배치됩니다.
- 이어서, 노드 5를 추가하면, 17의 왼쪽 자식 노드로 배치됩니다.
- 마지막으로, 노드 39를 추가하면 이는 35보다 크기 때문에 오른쪽 자식 노드로 배치됩니다.
이러한 과정을 통해 TreeSet을 사용하여 이진 탐색 트리에 노드를 효율적으로 추가할 수 있습니다.
import java.util.TreeSet;
public class TreeSetNodeAddition {
public static void main(String[] args) {
TreeSet<Integer> treeSet = new TreeSet<>();
treeSet.add(27);
treeSet.add(17);
treeSet.add(35);
treeSet.add(23);
treeSet.add(5);
treeSet.add(39);
System.out.println("TreeSet elements: " + treeSet);
System.out.println("First element: " + treeSet.first());
System.out.println("Last element: " + treeSet.last());
}
}
TreeSet은 내부적으로 레드-블랙 트리를 활용하기 때문에, 실제로는 이미지와 다르게 노드들이 재배치되어 균형을 유지하도록 설계되어 있습니다. 내부적으로 노드 구조에 접근하는 기능은 제공하지 않으며, 다음과 같이 노드들을 순회하거나 첫 번째와 마지막 노드에 접근하는 기능을 제공합니다:
TreeSet elements: [5, 17, 23, 27, 35, 39]
First element: 5
Last element: 39
Deleting Nodes from Trees
이진 탐색 트리에 노드를 삭제하는 과정은 트리의 규칙을 준수하며, 노드를 적절히 제거하고 트리의 균형을 유지하는 것입니다. 특히 자식 노드가 있는 부모 노드를 삭제하는 과정은 상대적으로 복잡합니다. 이진 탐색 트리에서 자식 노드가 있는 부모 노드를 삭제하는 과정을 살펴보겠습니다.
- 먼저, 삭제할 노드 17을 트리에서 찾습니다. 노드 17은 트리의 루트 노드 27보다 작기 때문에 왼쪽 자식 노드에서 찾습니다.
- 노드 17은 자식 노드 5와 23을 가지고 있습니다. 이 경우 두 자식 노드 중 하나를 선택하여 삭제된 노드의 자리를 대체해야 합니다. 일반적으로 왼쪽 자식 노드 중 가장 큰 값(최대값) 또는 오른쪽 자식 노드 중 가장 작은 값(최소값)을 선택합니다. 여기서는 노드 23이 노드 17의 자리를 대체하게 됩니다.
- 노드 23을 부모 노드 17의 자리를 대체한 다음, 형제 노드였던 노드 5를 자식 노드로 연결합니다.
이 과정을 통해 트리의 균형을 유지하며 노드 삭제가 완료됩니다. 위 프로세스를 Java의 TreeSet을 사용하여 다음과 같이 구현할 수 있습니다:
import java.util.TreeSet;
public class TreeSetNodeDeletion {
public static void main(String[] args) {
TreeSet<Integer> treeSet = new TreeSet<>();
treeSet.add(27);
treeSet.add(17);
treeSet.add(35);
treeSet.add(23);
treeSet.add(5);
treeSet.add(39);
System.out.println("TreeSet elements before deletion: " + treeSet);
treeSet.remove(17);
System.out.println("TreeSet elements after deletion: " + treeSet);
System.out.println("First element: " + treeSet.first());
System.out.println("Last element: " + treeSet.last());
}
}
TreeSet은 내부적으로 레드-블랙 트리 구조를 사용하여 트리의 균형을 유지하고 노드의 삽입과 삭제를 최적화하기 때문에 실제로 위 구조와 다른 구조를 가질 수 있습니다.
출력 결과는 다음과 같습니다:
TreeSet elements before deletion: [5, 17, 23, 27, 35, 39]
TreeSet elements after deletion: [5, 23, 27, 35, 39]
First element: 5
Last element: 39
Searching for Data in Trees
이진 탐색 트리에서 데이터를 검색하는 과정은 트리 구조의 큰 장점 중 하나입니다. 이진 탐색 트리는 데이터를 정렬된 상태로 유지하면서, 검색 시 효율적인 탐색이 가능하도록 설계되었습니다. 트리의 각 노드가 최대 두 개의 자식 노드를 가지며, 특정 값을 찾기 위해 트리를 반으로 나누어 탐색합니다. 이렇게 하면 데이터의 양이 많아지더라도 O(log n)의 시간 복잡도로 빠르게 검색할 수 있습니다. 이는 배열과 비교했을 때 매우 빠른 검색 속도를 제공합니다.
이진 탐색 트리에서 특정 노드를 검색하는 과정은 다음과 같습니다:
- 루트 노드에서 시작하여 검색할 값을 비교합니다.
- 검색할 값이 현재 노드의 값보다 작으면 왼쪽 자식 노드로, 크면 오른쪽 자식 노드로 이동합니다.
- 원하는 값을 찾을 때까지 이 과정을 반복합니다. 마지막 리프 노드에 도달할 때까지 값이 존재하지 않으면 검색을 종료합니다.
예를 들어, 다음과 같은 이진 탐색 트리가 있다고 가정해보겠습니다:
이 트리에서 값 88을 찾는 과정을 살펴보겠습니다:
- 루트 노드 27과 비교합니다. 88은 27보다 크기 때문에 오른쪽 자식 노드로 이동합니다.
- 노드 37과 비교합니다. 88은 37보다 크기 때문에 오른쪽 자식 노드로 이동합니다.
- 노드 45와 비교합니다. 88은 45보다 크기 때문에 오른쪽 자식 노드로 이동합니다.
- 노드 68과 비교합니다. 88은 68보다 크기 때문에 오른쪽 자식 노드로 이동합니다.
- 노드 88을 찾아서 탐색을 종료하고 결과를 반환합니다.
이진 탐색 트리는 16개의 노드 중에서 88을 찾기 위해 총 4번의 비교를 하였습니다. 배열에서는 이를 찾기 위해 최악의 경우 모든 요소를 다 조회해야 합니다. 이는 데이터의 수가 많아질수록 차이가 극명하게 드러납니다. 10만 건의 데이터가 있을 때, 균형 잡힌 트리의 경우 2^17로 트리의 높이인 총 17번 안에 어떤 값을 찾을 수 있지만, 배열은 최악의 경우 10만 번의 값을 비교해야 합니다.
Java의 TreeSet과 ArrayList에서 값을 찾는 시간을 비교해보겠습니다:
import java.util.TreeSet;
import java.util.ArrayList;
import java.util.List;
public class TreeSetSearch {
public static void main(String[] args) {
TreeSet<Integer> treeSet = new TreeSet<>();
ArrayList<Integer> arrayList = new ArrayList<>();
List<Integer> values = List.of(27, 5, 17, 18, 20, 21, 23, 24, 26, 31, 37, 41, 45, 51, 68, 88);
arrayList.addAll(values);
treeSet.addAll(values);
long startTime, endTime;
// For TreeSet
startTime = System.nanoTime();
treeSet.contains(88);
endTime = System.nanoTime();
System.out.println("Execution time in nanoseconds for Tree: " + (endTime - startTime));
// For ArrayList
startTime = System.nanoTime();
arrayList.contains(88);
endTime = System.nanoTime();
System.out.println("Execution time in nanoseconds for List: " + (endTime - startTime));
}
}
동일한 데이터를 지닌 TreeSet과 ArrayList에서 값을 찾는 시간을 비교해보면, 데이터가 많지 않음에도 속도가 큰 차이를 보이는 것을 확인할 수 있습니다. 이는 데이터의 크기가 커질수록 차이가 더 극명하게 될 것입니다.
출력 결과는 다음과 같습니다:
Execution time in nanoseconds for Tree: 2792
Execution time in nanoseconds for List: 5750
Java의 TreeSet은 트리가 한쪽으로 치우치지 않도록 내부적으로 각 노드들을 재정렬하여 균형을 잡아갑니다. 이로 인한 비용이 들지만, 이를 감안하더라도 빠른 검색이 필요한 경우 그만한 가치가 있을 것입니다.
Graphs
그래프는 노드(정점)와 간선(엣지)으로 구성된 자료구조로, 네트워크 구조나 복잡한 관계를 나타내는 데 사용됩니다. 여기서는 그래프의 기본 개념과 다양한 구조에 대해 살펴보겠습니다.
Hash-based Data Structures
해시 기반 자료구조(Hash-based Data Structure)는 해시 함수(Hash Function)를 사용하여 데이터를 저장하고 검색하는 자료구조입니다. 해시 함수는 데이터를 해시 값(Hash Value)으로 변환하여 저장 위치를 결정합니다. 이러한 구조는 매우 빠른 검색 속도를 제공하며, 데이터베이스 인덱싱, 캐싱 시스템, 집합 연산 등 다양한 분야에서 활용됩니다. 대표적인 해시 기반 자료구조로는 해시 테이블, 해시 맵, 해시 셋, 해시 트리 등이 있습니다.
Hash Tables
해시 테이블(Hash Table)은 키(key)와 값(value)의 쌍을 저장하는 데이터 구조로, 데이터를 신속하게 검색할 수 있도록 설계되었습니다. 해시 테이블은 배열이나 링크드 리스트를 기반으로 할 수 있으며, 해시 함수를 이용하여 키를 인덱스로 변환하여 데이터를 저장하고 검색합니다. 이로 인해 평균적으로 O(1)의 시간 복잡도로 검색, 삽입, 삭제 작업을 수행할 수 있습니다.
| 🚥 | Features | Descriptions |
|---|---|---|
| 🟢 | Fast Access | 평균적으로 O(1)의 시간 복잡도로 데이터 접근이 가능합니다. |
| 🟢 | Efficient Memory Usage | 대부분의 경우 해시 테이블은 메모리를 효율적으로 사용합니다. |
| 🚸 | Collision Handling | 충돌이 발생할 수 있으며, 충돌 해결을 위해 추가적인 작업이 필요합니다. |
| 🚸 | Fixed Size Array | 배열의 크기가 고정되어 있어, 데이터가 많아지면 리사이징(Resizing)이 필요할 수 있습니다. |
| 🚸 | Poor Worst-case Performance | 최악의 경우 시간 복잡도가 O(n)으로 증가할 수 있습니다. |
배열과 링크드 리스트는 순차적으로 데이터를 저장하는 반면, 해시 테이블은 키를 해시 함수로 변환하여 인덱스를 생성하고, 해당 인덱스에 값을 매핑합니다. 이러한 구조 덕분에 해시 테이블은 매우 빠른 검색 속도를 제공합니다.
해시 테이블의 주요 구성 요소는 다음과 같습니다:
- 해시 함수 (Hash Function): 키를 입력받아 해시 값을 출력하는 함수로, 이 값은 배열의 인덱스로 사용됩니다. 해시 함수는 키를 고르게 분산시켜 충돌을 최소화하는 것이 중요합니다.
- 해시 값 (Hash Value): 해시 함수에 의해 생성된 정수 값으로, 배열의 인덱스로 변환되어 데이터를 저장하거나 검색하는 데 사용됩니다.
- 버킷 (Bucket): 해시 값에 대응하는 배열의 각 요소를 버킷이라 부르며, 하나 이상의 키-값 쌍을 저장할 수 있습니다.
- 충돌 해결 (Collision Resolution): 서로 다른 키가 동일한 해시 값을 가질 때 발생하는 충돌을 해결하는 방법입니다. 대표적인 방법으로 체이닝(Chaining)과 오픈 어드레싱(Open Addressing)이 있습니다.
이러한 구성 요소를 통해 해시 테이블은 효율적이고 빠른 데이터 저장 및 검색을 가능하게 합니다.
Hash Function
해시 함수(Hash Function)는 키를 정수 인덱스로 변환합니다. 이상적인 해시 함수는 키를 균일하게 분산시켜 충돌 가능성을 최소화합니다. 좋은 해시 함수는 다음 조건들을 만족해야 합니다:
- 충돌 최소화 (Collision Resistance): 동일한 인덱스로 매핑되는 키의 수를 줄여야 합니다.
- 속도 (Efficiency): 해시 함수는 계산이 빠르고 효율적이어야 합니다.
- 균일 분포 (Uniform Distribution): 해시 값이 가능한 한 고르게 분포되어야 합니다.
- 결정적 (Deterministic): 동일한 입력에 대해 항상 동일한 해시 값을 반환해야 합니다.
- 확장성 (Scalability): 다양한 크기의 데이터에 대해 성능이 일관되게 유지되어야 합니다.
주요 해시 함수들은 다음과 같습니다:
- Division Operation: 해시 값에 배열의 크기로 모듈로 연산을 수행합니다. 간단하고 빠르지만 배열의 크기가 소수일 때 충돌 가능성이 줄어듭니다.
- Multiplicative Hashing: 해시 값을 특정 상수와 곱한 후, 소수점 이하의 값을 이용해 인덱스를 생성합니다. 충돌 가능성이 낮으며, 배열 크기에 덜 민감합니다.
- Universal Hashing: 여러 해시 함수 중 하나를 무작위로 선택하여 해시 값을 생성합니다. 충돌을 최소화하기 위해 다양한 해시 함수의 조합을 사용합니다.
- Cryptographic Hash Functions: 보안이 중요한 경우 SHA-256, MD5와 같은 해시 함수가 사용됩니다. 일반적인 해시 테이블에서는 성능상의 이유로 잘 사용되지 않습니다.
Collision Resolution
서로 다른 입력값을 해시 함수로 변환했을 때 동일한 해시 값이 반환되는 경우를 충돌이라고 합니다. 이 충돌을 해결하는 방법에는 대표적으로 분리 체이닝(Separate Chaining)과 오픈 어드레싱(Open Addressing)이 있습니다.
Separate Chaining
체이닝은 각 버킷을 링크드 리스트로 구성하여 충돌을 해결합니다. 동일한 해시 값을 가진 Key-Value 쌍은 해당 버킷의 링크드 리스트에 추가됩니다. 체이닝의 장점은 간단하고 구현이 용이하다는 것입니다. 그러나 링크드 리스트를 사용하므로 추가적인 메모리 공간이 필요하며, 최악의 경우 검색 시간 복잡도가 O(n)이 될 수 있습니다.
다음은 Java에서 Object.hashCode()를 활용하여 체이닝을 구현한 코드입니다.
import java.util.*;
public class ChainingHashSet {
private static final int DEFAULT_CAPACITY = 10;
private List<String>[] buckets;
private int size;
public ChainingHashSet() {
buckets = new LinkedList[DEFAULT_CAPACITY];
for (int i = 0; i < DEFAULT_CAPACITY; i++) {
buckets[i] = new LinkedList<>();
}
size = 0;
}
public boolean add(String value) {
int index = value.hashCode() % buckets.length;
List<String> bucket = buckets[index];
if (!bucket.contains(value)) {
bucket.add(value);
size++;
return true;
}
return false;
}
public boolean contains(String value) {
int index = value.hashCode() % buckets.length;
List<String> bucket = buckets[index];
return bucket.contains(value);
}
public boolean remove(String value) {
int index = value.hashCode() % buckets.length;
List<String> bucket = buckets[index];
if (bucket.remove(value)) {
size--;
return true;
}
return false;
}
public int size() {
return size;
}
public void printBuckets() {
System.out.println("Buckets: " + Arrays.toString(buckets));
}
}
모듈로 연산(Modulo Operation)은 두 숫자를 나눈 후 나머지를 반환하는 연산으로, 해시 값을 배열의 크기 내로 제한하는 데 유용합니다. 이를 통해 배열의 특정 위치에 데이터를 저장할 수 있습니다. 키의 해시 값을 배열의 길이로 나눈 나머지를 인덱스로 사용함으로써, 해시 값을 배열의 인덱스 범위 내로 변환하여 적절한 버킷에 매핑할 수 있습니다. 이를 통해 해시 테이블이 효율적으로 작동할 수 있으며, 배열의 경계를 벗어나지 않도록 보장합니다.
위에서 정의한 ChainingHashSet을 활용하여 충돌이 발생하는 상황을 살펴보겠습니다:
public class SeparateChaining {
public static void main(String[] args) {
ChainingHashSet set = new ChainingHashSet();
set.add("A");
set.add("B");
set.add("C");
set.add("D");
set.add("AB");
set.add("SET");
set.printBuckets();
System.out.println("A.hashCode=" + "A".hashCode());
System.out.println("B.hashCode=" + "B".hashCode());
System.out.println("AB.hashCode=" + "AB".hashCode());
System.out.println("SET.hashCode=" + "SET".hashCode());
System.out.println("bucket.contains(SET) = " + set.contains("SET"));
}
}
문자열 "B"와 "SET"은 동일한 해시 인덱스를 가지면서 충돌이 발생합니다. 하지만 동일한 인덱스의 배열에 순차적으로 쌓이면서 충돌이 해결됩니다. 출력 결과는 다음과 같습니다:
Buckets: [[], [AB], [], [], [], [A], [B, SET], [C], [D], []]
A.hashCode=65
B.hashCode=66
AB.hashCode=2081
SET.hashCode=81986
bucket.contains(SET) = true
해시 인덱스가 충돌하더라도, 각 버킷 내부의 링크드 리스트에 값이 순차적으로 쌓이면서
충돌을 해결할 수 있습니다. 그러나 동일한 인덱스에 너무 많은 데이터가 들어가면 검색 시간이 길어지기 때문에, 충돌이 최대한 발생하지 않도록 해시 함수를 설계하는 것이 중요합니다. 이를 위해 해시 함수의 품질을 높이고, 해시 테이블의 크기를 적절하게 조정하는 것이 필요합니다.
Open Addressing
오픈 어드레싱은 충돌이 발생하면 다른 빈 버킷을 찾아 데이터를 저장하는 방법입니다. 대표적인 오픈 어드레싱 기법으로는 선형 탐사, 이차 탐사, 이중 해싱이 있습니다.
- 선형 탐사(Linear Probing): 충돌이 발생하면 다음 빈 버킷을 순차적으로 찾습니다.
- 이차 탐사(Quadratic Probing): 충돌 시 탐사 간격을 제곱으로 증가시켜 빈 버킷을 찾습니다.
- 이중 해싱(Double Hashing): 두 개의 해시 함수를 사용하여 충돌 시 두 번째 해시 함수를 통해 새로운 인덱스를 계산합니다.
오픈 어드레싱은 추가적인 메모리 사용이 없다는 장점이 있지만, 충돌이 빈번히 발생하면 성능이 저하될 수 있습니다. 또한, 삭제 시 복잡성이 증가하며, 특정 조건에서 무한 루프에 빠질 가능성이 있습니다.
이와 같이 해시 충돌을 해결하는 다양한 방법들은 각각의 장단점이 있으며, 상황에 맞게 적절한 방법을 선택하여 사용해야 합니다.
Utilizing HashMap in Java
Java에서 해시 테이블은 Map<K, V> 인터페이스를 구현한 HashMap을 통해 제공됩니다. HashMap은 빠른 데이터 접근이 필요한 상황에서 매우 유용한 자료구조입니다.
다음은 put(K, V) 메서드를 활용하여 HashMap에 새로운 Key-Value 데이터를 추가하는 방법입니다:
import java.util.HashMap;
public class HashMapPut {
public static void main(String[] args) {
HashMap<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);
map.put("cherry", 3);
System.out.println("Value for key 'apple': " + map.get("apple"));
System.out.println("Value for key 'banana': " + map.get("banana"));
System.out.println("Value for key 'cherry': " + map.get("cherry"));
}
}
put() 메서드는 지정된 키와 값을 HashMap에 추가합니다. 이때, 동일한 키가 이미 존재하면 기존 값이 새로운 값으로 덮어쓰여집니다. 내부적으로 put() 메서드는 키의 해시 값을 계산하고, 이 해시 값을 기반으로 적절한 버킷에 데이터를 저장합니다. get() 메서드는 키를 사용하여 값을 검색하며, 키의 해시 값을 통해 해당 버킷을 찾고, 그 버킷 내에서 키를 비교하여 값을 반환합니다.
Value for key 'apple': 1
Value for key 'banana': 2
Value for key 'cherry': 3
HashMap에서 데이터를 삭제하려면 remove() 메서드를 활용합니다:
import java.util.HashMap;
public class HashMapRemove {
public static void main(String[] args) {
HashMap<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);
map.put("cherry", 3);
System.out.println("prev = " + map);
map.remove("banana");
System.out.println("next = " + map);
System.out.println("Value for key 'banana': " + map.get("banana"));
}
}
remove() 메서드는 지정된 키를 가진 엔트리를 HashMap에서 제거합니다. 내부적으로 remove() 메서드는 먼저 삭제하려는 키의 해시 값을 계산합니다. 그런 다음, 해시 값을 기반으로 해당 키가 저장된 버킷의 위치를 찾습니다. 마지막으로, 버킷 내에서 해당 키를 찾고, 일치하는 키-값 쌍을 제거합니다.
삭제된 키를 사용하여 값을 검색하면 null이 반환됩니다. 이는 삭제된 키가 더 이상 HashMap에 존재하지 않음을 의미합니다.
prev = {banana=2, apple=1, cherry=3}
next = {apple=1, cherry=3}
Value for key 'banana': null
다음은 HashMap에 저장된 모든 키를 조회하는 방법입니다. 이를 위해 keySet() 메서드를 활용합니다:
import java.util.HashMap;
import java.util.Set;
public class HashMapKeySet {
public static void main(String[] args) {
HashMap<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);
map.put("cherry", 3);
Set<String> keys = map.keySet();
for (String key : keys) {
System.out.println("Key: " + key);
}
}
}
keySet() 메서드는 HashMap에 저장된 모든 키를 반환합니다. 반환된 키들은 Set 형태로 제공되며, 각 키는 순서 없이 저장됩니다. 이 메서드를 통해 모든 키를 순회하며 출력할 수 있습니다.
Key: banana
Key: apple
Key: cherry
마지막으로, HashMap의 모든 Key-Value 쌍을 가져오려면 entrySet() 메서드를 사용합니다.
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Set;
public class HashMapEntrySet {
public static void main(String[] args) {
HashMap<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);
map.put("cherry", 3);
Set<Entry<String, Integer>> entries = map.entrySet();
for (Entry<String, Integer> entry : entries) {
System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
}
}
}
해시 테이블에서 Entry는 Key-Value 한 쌍을 의미합니다. entrySet() 메서드는 HashMap에 저장된 모든 엔트리를 Set 형태로 반환합니다. 각 엔트리는 Map.Entry<K, V> 객체로 표현되며, 키와 값에 접근할 수 있는 getKey()와 getValue() 메서드를 제공합니다. 이를 통해 모든 엔트리를 순회하면서 각 키와 값을 출력할 수 있습니다.
위의 출력 결과는 HashMap에 저장된 모든 Key-Value 쌍을 보여줍니다. entrySet() 메서드를 통해 각 엔트리에 접근하여 키와 값을 쉽게 조회할 수 있습니다. 이와 같은 방식으로 HashMap의 모든 데이터를 효율적으로 처리할 수 있습니다.
Key: banana, Value: 2
Key: apple, Value: 1
Key: cherry, Value: 3
해시 기반 자료구조는 실무에서 매우 자주 사용되며, 빠른 데이터 접근이 필요한 상황에서 특히 유용합니다. 예를 들어, 대규모 데이터 집합의 교집합 및 합집합 연산, 유일 값 식별, 중복 제거 등의 작업에서 해시 테이블을 효과적으로 사용하면 성능을 크게 향상시킬 수 있습니다.
- Java
- Architecture
- Algorithm