카테고리 없음

자바 공부#2_01. List

코딩연습중 2025. 3. 30. 17:35

 

List?

List는 배열의 한계로 만들어진 자료형이다. 배열은 크기가 정해져 있지만, 프로그래밍을 하다 보면 크기를 알 수 없는 상황이 발생한다. 이  경우, List 를 사용하면 동적으로 자료형의 개수를 늘릴 수 있다. 리스트는 배열과 같이 객체를 일렬로 늘어놓은 구조를 갖는다. 객체를 index로 관리하기 때문에 객체를 저장하면 자동으로 인덱스가 부여되고, 인덱스를 기준으로 객체를 검색, 추가, 삭제할 수 있는 등의 기능을 제공한다.

List  특징

  1. 순서 존재
  2. 중복 허용
  3. 인덱스로 관리. -> 인덱스로 접근 가능

List 인터페이스를 구현한 대표적인 클래스에는 ArrayList, LinkedList, Vector가 있으며, Stack은 Vector를 상속받아 스택 구조(LIFO)를 지원하는 클래스이다.

 

1. ArrayList

ArrayList는 내부적으로 배열을 사용하여 요소를 저장하며, 동적으로 크기가 조절된다. 랜덤 액세스(인덱스를 통한 요소 접근)가 빠르지만, 중간에 요소를 추가 또는 제거할 때는 비효율적일 수 있다.

특징

  • 연속적인 데이터의 리스트(데이터는 연속적으로 리스트에 들어있어야 함. 중간에 빈공간 있으면 안됨)
  • 내부적으로 Object[] 배열을 이용해 요소 저장
  • 인덱스 이용해 요소에 빠르게 접근 가능
  • 배열과 다르게 데이터 적재량에 따라 가변적으로 공간을 늘리거나 줄임
  • 그러나 배열 공간이 꽉 찰 때 마다 배열을 copy하는 방식으로 공간을 늘리므로 이 과정에서 지연 발생
  • 데이터를 중간에 삽입/삭제할 경우, 요소들의 위치를 앞뒤로 자동으로 이동시키기 때문에 삽입/삭제가 느림

따라서 조회를 많이 하는 경우에 사용하는 것이 좋다.

 

2. LinkedList

LinkedList는 Double linked list(이중 연결 리스트) 구조를 사용하여 요소를 저장하는 리스트 구현체이다. 각 노드는 데이터와 다음노드의 주소, 이전 노드의 주소를 갖는다.

특징

  • 중간에 데이터를 삽입/삭제 시, 연결만 바꿔주면 되므로 ArrayList에 비해 빠르다
  • 인덱스로 접근할 수는 있지만, 실제로는 앞에서부터 순차 탐색해야하므로 검색 속도가 느리다.
  • 각 노드가 포인터(참조)를 2개씩 갖고있기 때문에 ArrayList보다 메모리 사용량이 많다.(메모리 오버헤드)
  • Queue, Deque 인터페이스도 구현하고 있어 스택, 큐, 덱 자료구조로도 활용 가능

따라서 삽입/삭제가 빈번한 경우, 순차적 접근이 많은 경우에 사용하는 것이 좋다.

 

3. ArrayList vs LinkedList

두 리스트는 모두 List 인터페이스를 구현하지만, 내부 동작 방식이 달라 성능 차이가 존재한다.

 

주요 메서드 성능 비교

  ArrayList LinkedList
add(E element) ✅ O(1) (끝에 추가) ✅ O(1) (끝에 추가)
add(int index, E element) ❌ O(n) (중간 삽입 시 밀어내기) ✅ O(n) (이동 + 노드 연결만 하면 됨)
addAll(Collection<? extends E>) ✅ O(m) (추가할 요소 수 m만큼) ✅ O(m)
clear() ✅ O(1) ✅ O(1)
contains(Object o) ❌ O(n) (순차 탐색) ❌ O(n) (노드 순회)
elementAt(int index) ✅ O(1) (배열 접근) ❌ O(n) (앞에서부터 순회)
get(int index) ✅ O(1) ❌ O(n)
indexOf(Object o) ❌ O(n) ❌ O(n)
isEmpty() ✅ O(1) ✅ O(1)
remove(int index) ❌ O(n) (뒤로 밀어야 함) ✅ O(n) (노드만 끊어주면 됨)
remove(Object o) ❌ O(n) (탐색 + 삭제) ❌ O(n) (탐색 + 연결 해제)
size() ✅ O(1) ✅ O(1)
toArray() ✅ O(n) ✅ O(n)
sort(Comparator) ✅ O(n log n) (내부 정렬 지원) ❌ O(n log n) (Array로 바꿔 정렬함)
  • ArrayList: 조회 작업이 빈번하고, 요소의 추가/삭제가 주로 리스트의 끝부분에서 이루어지는 경우에 적합. 예를 들어, 데이터베이스의 레코드를 조회하여 리스트에 저장하고 이를 순차적으로 처리하는 경우에 유용
  • LinkedList: 삽입과 삭제가 빈번하게 발생하는 경우에 적합. 예를 들어, 구현해야 하는 기능이 큐(Queue) 또는 덱(Deque)과 같이 데이터의 앞뒤로 빈번한 추가 및 삭제가 필요한 경우에 유용

 

 

