Array와 List

김동헌·2024년 4월 13일

목록 보기

3/4

객체지향 스터디를 진행하면서 우테코 프리코스의 baseball을 학습하였습니다. 팀원들은 대부분 List로 구현했고 저는 Array로 구현을 했습니다.

Array가 현재의 기능에는 적합하다고 대략 알고 있었지만 어떤 부분에서 다른지 명확하게 답변을 할 수 없었어서 정리를 하기 위해 포스팅을 진행했습니다.

Code

public void computeScore(Baseball baseball) {
        resetCounts();
        int[] computerBall = baseball.getComputerBall();
        int[] userBall = baseball.getUserBall();
        for (int i = 0; i < BASEBALL_LENGTH; i++) {
            compute(computerBall, userBall, i);
        }
        resultDisplay();
    }

    private void compute(int[] computerBall, int[] userBall, int index) {
        int temp = -1;
        for (int i = 0; i < BASEBALL_LENGTH; i++) {
            if(computerBall[i] == userBall[index]) {
                temp = i;
                break;
            }
        }
        correctCount(index, temp);
    }

    private void correctCount(int index, int temp) {
        if (temp != index && temp != -1) { ballCount++; }
        if (temp == index) { strikeCount++; }
    }

computeScore(Baseball baseball)은
1. Baseball의 현재 도메인 상태를 메세지로 전달받아
2. 사용자의 ball과 컴퓨터의 ball을 비교
3. Strike&Ball을 계산하는 책임을 갖고 있는 객체입니다.

그렇다면computerBall과 userBall을 Array와 List를 적용했을 때 어떤 차이가 있는지 알아보겠습니다.

Array(배열)&List(리스트)

배열

여러 개의 데이터를 하나의 이름으로 그룹핑해서 관리 하기 위한 자료구조

배열은 연속적인 메모리 공간에 동일한 자료형의 원소들을 저장하는 구조입니다. 이렇게 저장된 각 요소는 인덱스를 통해 직접 접근이 가능하기 때문에 개별 요소에 대한 검색 및 접근이 빠릅니다.
단, 배열의 크기는 고정적으로 크기를 변경할 수 없고 삽입과 삭제는 용이하지 않습니다.

리스트

여러 개의 데이터를 하나의 이름으로 그룹핑해서 관리 하기 위한 자료구조이지만 배열과의 차이가 있음.

List는 동일한 자료형의 원소들을 비연속적인 메모리 공간에 저장합니다. 리스트의 크기는 가변적이며, 요소의 추가 및 제거가 쉽고 List 인터페이스의 다양한 메서드를 사용할 수 있어 작업이 편리합니다.
단, 순차적인 접근을 통해 배열에 비해 성능이 조금 더 느릴 수 있고, 메모리 오버헤드가 발생할 수 있습니다.

배열은 크기 할당이 필수고 리스트는 그럴 필요가 없습니다.

그렇다면 "리스트가 무조건 좋을까요?" 라는 질문에는 꼭 그렇지만은 않습니다.

리스트는 크기가 자동적으로 1.5배 증가하고, 이로 인해 사용하지 않는 메모리 할당이 많아지기 때문에 크기가 정해져 있는 데이터의 그룹핑을 하고 싶다면 배열이 더 효율적인 선택이 될 수 있습니다.

즉, 크기가 정해져 있다면 배열(Array)이 유리하고, 그렇지 않다면 ArrayList를 사용하는 것이 좋습니다. -> 네? ArrayList요 ?

List 인터페이스

저는 자바 개발자로 Java에는 List인터페이스를 이용해 여러 개의 구현체(ArrayList, LinkedList, Vector)가 있습니다.

먼저 List인터페이스의 특징을 볼까요 ?

객체가 일렬로 줄 서있는 구조
객체를 인덱스로 관리
객체 저장, 검색, 삭제 기능 제공
객체 저장 시 자동 인덱스 부여
객체 자체를 저장하는 것이 아니고 객체의 번지를 참조
구현 클래스 ArrayList, LinkedList, Vector

List 인터페이스 주요 기능

E → 제네릭 타입

