지난 글에서는 MyArrayList와 MyLinkedList를 직접 구현해보았다. 단순히 구현해보는 것만으로는 부족하다. 실제로 얼마나 성능 차이가 나는지, 자바는 왜 더 빠른지, 구조가 어떻게 다른지까지 알아야 진짜 실력을 키울 수 있다. 이번 글에서는 직접 구현한 리스트와 자바의 ArrayList, LinkedList를 비교 실험을 통해 차이점과 이유까지 하나하나 풀어본다. 1. 자바의 List는 인터페이스이다먼저 개념부터 잡고 가자.자바에서 List는 인터페이스(interface) 이다. 즉, 기능의 틀만 정해놓고, 실제 구현은 하지 않은 것이다. List는 순서가 있는 데이터를 저장하고 중복을 허용하는 자료 구조이며, 대표적인 구현체는 아래와 같다:List arrayList = new ArrayL..

자바에서 배열은 가장 손쉽게 데이터를 담는 방법이다. new String[5]처럼 선언 한 번으로 바로 메모리를 잡아주고, arr[2]로 빠르게 요소를 꺼낼 수 있다. 그러나 실제 서비스 규모가 커지면 배열의 한계가 금세 드러난다. 예를 들어 주문 내역을 배열에 담아 관리한다고 가정하자. “최대 10만 건”이라 미리 크기를 잡아두었는데, 주문량이 15만 건으로 늘어나면 새 배열을 만들고 기존 데이터를 전부 복사해야 한다. 이 과정은 O(n)의 시간이 들기 때문에, n이 커질수록 서버 부담이 커진다. 반대로 주문량이 적으면 사용되지 않는 공간이 낭비된다. 중간에 어떤 주문을 삭제해야 할 때는 그 뒤의 모든 요소를 한 칸씩 앞으로 당겨야 한다. 천만 건 단위라면 삭제 한 번에 천만 번 이상의 대입 연산이 발..