[Java] Chapter 1. List

✔️ List

1. 특징

• 여러 개의 데이터를 한꺼번에 다룰 수 있음
• 미리 공간을 확보해놓지 않아도 됨
• 메모리 상에 연속되지 않아도 됨
• 필요에 따라 데이터가 늘어나거나 줄어듬(동적 할당)
• 데이터 사이에 빈 공간을 허용하지 않음

2. 단점

• 목표 위치를 알려면 첫 번째 위치로부터 index로 한 칸씩 이동하면서 찾아야 함
• 객체로 데이터를 다루기 때문에 적은 양의 데이터만 사용할 경우 배열에 비해 차지하는 메모리가 커짐

3. 차이점 - 배열

• 배열은 처음 선언한 배열의 크기 변경 불가능(정적 할당)
• 메모리에 연속적으로 나열되어 할당됨
• index에 위치한 하나의 데이터를 삭제하더라도 해당 index에는 빈 공간으로 계속 남음

5. Array로 List 만들기

Integer[] arr = new Integer[]{1, 2, 3, 4, 5};
List<Integer> list = Arrays.asList(arr);

6. 리스트의 종류별 시간복잡도

종류	add()	remove()	get()	contains()
ArrayList	O(1)	O(n)	O(1)	O(n)
LinkedList	O(1)	O(1)	O(n)	O(n)
CopyOnWriteArrayList	O(n)	O(n)	O(1)	O(n)

💡 ArrayList에서 add는 O(1)이지만, capacity를 넘어 배열복사가 발생할 경우 O(n)이 됨
💡 LinkedList에서 특정 요소를 삭제하는 경우는 O(1)이지만, 요소를 찾아서 삭제해야 할 경우 O(n)이 됨

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

// LinkedList
// ArrayList(synchronized X) - index에 빠르게 접근해야할 때
// Vector(synchronized O) - index에 빠르게 접근하되 thread safe 해야 할 때

public class practiceList {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();

        // 리스트 요소 추가
        list.add(1);
        list.add(2);
        list.add(3);
        System.out.println(list); // [1, 2, 3]

        list.add(1, 10); // [1, 10, 2, 3]
        System.out.println(list);

        // 해당 인덱스의 값 반환
        System.out.println(list.get(1)); // 10

        // 인덱스로 값 변경
        list.set(1, 4);
        System.out.println(list); // [1, 4, 2, 3]

        // 인덱스로 값 찾기
        System.out.println(list.indexOf("3")); // 3
        System.out.println(list.lastIndexOf("3")); // 3

        // 인덱스로 값 삭제
        list.remove(1);
        System.out.println(list); // [1, 2, 3]

        // 값 포함하는지
        System.out.println(list.contains(4)); // false

        // Array로 변환 1
        System.out.println(list.toArray()); // [Ljava.lang.Object;@1540e19d

        // Array로 변환 2
        System.out.println(list.stream().mapToInt(Integer::intValue).toArray()); // [I@58372a00

        // 배열 비우기
        list.clear(); // []

        // 배열 비었는지 확인
        System.out.println(list.isEmpty()); // true

        // 두 리스트 합치기
        ArrayList<Integer> a1 = new ArrayList<>();
        a1.add(1);
        a1.add(2);
        a1.add(3);

        ArrayList<Integer> a2 = new ArrayList<>();
        a2.add(4);
        a2.add(5);
        a2.add(6);

        a1.addAll(a2);
        System.out.println(a1); // [1, 2, 3, 4, 5, 6]

        // a1이 a2를 포함하는지
        System.out.println(a1.containsAll(a2)); // true

        // 해당 요소 제외하고 모두 지우기
        a1.retainAll(a2);
        System.out.println(a1); // [4, 5, 6]

        // 전체 조회 1
        Iterator<Integer> iterator = a1.iterator();
        while(iterator.hasNext()) {
            int i = iterator.next();
            System.out.print(i + " "); // 4 5 6
        }

        // 전체 조회 2
        for(int i = 0; i < a1.size(); i++) {
            System.out.print(a1.get(i) + " "); // 4 5 6
        }
    }
}

---

✔️ List의 종류

1. ArrayList

• 최상위 타입인 Object[] 타입으로 배열을 생성하여 사용함
• 장점 : 요소 접근 면에서 성능이 좋음
• 단점 : 중간 요소의 삽입, 삭제가 발생하는 경우 그 뒤의 요소들을 한 칸씩 밀거나 당겨야 한다는 이유로 비효율적임

2. LinkedList

• 노드(데이터와 주소로 이루어진 클래스)를 만들어 서로 연결함, 즉 이전 노드와 다음 노드를 연결함
• 장점 : 삽입, 삭제 시 해당 노드의 링크를 연결하거나 끊어주기만 하면 됨
• 단점 : 요소 검색 시 처음 노드부터 해당 요소까지 모두 방문해야 함

3. Vector(+Vector를 상속받은 Stack)

• ArrayList와 비슷함, 동기화를 지원함
• 장점 : 멀티쓰레드에서 안전함
• 단점 : 단일쓰레드에서는 ArrayList에 비해 성능이 약간 느림