# 자바 자료구조, 알고리즘 구현 어떤걸 써야 할까?

## 자료구조 별 시간 복잡도

### 리스트 구현체

* ArrayList
* LinkedList

{% hint style="info" %}
일반적으로는 리스트 자료구조는 [삽입 (끝/중간), 삭제 (끝/중간)](#user-content-fn-1)[^1] 와 조회로 구분되고, 

구현체의 성능은 조회는 ArrayList (랜덤 접근이 가능하므로), 삽입 삭제는 LinkedList (링크의 연결 만 변경하면 되므로) 가 더 유리하다고 생각한다. 실제로 그럴까?
{% endhint %}

#### 상황별 사용

어떤 자료, 어떤 연산이 빈번하다면 이 구현체를 쓰자 (예시)

### 맵 구현체

* HashMap
* LinkedHashMap

### 데크 구현체

* ArrayDeque
* LinkedList

## 알고리즘 별 시간 복잡도

### 최대값 구하기

#### 1. 반복문 <a href="#id-1" id="id-1"></a>

O(n), 배열의 값을 하나씩 비교

```java
int[] arr = { 1, 2, 3, 4, 5 };
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
        max = arr[i];
    }
}
```

#### 2. Stream() <a href="#id-3-stream" id="id-3-stream"></a>

O(n), 내부 반복자와 프로퍼티로 값을 하나씩 비교 (동작 원리는 for 와 동일, Stream 객체를 이용한다는 점이 다름)&#x20;

```java
int[] arr = { 1, 2, 3, 4, 5 };
int max = Arrays.stream(arr).max().getAsInt();
```

#### 3. parallelStream() <a href="#id-4-parallelstream" id="id-4-parallelstream"></a>

O(log n), 병렬 스트림 처리, 배열의 크기가 작을 때는 오히려 느릴 수 있음 (크기 기준은 ??)

```java
int[] arr = { 1, 2, 3, 4, 5 };
int max = Arrays.parallelStream(arr).max().getAsInt();
```

#### 4. 정렬 <a href="#id-2-arrays-sort" id="id-2-arrays-sort"></a>

O(nlogn), 오름차순 정렬시킨 배열의 마지막 요소를 최대값으로 설정

```java
int[] arr = { 1, 2, 3, 4, 5 };
Arrays.sort(arr);
int max = arr[arr.length - 1];
```

[^1]: 삽입과 삭제도 좀 더 생각하면 인덱스의 끝과 중간으로 구분하여 생각할 수 있다.

    * 끝 : O(1)
    * 중간 : 탐색 O(n), 동작 O(1)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://programmer-jjy.gitbook.io/second-brain/technical/technical-curiosity/time-complexity.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.