[Data Structure] ArrayList 데이터 동적 할당

해당 게시물은 기존에 만들어진 자료 구조인 ArrayList 내의 데이터가 어떻게 동작하는지를 이해하기 위해 작성되었습니다.
개인적인 바램으로 대규모 시스템에서의 데이터를 다룰 때의 인사이트를 얻을 수 있었으면 좋겠습니다.

 

ArrayList에서 데이터를 어떻게 다루고, 동작하는지에 대해 이해해보도록 하겠습니다.

 

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

ArrayList를 알아보기 전에, 배열과 리스트가 단순히 데이터를 저장하는 공간이 아님임을 알려드립니다. 이에 대해 혼동하는 면이 있을 것 같습니다. 이를 위해 먼저, 배열과 리스트 간의 컴퓨터 공학적인 개념부터 짚고 넘어가고자 합니다. 

 

배열은 메모리 상 연속적인 공간을 할당받음으로써, 이 곳에 데이터를 저장합니다. 따라서, 연속적인 공간에 접근하기 위해서 Index라는 배열 내 저장공간의 식별자를 사용합니다. 이러한 Index를 알고 있다면, 배열에 빠르게 접근을 할 수 있습니다. 하지만, 중간 요소에 데이터를 삽입/삭제 할 때 뒤에 위치한 Index의 데이터를 더 뒤로 밀어줘 공간을 확보하거나, 다시 앞으로 당겨오는 과정이 필요하기 때문에 최악의 경우에는 모든 공간을 탐색해야 해 처리 속도가 느립니다. 즉, 특정 데이터에 대한 접근은 매우 빠르지만, 삽입/삭제에는 좋지 않은 성능을 지닙니다

 

리스트는 메모리 상 비연속적인 공간을 할당받아, 이 곳에 데이터를 저장합니다. 선형적으로 일직선 상으로 연결되어 있으며, 순서 개념이 없습니다. 이 때, 순서 개념없이 연결되어 있다는 점에서 리스트 내에서는 '포인터(Pointer)' 등을 활용해서 각 원소의 순서를 이룹니다. 때문에 삽입/삭제 시, 연결된 포인터만 바꿔주면 되기 때문에 더 빠르게 처리할 수 있습니다. 하지만, 특정 데이터로 접근하기 위해서는 첫번째 데이터부터 선형 검색(Linear Search) 해야해 좋지 않은 성능을 지닙니다.

 

ArrayList

ArrayList 내 원소는 배열

주의할 점은 컴퓨터 공학적인 면에서의 List 개념과 실제 구현에서 쓰이는 List의 개념이 다르다는 점입니다.

Java에서 List는 인터페이스 형태로 제공이 되며, 이를 배열로 구현한 것이 ArrayList이고, 노드 끼리의 주소 포인터를 참조시키며 구현한 것이 LinkedList 입니다. 배열로 구현하였기 때문에 기존 List 개념과 달리, 연속적인 공간에 할당받아 데이터를 저장합니다. 이 덕분에 단일 요소 접근에서 Index 식별자를 가진 배열로 구현된 덕분에 빠르지만, 삽입/삭제에서는 앞,뒤 인덱스를 이동시켜야 하는 추가 작업을 해야하기 때문에 다소 느린면이 있습니다.

배열과 ArrayList의 사용

//Array 사용
int[] numberArray = new int[5];
numberArray[0] = 1;
numberArray[1] = 2;

//ArrayList 사용
ArrayList<Integer> numberList = new ArrayList<>();
numberList.add(1);
numberList.add(2);

여러분들이 배열과 ArrayList에 데이터를 넣고자 하신다면, 위처럼 작성하실 수 있습니다. 위 처럼 ArrayList는 배열과 달리, 크기를 고정적으로 정하지 않고도 그 공간에 데이터를 데이터를 유동적으로 저장시킬 수 있습니다.

그런데, ArrayList에서도 배열을 쓰는데 이게 '어떻게 내부적으로 데이터가 동작시키길래' 이게 가능할까요??

 

ArrayList 란??

https://blog.kakaocdn.net/dn/qp1KU/btqEiLKhVVi/h1IfW46J1Ks7nu1DBvgUmk/img.png

ArrayList란 앞서 설명드린 것과 같이, List 인터페이스를 연속적인 공간의 배열로 구현한 것입니다. 단, 배열과 다른 점은 유동적으로 공간을 가져가, 데이터를 저장할 수 있다는 것입니다. 이에 대해 코드로 살펴보겠습니다.

 

ArrayList 동작 원리

ArrayList 내 사용되는 데이터

- 초기 수용량(10)에 대한 데이터와 빈 배열과 초기 배열이 사용될 것임을 예상할 수 있습니다.

- elementData는 ArrayList 내에 저장된 모든 (배열) 데이터를 의미합니다.

- 여기에서 중요하게 봐야한다고 생각한 점은 size를 별도로 존재한다는 것입니다. elementData.length로 길이를 젤 수도 있지 않을까요?? 이렇게 설계된 이유는 이 때, elementData가 현재 할당된 배열을 그 자체를 의미하기 때문입니다. 이 때문에 할당된 배열이 데이터로만 차여있지 않을 수 있고, 내부에 실질적으로 저장된 데이터의 갯수를 size로 따로 관리하도록 합니다.

 

