Java - native method With System.arraycopy() (Feat. ArrayList)

요즘, 그동안 기본기를 너무 챙기지 않고 프레임 워크와 아키텍쳐에 빠졌나 싶어서, 자료구조와 알고리즘을 다시 보고 있다가, 실질적으로 jdk 의 List 구현체인 ArrayList 를 까서 보았다. 그러다가 흥미로운 것을 보게되었고, 실질적으로 jdk 를 까보는 것도 재미가 있어서 블로깅을 해본다. 다들 알겠지만, ArrayList 는 말 그대로 내부적으로 data 를 저장하는 배열(array) 을 가지고 있다. 자료구조와 알고리즘 공부를 하게되면, 기본중의 기본인 ArrayList 와 LinkedList 의 비교를 하게 된다. ArrayList 의 add() 메서드는 끝에 집어 넣을 때 O(1) 상수 시간이고, 처음에 집어 넣을 때와 일반적인 상황에서 O(n) 으로 선형 시간이 된다. remove() 메서드도 배열의 제일 마지막을 지울 경우 O(1) 상수 시간이고, 처음을 지울 때와 일반적인 상황에서는 O(n) 으로 선형 시간이 된다. 배열을 내부적으로 가지고 있기 때문에, 당연하게 시작 혹은 중간에 data 를 삽입하게 되면 삽입 지점 index 에 있던 원래 있던 data 부터 배열의 끝까지의 모든 데이터들을 다음 index 공간( 오른쪽 )으로 Shift 연산을 해야 한다. 즉 해당 index 지점부터 배열의 끝까지 순회 하면서 오른쪽으로 한 칸 씩 밀어주게 된다. 반대로 remove 삭제의 경우에도, 시작 혹은 중간에 data 를 지우려고 하면 해당 지점 index 한칸 뒤에 있는 지점부터 배열의 끝까지의 data 들을 한칸 씩 모두 왼쪽으로 Shift 연산을 해야 한다. 즉 해당 index 다음 지점부터 배열의 끝까지 순회 하면서 왼쪽으로 한 칸 씩 밀어주게 된다. 이미지 제작의 귀찮음으로 아래 사이트의 이미지를 사용했다. https://cloudstudying.kr/lectures/138 그래서 Shift 연산이 필요하기 때문에 선형 시간 O(n) 의 시간 복잡도를 가진다. 자, 그렇다면 이제 JDK 를 까보자....