[인실리코젠] 배열 vs 리스트

해당 글은 (주)인실리코젠 조일흠 선임님께서 질문하신 내용에 대한 답변입니다.

 

배열

• 배열 - 여러 개의 데이터를 하나의 이름으로 그룹핑해서 관리하기 위한 자료구조
• index는 값에 대한 유일무이한 식별자(마치 주민번호)(리스트에서 인덱스는 몇 번째 데이터인가 정도의 의미를 가짐)
• 논리적 저장 순서와 물리적 저장 순서가 일치 => index로 해당 원소에 접근할 수 있다. (O(1)의 시간복잡도를 가짐)
• 연속된 메모리의 공간으로 이루어져 있다
• 배열은 정의와 동시에 길이를 지정하며 길이를 바꿀 수 없다.

리스트

• 리스트 - 배열과 같이 데이터를 그룹핑해서 관리
• 리스트는 순서가 있는 엘리먼트의 모임으로 배열과는 다르게 빈 엘리먼트는 절대 허용하지 않는다.
• 리스트는 배열이 가지고 있는 인덱스라는 장점을 버리고 대신 빈틈없는 데이터의 적재 라는 장점을 취함
• 리스트에서 인덱스는 몇 번째 데이터인가 정도(순서)의 의미를 가진다. (배열-Array에서의 인덱스는 값에 대한 유일무이한 식별자)
• 빈 엘리먼트는 허용하지 않는다. => java에서는 허용하는 경우가 있음
• 불연속적으로 메모리 공간을 차지.
• 포인터를 통한 접근
• 순차성을 보장하지 못하기 때문에 spacial locality 보장이 되지 않아서 cash hit가 어렵다.(데이터 갯수가 확실하게 정해져 있고, 자주 사용된다면 array가 더 효율적이다.)
  • spacial locality
  • Locality에 대해 간단히 알아보자.
    • 기억 장치 내의 정보를 균일하게 접근하는 것이 아닌 어느 한순간에 특정 부분을 집중적으로 참조하는 특성
    • CPU가 메모리로부터 데이터를 가져오는 데 있어서 가장 최근 영역에, 가장 접근하기 가까운 영역에 Data를 저장하면 훨씬 효과적이라는 것
    • 대표적인 locality
      • 1. Temporal locality
        •  설명
          • 최근 사용되었던 기억 장소들이 집중적으로 엑세스되는 경향.
          • 프로그램 실행시 한번 접근이 이루어진 주소의 메모리 영역은 자주 접하게 된다는 프로그램 성격 표현.
        • 예
          • 순환, Stack 등등
      • 2. Spatical locality
        • 설명
          • 특정 클러스터의 기억 장소들에대해 참조가 집중적으로 이루어지는 경향.
          • 프로그램 실행시 접근하는 메모리의 영역은 이미 접근이 이루어진 영역의 근처일 확률이 높다는 프로그램 성격 표현.
        • 예
          • Sequential processing, Array 등등.

가장 큰 차이

• 배열은 크기 할당을 반드시 해줘야 하고, 리스트는 그럴 필요가 없다는 것
• 배열은 제네릭을 사용할 수 없지만 ArrayList는 타입 안정성을 보장해주는 제네릭을 사용할 수 있음

직접 코드로 확인하자

package JavaStudy;

import java.util.ArrayList;

public class ArrayList연습 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int [] arr = new int[5];
		
		System.out.print("배열 출력 : ");
		for(int i = 0 ; i < arr.length ; i++) {
			arr[i] = 5 * (i+1);
			System.out.print(arr[i] + " ");
		}
		System.out.println();
		ArrayList<Integer> array = new ArrayList<>();
		
		array.add(5);
		array.add(10);
		array.add(15);
		
		System.out.println("리스트 출력 " + array.toString());
		System.out.print("리스트 크기 : " + array.size());
				
	}
}

 

ArrayList는 add 함수를 통해서 동적으로 크기가 늘어나는 것을 볼 수 있다.

 

둘 중 어느 것이 더 효율적인가?

• 상황에 따라 다르다고 생각된다.

크기 구하기

• 배열의 크기 : length
• 리스트 크기 : size()

 

ArrayList

해당 이미지는 https://docs.oracle.com/javase/8/docs/api/ 에서 가져온 화면이다.

 

살펴보면 ArrayList는 AbstractList 를 상속 받고 AbstractList는 AbstractCollection을 상속 받는다.

 

그렇다면 Collection은 뭐하는 놈일까?

 

Collection 프레임워크

컬렉션 프레임워크 : 데이터 그룹을 저장하는 클래스들을 표준화한 설계

ArrayList는 List 인터페이스에 구현되어 있다.

 

Collection 프레임워크의 장점

• 인터페이스와 다형성을 이용한 객체지향적 설계를 통해 표준화되어 있어 사용법을 익히기 쉬움
• 데이터 구조 및 알고리즘의 고성능 구현을 제공하여 프로그램의 성능과 품질 향상
• 관련 없는 API 간의 상호 운용성 제공
• 소프트웨어 재사용 촉진

 

컬렉션 프레임워크에 저장할 수 있는 데이터는 오로지 객체(object) 뿐이다. primitive 타입을 wrapper 타입으로 변환하여 Integer 나 Double 객체 형태로 Boxing하여 저장해야 한다.

즉, ArrayList는 List 인터페이스에서 구현된 클래스이며, List는 Collection에 속한 인터페이스이다. Collection은 Iterable 인터페이스를 상속 받는데, Iterable은 컬렉션 인터페이스들의 최상위 인터페이스이다. 컬렉션 자료를 순회 시 사용되는 Iterator 객체를 관리하는 객체로도 볼 수 있다.