자료구조 - 배열 (feat. Java, Python), 자매품 - Java Collection ArrayList

배열이란?

배열을 왜 쓸까?

• 같은 종류의 데이터를 관리하기 하기 위해서
• 같은 종류의 데이터를 순차적으로 저장

 

 

대전제는 데이터를 쉽게 관리하는 목적이다. 그것을 한 묶음으로 관리하는게 효율적이다. 근데 이걸 또 순차적으로 있다면? 한눈에 봐도 데이터를 다루기가 쉬울 것이다.

 

장점 - Index

배열의 가장 큰 장점은 Index라고 할 수 있다. 배열는 공간에 각각의 element 마다 각각의 index가 생긴다. (각각각각)
각 요소에 번호가 생기면 데이터 안에 하나의 값만 가져올 때 굉장히 편해진다. 또한 값을 찾을 때 소모되는 비용은 index로 인해 시간복잡도 O(1)을 가진다.

 

 

 

단점 - 배열의 크기설정 & 추가/삭제

배열의 가장 큰 단점 데이터를 삭제와 추가 하는 부분에서 발생한다. 배열은 크기를 설정해야 한다는 것이다. 5개의 요소면 5개, 10개면 10개 딱 설정을 해야한다.

요소가 배열에 꽉 차 있을 때, 배열에 데이터 하나를 추가한다면 어떻게 될까?

여기서 부터가 문제가 생긴다. 추가적인 배열을 설정해 뒤에 붙여줄까, 새로운 크기의 배열을 다시 설정해서 이전에 데이터와 새로운 데이터를 다시 넣어줄까 하는 의문이 생긴다. 하지만 딱 봐도 굉장히 비효율 적이라는 것이 직감적으로 생긴다.

또한 삭제하는 과정에 문제가 발생한다. 배열은 가운데 공간이 비면 안된다. 즉, 순서대로 데이터가 무조건 있어야 한다. 따라서 가운데 위치한 어떤 데이터를 삭제를 했다면, 그 뒤 데이터를 앞으로 이동 시켜줄 필요가 있다.

int[] arr = new int[5]; // 5개 숫자 데이터를 넣을 수 있는 배열
String[] str = new String[5]; // 5개 문자 배열

위 코드는 자바 코드이다. 자바는 내부배열 메서드를 사용하려면 배열의 크기를 선언해줘야 한다. 이 이상의 데이터를 넣게 되면 오류가 나온다.

arr = [1,2,3,4]
arr.append(5)
print(arr) # [1,2,3,4,5]

파이썬은 배열의 크기를 선언하는 것이 없다. 쉽게 배열을 넣을 수 있고, 삭제할 수 있다.

 

Python 리스트

파이썬은 기본적으로 배열이 아닌 리스트로 구현되어져 있다.
하지만 내부적으로는 동적 배열(Dynamic array)로 구현되어 있다. 즉, 기본 배열 방식은 제공되지 않고, 동적 배열만 제공한다. 이 동적 배열은 자바의 ArrayList와 비슷한 기능을 제공한다. 배열의 크기를 설정해주지 않고, 내부적으로 지원해준다.

 

Java Collection

자바 컬렉션 프레임워크에 ArrayList가 구현되어 있다. 내부적으로 어떤 함수가 구현되어 있는지 찾아보는 것도 좋은 이해 방법이라고 생각한다. 더하여 공식문서를 참고는 것도 내부로직을 이해하고, 메서드를 사용하기 위해서 좋은 방법이라고 생각된다!

 

Array T[]

가장 기본이 되는 데이터 셋으로 이 로직에서 파생되서 여러 기능을 만든다.
가장 큰 특징은 사용이 정적으로 되어 있어서 불편하지만, 요소를 가져오기 위해 index를 사용한다는 것이다.

특징과 한계로는 아래와 같다.

• 처음 배열의 크기를 정하고, 이후에 크기를 변경할 수 없다.

  • 자바에서 이런 특징을 정적 할당(static allocation)이라고 한다.

• 메모리에 연속적으로 구현되어 있어 index를 알고 있다면 요소에 접근속도가 굉장히 빠르다.

• 중간에 요소가 삭제 된다고 하더라도 빈 공간으로 남아있다.

 

ArrayList<제네릭T>

파이썬 List와 유사한 자바의 ArrayList를 알아보자.

ArrayList는 자바에서 가장 쉽게 접하는 컬렉션 프레임워크이다. 기존 배열의 추가, 삭제 부분의 불편한점을 개선한 배열이다.

특징과 한계로는 아래와 같다.

• 배열의 Index 특징을 기반으로 하여 요소에 접근 시간은 상수(O(1))
• 데이터의 개수에 따라 가변적으로 공간을 늘리거나 줄이는 기능
• 배열이 다 차게 되면 배열을 copy하는 방식으로 늘려 시간 효율이 떨어진다.
• 초기 용량은 10이며 용량을 초과할 경우 1.5배로 증가시킨다.
• 배열에 빈 공간이 생기지 말아야 하기 때문에, 배열에 데이터가 추가/삭제가 될 경우 공간을 생성하거나 이동하는 이슈로 시간 효율이 떨어진다.

 

사용 방식

기본 Array 와 ArrayList Collection

int[] arr = new int[5]; // 5크기의 배열 생성

import java.util.ArrayList;
ArrayList<Integer> arr = new ArrayList<>(); // 기본적으로 10크기로 초기화

ArrayList 타입에 따른 선언

// 숫자 ArrayList
ArrayList<Integer> numArr = new ArrayList<>();

// 문자 ArrayList
ArrayList<String> numArr = new ArrayList<>();

 

데이터 추가/삭제

ArrayList의 데이터 주가 삭제시 메서드

 

 

공식문서에 따르면 add()와 addAll을 사용하는 두가지 방식이 있다.

 

Method	설명
add(E e)	index번호를 지정할 수가 있고, 요소만 넣을 수도 있다. 배열의 가장 끝에 요소가 추가
addAll(int index, Collection c)	지정한 자료의 모든 요소를 끝에 추가

 

ArrayList<String> arr = new ArrayList<>();

// add()
arr.add("1");
arr.add("2");
arr.add("3");
arr.add("4");
arr.add("5");

System.out.println(arr); // [1,2,3,4,5]


ArrayList<String> arr2 = new ArrayList<>();

arr2.add("6");
arr2.add("7");
arr2.add("8");
arr2.add("9");

// addAll()
arr.addAll(arr2);


System.out.println(arr); // [1,2,3,4,5,6,7,8,9]

// add(index, element);
arr.add(3, "0");
System.out.println(arr); // [1,2,3,0,4,5,6,7,8,9]

 

 

Method	설명
remove(int index)	index 위치 요소 제거
remove(Object o)	파라미터로 들어온 o객체 제거
removeAll(Collection<?> c)	컬렉션에 지정한 것과 동일한 객체를 제거

ArrayList<String> arr = new ArrayList<>();

arr.add("1");
arr.add("2");
arr.add("3");
arr.add("4");
arr.add("5");

arr.remove(1);

System.out.println(arr); // [1,3,4,5]

 

끝으로

ArrayList Collection의 모든 요소를 다뤄보지 않았지만, 2편에 요소를 검색하고, 가져오는 부분을 다뤄볼까 한다. Array와 ArrayList에서 뭐가 좋고 안좋고는 없다. 맞는 부분을 찾아서 쓴다면 가장 좋은 것이고, 틀린 부분에서 사용한다면 가장 안좋은 로직이 될 거라 생각한다.

 

Referance

참고 자료
초보몽키 개발블로그
이것이 자바다
공식문서