📌 Array, ArrayList, LinkedList 정리

1. Array (배열)

정의 : 배열은 고정된 크기의 연속적인 메모리 영역에 동일한 타입의 데이터를 저장하는 자료 구조다.

장점:

• 빠른 접근: 인덱스를 사용하여 데이터에 빠르게 접근한다. (O(1)의 시간 복잡도)
• 메모리 사용이 효율적이다.

단점:

• 고정된 크기: 크기가 미리 정해져 있어서, 크기를 늘리거나 줄이기가 어렵다.
• 데이터 삽입/삭제의 비효율성: 중간에 데이터를 삽입하거나 삭제할 때, 데이터의 이동이 필요하여 O(n)의 시간이 걸린다.

2. ArrayList (동적 배열)

정의: ArrayList는 내부적으로 배열을 사용하여 데이터를 저장하는 동적 배열이다. 크기를 자동으로 늘리거나 줄일 수 있다.

장점:

• 동적 크기 조정: 배열의 크기를 동적으로 늘리거나 줄일 수 있다.
• 인덱스를 사용하여 데이터에 빠르게 접근한다. (O(1)의 시간 복잡도)

단점:

• 배열의 크기를 늘릴 때(즉, 용량이 부족할 때) 새로운 배열을 만들고 기존의 데이터를 복사해야 하는 비용이 발생한다.
• 중간에 데이터를 삽입하거나 삭제할 때, 데이터의 이동이 필요하여 O(n)의 시간이 걸린다.

3. LinkedList (연결 리스트)

정의: LinkedList는 노드들이 포인터로 연결된, 연속적이지 않은 메모리 영역에 데이터를 저장하는 자료 구조다. 각 노드는 데이터와 다음 노드를 가리키는 포인터로 구성되어 있다.

장점:

• 동적 크기 조정: 연결 리스트의 크기는 동적으로 늘리거나 줄일 수 있다.
• 데이터 삽입/삭제의 효율성: 특정 노드의 참조 정보만 변경하면 되므로 O(1)의 시간에 삽입이나 삭제가 가능하다. 그러나, 삽입/삭제 위치를 찾기 위해서는 O(n)의 시간이 걸릴 수 있다.

단점:

• 연속적이지 않은 메모리 공간에 데이터를 저장하기 때문에 메모리 사용이 비효율적일 수 있다.
• 인덱스로 데이터에 접근하려면 처음부터 노드를 순차적으로 탐색해야 하므로 접근 속도가 느리다. (O(n)의 시간 복잡도)

📌 정리

사용하는 환경이나 필요한 연산의 종류에 따라 적절한 자료 구조를 선택하는 것이 중요하다. 데이터의 삽입과 삭제가 자주 일어나면 LinkedList를, 빠른 접근이 중요하다면 Array나 ArrayList를 선택하는 것이 좋다.