4. Array vs ArrayList | ArrayList vs LinkedList

1) Array vs ArrayList

  Array ArrayList
크기 변경 ❌ 고정 ✅ 동적 증가/감소
제네릭 지원 ❌ 불가능 ✅ 가능 (List<Integer>)
메서드 제공 ❌ 없음 (기본 연산만) ✅ 추가, 삭제, 검색 등 다수
사용 난이도 낮음 (직관적) 높음 (컬렉션 API 사용)

📌 사용 상황

  • 배열은 고정 길이, 단순 구조에서 사용
  • ArrayList는 데이터 추가/삭제가 많은 일반적인 컬렉션 처리에 사용

2) ArrayList vs LinkedList

  ArrayList LinkedList
내부 구조 배열 (Object[]) 이중 연결 리스트 (노드)
접근 속도 ✅ 빠름 (O(1)) ❌ 느림 (O(n))
삽입/삭제 ❌ 느림 (중간에선 O(n)) ✅ 빠름 (O(1))
메모리 사용량 낮음 높음 (포인터 추가 저장)
활용 구조 일반 리스트, 조회 중심 큐, 덱, 삽입/삭제 중심 구조

 

결론

Array 고정 크기, 빠른 접근 크기 변경 없고 단순한 구조일 때
ArrayList 동적 배열, 빠른 조회, 느린 삽입/삭제 조회 중심, 리스트 UI 렌더링 등
LinkedList 노드 기반 연결 구조, 삽입/삭제 빠름 큐, 덱, 삽입/삭제 많은 경우

 

5. 리스트 순회

1) 일반 for문 (index 기반)

for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
}
  • ✅ ArrayList: get(i)가 O(1) → 성능 좋음
  • ❗ LinkedList: get(i)가 O(n) → 반복문 안에서 성능 저하 가능성 있음

📌 Tip: LinkedList에서는 되도록 for-each나 iterator 사용이 더 효율적

 

2) 향상된 for문 (for-each)

for (String fruit : list) {
    System.out.println(fruit);
}
  • ✅ ArrayList, LinkedList 모두 적절
  • 리스트 순회하며 구조를 변경하는 작업(추가 또는 삭제) → ConcurrentModificationException 발생 가능.
  •  위의 경우에는 따라서 Iterator 사용하는 것이 안전.

 

3) Iterator 순회

Iterator<String> iter = list.iterator();
while (iter.hasNext()) {
    String fruit = iter.next();
    if (fruit.equals("banana")) {
        iter.remove(); // 안전하게 삭제 가능
    }
}
  • ✅ 안전하게 요소 삭제 가능
  • ✅ ArrayList, LinkedList 모두 사용 권장
  • ✔ 삭제가 필요한 상황에서는 iterator가 가장 안전하고 유연함

결론

  삭제 가능 속도(ArrayList) 속도(LinkedList) 특이사항
for (i) ✅ (주의) 빠름 (O(1)) 느림 (O(n)) 삭제 시 인덱스 조정 필요
for-each ❌ 보통 보통 삭제 시 예외 발생 가능
iterator ✅ 빠름 빠름 삭제 가능, 안전함 ✅
  • ArrayList: for (i) 성능 유리 (get(i) 빠름)
  • LinkedList: iterator 기반 순회가 유리 (get(i)는 느림)
  • 삭제가 필요하면 무조건 Iterator 쓰는 게 안전!

 

cf) List.stream().forEach(), removeIf() 

 - 자바 8 이후 추가된 함수형 스타일의 컬렉션 처리 방식.(이는 나중에 정리하겠다~)

 

참고

- https://inpa.tistory.com/entry/JAVA-%E2%98%95-LinkedList-%EA%B5%AC%EC%A1%B0-%EC%82%AC%EC%9A%A9%EB%B2%95-%EC%99%84%EB%B2%BD-%EC%A0%95%EB%B3%B5%ED%95%98%EA%B8%B0#linkedlist_vs_arraylist_%ED%8A%B9%EC%A7%95_%EB%B9%84%EA%B5%90

- https://sugoring-it.tistory.com/258

- https://inpa.tistory.com/entry/JAVA-%E2%98%95-ArrayList-%EA%B5%AC%EC%A1%B0-%EC%82%AC%EC%9A%A9%EB%B2%95

- https://pongic.tistory.com/3

- https://velog.io/@hameee/Java-List