ArrayList 생성 - 동적 할당 방식

1-1. 별도 파라미터 없는 생성자

- ArrayList는 최초 아무 파라미터 없이 생성할 수 있습니다.

- 따라서, 이럴 경우 기존의 저장된 DEFAULTCAPACITY_EMPTY_ELEMENTADATA를 반환합니다.

 

1-2. 파라미터(수용량)이 존재하는 생성자

- ArrayList는 실질적으로 배열로 구현되어 있기 때문에 초기 수용량(initialCapacity)를 입력할 수 있습니다.

- 만약 초기 수용량이 정상적인 값(0보다 큰)이라면, 새로운 배열 객체를 생성해서 elementData에 할당합니다.

- 아무 데이터가 없다면, EMPTY_ELEMENTDATA( 빈 배열, { } )을 할당합니다.

 

 

2. ArrayList 데이터 삽입 - 데이터 공간 동적 변환

- 위 그림에서, 흔히 쓰이는 add(E e) 메서드를 먼저 살펴보겠습니다.

- 수정된 횟수를 증가시키는 역할을 담당시키고, 별도로 add(E e, Object[] elementData, int s) 메서드에 elementData와 size를 전달시켜 데이터 공간에 대한 역할로 분리시켜주고 있습니다.

- add(E e, Object[] elementData, int s)에서는 그저, 할당된 공간이 다 찬 경우 증가시키거나 마지막에 데이터를 삽입시켜주는 것으로 보입니다.

- 여기에서, 주의 깊게 살펴볼 점은 grow() 라고 생각합니다. 저희의 주된 관심사가 '어떻게 동적으로 데이터를 관리시킬 수 있을까' 이기 때문입니다. 

 

 

grow(), newLength()

- add로부터 호출된 grow는 최소한의 데이터를 저장하기 위한 공간 확보를 위해 size+1로 grow(int minCapacity)를 호출하고 있습니다. 그리고, 내부에서는 현재 ArrayList의 총 데이터(elementData 배열)의 길이와 전달받은 최소 공간에 대한 길이, 총 데이터의 오른쪽 1시프트 한 결과를 토대로 새로운 유동적인 길이를 확보(newLength())하고 있습니다.

 

- 그리고, newLength() 메서드 내에서는 계산한 길이를 토대로 증가시킬 공간의 대한 길이를 전달해주고 있습니다. 이 때, SOFT_MAX_ARRAY_LENGTH는 내부적으로 정해져 있는 것을 확인할 수 있었습니다! 또한, 이 길이가 벗어난다면 더 큰 공간을 확보할 수 있도록 hugeLength를 통해 SOFT_MAX_ARRAY_LENGTH를 새로운 길이로 반환시킬 수도 있습니다!

 

여기에서 그럼 newLength에서는 어떻게 유동적으로 추가 길이를 확보하고 있을까요??

이게 잘 이해되지 않을 수 있기 때문에 아래 그림으로 설명드리겠습니다!

만약, 현재 용량이 5의 길이로 가득 찬 ArrayList가 있다고 가정하겠습니다. 그 때의 데이터를 담기 위한 최소 용량은 6입니다. 유동적인 크기를 위해 grow 메서드에 최소 증가해야할 길이인 minGrowth를 넘겨줍니다. 이 후 newLength 메서드에 기존 ArrayList의 크기(elementData.length)인 oldLength, minGraph(oldLength - minGrowth) , 그리고 preGrowth을 넘겨주고 있습니다. 

 

이 때, prefGrowth에는 5를 >> 1 가 있습니다. 이 말은 5를 이진수로 변환(0101)시켜 이진수 자체를 그대로 오른쪽으로 1번 시프트(0010) 시킨다는 말과 같습니다. 때문에 2의 결과값이 나옵니다. >>1 은 곧 2로 나눈다는 말과 유사합니다. 따라서, 추가 길이는 기존 길이의 1.5배로 유동적으로 늘어남을 확인할 수 있었습니다!!

 

 

느낀 점

ArrayList가 데이터를 어떻게 유동적인 공간에 다룰 수 있는지가 결국은 배열(elementData)의 길이, size 그리고 시프트 연산을 통해서 추가 확장 공간을 유동적으로 가질 수 있구나라는 인사이트를 얻을 수 있었습니다. 각 메서드마다 역할이 분명하게 정해져 있어 제가 봤을때도 이해하기 쉽도록 짜주신 점에서 클린 코드의 중요함을 다시 한번 느꼈습니다. 이전에 혼동됐던 개념인 배열과 리스트의 개념도 다시 한번 정리할 수 있었던 의미 있는 시간이였습니다!

 

단순 프로젝트 만들기보다는 더 본질적으로 데이터 관점(인사이트)을 혼자 이해하려 하니 시간이 오래 걸렸습니다. 이에 대해 관심이 있는 사람이 주위에 없다보니, 하나하나 코드를 까보며 외로운 시간을 보냈던 것 같습니다. 데이터에 대한 인사이트를 얻고자 하시거나, 가볍게 얘기라도 나누시고 싶으신 분들은 dbstn6477@gmail.com이나 해당 게시물에 댓글을 작성해주시길 바랍니다..