자료구조 기초 정리 (배열, 리스트 , Set , Map 예시 - java )

2025년 4월 3일

자바 자료구조 공부

자료구조 기초 정리

1. 배열 (Array)

배열은 동일한 자료형의 데이터를 연속된 메모리 공간에 저장하는 선형 자료구조로, 인덱스를 기반으로 한 임의 접근(random access)이 가능하다. Java에서 배열은 선언 시 고정된 크기를 가지며, 이후 크기를 변경할 수 없다. 배열은 인덱스를 이용한 조회 연산에서 시간 복잡도 O(1)의 효율을 가지며, 삽입 또는 삭제 시 전체 데이터를 이동해야 하므로 O(n)의 시간 복잡도를 갖는다.

ex)

 

int[] arr = new int[5];

arr[0] = 10;

 

배열은 메모리상 연속된 공간을 점유하므로 CPU 캐시 효율이 높고, 인덱스를 통한 접근이 매우 빠르다. 그러나 삽입과 삭제 연산이 잦은 경우에는 성능상의 단점이 존재한다.

---

2. 리스트 (List) – ArrayList

ArrayList는 Java에서 제공하는 가변 크기 배열로, 내부적으로 배열을 사용하여 데이터를 저장한다. 크기 제한이 있는 일반 배열과 달리, 필요에 따라 자동으로 크기를 증가시키는 동적 배열 구조를 가진다. 일반적으로 요소 추가 시 평균적으로 O(1)의 시간복잡도를 가지며, 크기 초과 시 내부 배열 복사가 발생하여 O(n)의 오버헤드가 발생할 수 있다.

 

ex)

 

List<String> list = new ArrayList<>();

list.add("A");

list.get(0); // O(1)

 

 

ArrayList는 인덱스를 통한 조회가 가능하며, 중간 삽입 및 삭제에는 데이터 이동이 수반되어 성능이 떨어진다. 따라서 빈번한 조회 및 순차적인 데이터 처리에 적합하며, 메모리 공간이 연속적으로 확보되어야 하므로 공간 효율성도 고려 대상이다.

---

3. 연결 리스트 (LinkedList)

LinkedList는 각 노드가 데이터와 다음 노드를 가리키는 포인터를 포함하는 비연속적인 메모리 구조를 갖는 자료구조이다. Java의 LinkedList 클래스는 이중 연결 리스트(doubly linked list)로 구현되어 있으며, 각 노드는 이전 노드와 다음 노드에 대한 참조를 포함한다.

ex)

 

LinkedList<String> linkedList = new LinkedList<>();

linkedList.addFirst("A");

linkedList.addLast("B");

 

LinkedList는 중간 삽입과 삭제가 빠르며, 포인터 조작만으로 처리 가능하므로 시간 복잡도는 O(1)이다. 하지만 인덱스를 통한 접근은 첫 노드부터 순차적으로 탐색해야 하므로 O(n)의 시간이 소요된다. 따라서 인덱스 기반 접근보다는 삽입/삭제 중심의 큐 또는 덱(deque) 구조에 적합하다.

 

 

---

 

 

4. 탐색 방식 차이 – ArrayList vs LinkedList

ArrayList는 배열 기반으로 인덱스를 통한 직접 접근이 가능하여 조회 속도가 빠르다. 반면, LinkedList는 포인터 체인을 따라 탐색하기 때문에 인덱스 기반 접근은 비효율적이며, 앞에서부터 차례대로 노드를 따라가야 한다. 따라서 순차적 탐색이 필요한 경우에는 ArrayList가, 빈번한 삽입/삭제가 필요한 경우에는 LinkedList가 더 적합하다.

 

5. ArrayList vs LinkedList 비교

항목ArrayList , LinkedList

내부 구조	배열	노드 + 포인터
인덱스 접근 속도	O(1)	O(n)
삽입/삭제 (중간)	O(n) (데이터 이동 필요)	O(1) (포인터 바꾸기 ,  (노드 위치 알고 있을 경우) )
메모리 효율	높음 (연속 메모리)	낮음 (포인터 저장 추가)
적절 사용 사항	배열 같은 값 많이 필요, 조회 중심, 인덱스 접근	반복되는 삽입/삭제 필요

6. 메모리 구조 차이

ArrayList는 배열 구조이며, 메모리사이의 값이 연속되어야 한다. 따라 가장 중간에 삽입 또는 삭제가 일어나면, 이후에 있는 항목들을 무엇이든 이동시켜야 한다.

LinkedList는 노드를 구성하는 목록으로, 각 노드가 다음 노드를 가리키는 참조(next 포인터)를 가진다. 각 노드는 각각 다른 메모리 공간에 저장되기 때문에, 연속적이지 않은 메모리 공간에 도 저장 가능하며, 필요 시 포인터 조작만으로 다음 또는 이전 노드로 가리키는 것이 가능하다.

이렇기 때문에, 반복되는 삽입 또는 삭제가 발생하는 경우에는 ArrayList보다는 LinkedList가 시간 효율적이며, 연속 구조의 메모리 가방성이 높은 ArrayList는 접근 통계가 많고 수행 데이터 관리에 적합하다.

 

7 Set 및 Map

Set

Set은 중복을 허용하지 않는 집합 구조로, Java에서는 HashSet, LinkedHashSet, TreeSet 등의 구현체가 제공된다. HashSet은 내부적으로 해시 테이블을 사용하며, 요소의 중복 여부는 해시 함수를 기반으로 판단된다. Set은 일반적으로 탐색, 삽입, 삭제에 평균적으로 O(1)의 시간 복잡도를 가진다. 단, 순서가 보장되지 않는다는 특성이 있으며, LinkedHashSet을 사용하면 삽입 순서를 유지할 수 있다.

ex)

Set<String> set = new HashSet<>();

set.add("A"); // 중복 불가

Map

Map은 Key-Value 쌍의 자료를 저장하는 구조로, Key를 기준으로 값을 빠르게 조회할 수 있다. Java의 대표적인 구현체는 HashMap, LinkedHashMap, TreeMap 등이 있으며, 그 중 HashMap은 해시 테이블 기반으로 평균 O(1)의 조회 및 삽입 성능을 제공한다.

ex)

Map<String, String> map = new HashMap<>();

map.put("id", "user1");

map.get("id"); // "user1"

 

중복 키가 있는 경우에는 Map<K, List<V>>와 같은 구조를 사용하여 다대일(N:1) 매핑이 아닌 일대다(1:N) 매핑을 구현할 수 있다.

 

 

---

이상으로 배열, ArrayList, LinkedList, Set, Map에 대한 기초적인 자료구조 개념 및 비교 정리를 마친다.

각 자료구조는 특정한 목적과 상황에 따라 적합성이 다르므로, 실제 사용 시에는 데이터의 크기, 접근/수정 빈도, 메모리 사용량 등을 종합적으로 고려하여 선택해야 한다.

 

@잘못된 점 혹은 부족한 점 댓글 주시면 감사하겠습니다 :)