[Java] 배열(Array)과 리스트(List)

배열

index(식별자)와 값으로 구성

배열은 크기를 정의하고 변경할 수 없음

초기 정의된 크기대로 연속된 메모리 공간을 가짐

논리적 저장 순서와 물리적 저장 순서가 일치

장점

메모리 공간이 연속적이여서 관리가 편리함

인덱스를 사용해 검색이 빠름

단점

초기 크기 지정(컴파일) 이후, 변경이 되지 않음

만약 데이터가 삭제된다면 빈 공간으로 남아있게 되어 낭비가 생김

예시

int[] i = {1, 2, 3}; // 초기 선언 int[] i; i = new int[] {1, 2, 3}; // i = {1, 2, 3} 은 컴파일 에러 발생 int[] i = new int[3]; // 초기값 0으로 5 크기의 배열 생성 i[0] = 1; i[1] = 2; int i[]; // C언어 스타일

리스트

동적으로 크기 할당이 가능

장점

포인터가 다음 데이터의 순서를 가리키기 때문에 삽입, 삭제가 빠름 (Linked List)

크기 할당이 동적임

데이터 삭제시, 포인터가 해당 메모리 공간을 가리키지 않으면 되기 때문에 효율적임 (Linked List)

단점

기본 타입은 담을 수 없음 (객체만 가능)

리스트의 5번째 데이터를 검색하기 위해선 1번째 → 2번째 → 3번째 → 4번째 → 5번째 와 같이 순차적으로 포인터를 따라가야 함 (Linked List)

예시

List<String> s = new ArrayList<>() { { add("1"); add("2"); add("3"); } }; List<String> s1 = new ArrayList<String>(Arrays.asList(new String[]{ "1", "2", "3" })); // 중복으로 어레이 생성하는 로직으로 지양 List<String> s2 = new ArrayList<String>(Arrays.asList("1", "2", "3")); // 타입에서 String이 선언되어 있기 때문에 뒷 부분의 String은 제거할 수 있음 List<String> s3 = new ArrayList<>(Arrays.asList("1", "2", "3")); // 초기 선언 후, 삽입, 삭제 불가능 List<String> s4 = Arrays.asList(new String[]{ "1", "2", "3" }); // 중복으로 어레이 생성하는 로직으로 지양 List<String> s5 = Arrays.asList("1", "2", "3"); List<String> s6 = List.of("1", "2", "3"); List<String> s7 = new ArrayList<>(); s7.add("a"); List s00 = new ArrayList(); s00.add(1); s00.add("as"); // 타입을 선언하지 않으면 파이썬과 유사하게 리스트를 사용할 수 있음

List 종류

list는 Collection 인터페이스를 확장한 인터페이스로 실제로 선언하고 사용하기 위해선 위의 ArrayList와 같이 실제 구현체를 사용해야 합니다.

ArrayList

ArrayList는 배열과 동일하게 인덱스로 객체를 관리하고 크기를 동적으로 변경할 수 있습니다. 만약 기본 저장 용량이나 설정한 용량이 넘어 더 많은 객체가 입력되면 배열의 크기를 증가시킵니다.

• 확인해봐야 하지만 golang에서와 유사한 개념이라면 ArrayList는 인덱스로 객체를 관리하므로 연속된 메모리 공간을 할당받습니다. 만약 초기 크기가 100인데 그 이상의 객체가 입력되면 150개의 연속적인 메모리 공간을 찾아 할당합니다.

배열에서는 중간의 객체가 삭제되면 빈 공간으로 남아 있었지만, ArrayList는 중간 객체가 삭제되면 삭제된 뒤 객체들을 앞으로 이동시킵니다. 동일하게 객체가 추가되면 추가된 이후의 객체들을 뒤로 이동시킵니다.

객체가 삽입, 삭제될 때마다 데이터가 이동하므로 삽입, 삭제에 효율적이지 않습니다.

예시

// 초기 용량 설정 List<String> s = new ArrayList<>(100); List<String> s1 = new ArrayList<>(); ArrayList<String> s2 = new ArrayList<>();

요약

배열과는 다르게 ArrayList는 동적 크기 할당 가능

배열은 모든 타입을 담을 수 있지만 Array List는 객체만 가능 (int와 같은 기본타입은 오류. int를 담고 싶으면 Integer 객체를 선언해야 함)

조회, 검색이 빠르고 삽입, 삭제는 비효율적

AbstractList 추상 클래스를 상속

LinkedList

ArrayList나 배열과는 다르게 인덱스는 몇 번째 데이터인지 순서의 의미를 의미하고 각 객체에는 포인터로 다음 객체 주소값을 가리키고 있습니다. 또한 논리적 저장 순서와 물리적 저장 순서가 같지 않습니다.

리스트의 5번째 데이터를 검색하기 위해선 1번째 → 2번째 → 3번째 → 4번째 → 5번째 와 같이 순차적으로 포인터를 따라가야 하므로 복잡도가 O(n)이 발생합니다.

LinkedList는 삽입, 삭제가 효율적인데 데이터를 삽입 또는 삭제 한 다음, 변경이 일어난 객체의 앞, 뒤 포인터만 변경해주면 됩니다.

예시

List<String> s = new LinkedList<>(); LinkedList<String> s1 = new LinkedList<>();

Vector

Vector는 ArrayList와 동일한 내부 구조를 가지고 있습니다. 다른 점은 동기화된 메소드로 구성되어 있기 때문에 멀티 스레드가 동시에 Vector의 메소드를 실행할 수 없고 하나의 스레드가 메소드 실행을 완료해야만 다른 스레드가 메소드를 실행할 수 있습니다. 그래서 멀티 스레드 환경에서 안전하게 객체를 추가, 삭제할 수 있습니다. 이것을 스레드에 안전하다고 표현합니다.

요약

동적 크기 할당 가능

ArrayList와 마찬가지로 객체만 담을 수 있음

조회, 검색이 느리고 삽입 삭제가 효율적

AbstractSequentialList 추상 클래스를 상속

멀티 스레드 환경에서는 ArrayList보다 Vector를 사용하는 것이 안전