배열, 리스트 (Java)

배열

- 검색 연산은 빠르지만, 추가/삭제 연산이 느리다

- 추가/삭제 : 새로운 데이터가 입력되거나 중간에서 특정 항목이 삭제될 경우 메모리 상의 주소를 모두 바꿔야 한다.

- 배열의 검색  :  O(1)

- 배열의 수정/삭제  :  O(ͷ)

---

연결 리스트 Linked List

- 배열과 같이 연속된 데이터를 저장하는 자료구조로서 추가/삭제 연산은 빠르지만, 검색이 느리다.

- 아무 메모리에나 저장하고 기존 데이터에 부가 정보로 다음 데이터의 주소를 저장한다.

- 검색  :  5번째 데이터를 찾고 싶다면 처음 주소지에서 다음 데이터의 주소를 찾는데 연산이 4번

- 추가/삭제  :  기존 데이터 구조가 변하지 않고 데이터간의 주소 연결만 수정한다.

- 리스트의 검색  :  O(ͷ)

- 리스트의 추가/삭제  :  O(1)

 

검색 연산 추가 연산

 

---

기능	Array	List
생성	ex)  String[] arr = new String[5];	ex)  List<String> list = new ArrayList<>();
길이 확인	arr.length	list.size()
값 추가	❌ (크기 고정)	list.add("A")
값 삽입	❌	list.add(1, "A")
값 조회	arr[i]	list.get(i)
값 수정	arr[i] = "A"	list.set(i, "A")
값 삭제	❌	list.remove(i) or list.remove("A")
포함 여부 확인	Arrays.asList(arr).contains("A")	list.contains("A")
정렬	Arrays.sort(arr)	Collections.sort(list)
복사	Arrays.copyOf(arr, n)	new ArrayList<>(list)
문자열 출력	Arrays.toString(arr)	list.toString()
비었는지 확인	arr.length == 0	list.isEmpty()
전체 삭제	❌	list.clear()
인덱스 조회	Arrays.asList(arr).indexOf("A")	list.indexOf("A")
마지막 인덱스 조회	Arrays.asList(arr).lastIndexOf("A")	list.lastIndexOf("A")
배열 → 리스트 변환	Arrays.asList(arr)	—
리스트 → 배열 변환	—	list.toArray(new String[0])

---

---

	ArrayList	Vector	LinkedList
내부 구조	동적 배열 (Dynamic Array)	동적 배열 (Dynamic Array)	이중 연결 리스트 (Doubly Linked List)
동기화	❌ (비동기)	✅ (자동 동기화)	❌ (비동기)
성능	빠름 (단일 스레드 환경에 적합)	느림 (동기화 오버헤드 존재)	삽입/삭제는 빠름 탐색은 느림
삽입/삭제	느림 (중간 삽입/삭제 시 이동 필요)	느림	빠름 (노드 연결만 조작)
조회 성능	빠름 (인덱스 기반 접근)	빠름	느림 (순차 접근 필요)
메모리 사용	상대적으로 적음	상대적으로 적음	상대적으로 많음 (노드 + 포인터)
멀티스레드 환경	직접 Collections.synchronizedList() 사용	자체적으로 동기화	직접 동기화 필요
사용 시점 요약	일반적인 리스트 사용 시 가장 많이 사용	멀티스레드 환경에서 안전하게 사용할 때	삽입/삭제가 빈번한 경우에 적합

 

 

 

---

refer to

메가아이티아카데미 이광호쌤