객체 추가

boolean add(E e) → 특정 객체를 맨 끝에 추가
void add(int index, E element) → 특정 인덱스에 객체 추가
set(int index, E element) → 특정 인덱스의 객체 교체

객체 검색

boolean contains(Object o) → 특정 객체 존재 여부 체크
E get(int index) → 특정 인덱스에 저장된 객체 반환
boolean isEmpty() → 비어있는지 확인
int size() → 저장된 객체 수 리턴

객체 삭제

void clear() → 저장된 모든 객체 삭제
E remove(int index) → 특정 인덱스에 저장된 객체 삭제
boolean remove(Object o) → 특정 객체 삭제

ArrayList

내부 배열에 객체를 저장해서 인덱스로 관리
인덱스 0번부터 차례대로 저장
배열과 다르게 객체를 추가할 경우 자동적으로 저장 용량이 증가
특정 인덱스의 객체를 추가할 경우, 특정 인덱스를 기준으로 마지막 인덱스까지 1씩 밀림
특정 인덱스의 객체를 삭제할 경우, 특정 인덱스를 기준으로 마지막 인덱스까지 1씩 당겨짐
빈번한 객체 삭제와 삽입이 일어날 경우 ArrayList보다 LinkedList 사용이 유리
인덱스 검색이나, 맨 마지막에 객체를 추가하는 경우는 ArrayList가 더 성능이 좋다.
[ArrayList 구조]

LinkedList

ArrayList와 사용법은 같지만 내부 구조가 다름
인접 참조를 링크해서 관리
특정 인덱스의 객체를 제거하면 앞뒤 링크만 변경되고 나머지 링크는 변경되지 않는다.
빈번한 객체 삭제와 삽입이 일어나는 경우 ArrayList보다 유리하다.

[LinkedList 구조]

Vector

ArrayList와 동일한 내부구조
Thread Safe
동기화된 메소드로 구성
멀티 스레드가 동시에 실행할 수 없고, 하나의 스레드가 실행을 완료해야만 다른 스레드를 실행할 수 있다.
멀티 스레드 환경에서 안전하게 객체를 추가, 삭제 가능

정리

배열(Array)

고정된 크기의 연속적 메모리 할당
장점
- 인덱스를 통한 직접 접근이 가능하며, 데이터 접근 속도가 매우 빠름
- 메모리 상에서 연속적인 공간을 차지하기 때문에 CPU 캐시 효율이 좋다.
단점
- 크기가 고정되어 크기 변경이 불가능하다.
- 동적으로 요소를 추가, 삭제가 어렵다.

ArrayList

배열을 기반을 하는 가변 크기의 리스트 구현
장점
- 요소의 추가 및 삭제에 유연하다. 내부 배열이 가득 차면, 크기를 자동으로 늘린다.
- 인덱스를 통한 데이터 접근 속도가 배열과 동일하게 빠르다.
  - 단, 메소드 호출 오버헤드가 존재하는데 .get(index)메서드를 통해 데이터에 접근하는 경우 호출 자체가 작은 오버헤드를 발생한다. 메서드 호출 과정에서 발생하는 추가적인 오버헤드 발생`
    - 배열은 이러한 메서드 호출 과정이 없고 직접 접근하므로 더 빠르다.
단점
- 배열을 확장하는 과정에서 시간과 메모리 비용이 추가로 발생
- 배열에 비해 상대적으로 메모리 오버헤드가 크다.

LinkedList

요소 간 포인터를 이용해 연결된 리스트 구현
장점
- 요소의 추가 및 삭제가 매우 효율적이다. 특정 노드의 포인터만 조정하면 되기 때문에 상수 시간(complexity O(1)) 내에 수행 가능
단점
- 인덱스를 통한 접근이 비효율적임 (O(n) 시간 복잡도)) -> 순차적으로 포인터를 따라가며 접근해야 하므로, 접근 속도가 느림
- 각 요소가 포인터를 추가로 저장해야 하므로, 메모리 사용량이 더 많다.

김동헌

백엔드 기록 공간😁

이전 포스트

Thread Pool

다음 포스트