반응형

 이번 시간에는 ArrayList의 remove에 대해 알아보겠습니다.

 

 remove를 보시면, int형을 받는 것이 있고, Object를 받는 것이 있습니다. int를 wrapping한 것은 Integer입니다. auto boxing까지 생각한다면 이 둘이 헷갈릴 소지가 매우 다분합니다. 특히 Integer는 스택 오버플로우에도 꽤 많이 올라왔던 질문 중 하나였습니다. 이 기회에 정리를 해 두시는 것도 괜찮겠습니다.


 먼저 Object를 받는 remove를 알아보겠습니다.

 

 먼저, Obj를 하나 생성하였습니다. 여기에는 equals가 재정의 되어 있지 않습니다.

 

 

 저는 여기에서, "gahui"가 들어간 오브젝트를 새로 생성하였습니다. 그리고, 새롭게 생성한 "gahui" 라는 오브젝트를 li에서 제거할 건데요. 제대로 동작할까요? 그렇지 않습니다. 왜냐하면, "gahui"라는 내용은 같아 보여도 다른 객체이기 때문입니다.

 

 즉, 내용이 같더라도 다른 객체이므로, remove는 실패합니다. 실행 결과는 아래와 같습니다.

 

 

 1개를 추가했고, 0개가 제거되었으니, 1이 나오는 것은 당연한 이야기입니다. 어떻게 그러면 "gahui" 라는 내용을 가지는 객체들을 List에서 제거할까요? 답은 equals를 오버라이드 하시면 됩니다. 당연하게도, hashCode도 재정의 하는 것은 국룰이라 생각하시면 됩니다.

 


 그러면, 이 메서드의 내부를 뜯어보겠습니다.

 

 사실, 별 거 없습니다. o는 찾을 객체를 의미합니다. 그리고 elementData는 실제 데이터가 저장된 장소를 의미하는데요. index번째이니, 리스트의 전체를 순회하면서 o와 동등한지 판단합니다. 이 과정에서 equals 메소드가 들어갑니다. 예를 들어 Integer를 저장하는 ArrayList였고, Integer 10을 제거한다고 해 보겠습니다. 그러면 equals가 호출이 된 순간 아래 메서드를 실행할 겁니다.

 

 

 여기서 중요한 것은 value는 Integer 안에 있는 실제 value 값을 의미합니다. 그리고, intValue는 이 값을 리턴합니다. 즉, obj와 this가 동등하다면, 안에 들어있는 int 값도 같습니다. 더 정확히 말하면, Integer가 저장이 되어 있는 배열 리스트에서 Integer 10을 제거한다고 하면, 값 10을 가지는 Integer 객체의 최초 위치를 찾아서 그 객체를 제거합니다.

 

 

 반면에, int를 넘겨주면, index번째 원소를 제거합니다. 이는 코드를 슥 훑어봐도 알 수 있는 내용입니다.

 


 스택 오버플로우에 자주 올라오는 질문 중 하나는 Integer들을 저장한 ArrayList에서 2를 제거하려고 하는데, 왜 2번째 원소가 제거되느냐는 것입니다.

 

 위 프로그램을 실행시켜 봅시다. 그러면, 맨 앞에 있는 2가 제거될 거라는 기대와는 다르게, 3이 제거됩니다.

 

 

 이는 2가 Integer가 아닌 int로 해석되기 때문입니다. 맨 앞에 있는 2를 제거하려면 어떻게 하면 될까요?

 

 

 Integer 2를 제거한다고 명시해 주면 됩니다. 저는 새로운 Integer 객체 2를 넘겨주었습니다.

 

 

 그러면 맨 앞의 2가 하나 제거되었음을 알 수 있습니다. 물론, Integer의 valueOf를 써도 됩니다. 이것은 cache가 된 객체에 대해서 다시 object를 생성하지 않습니다.

 


List 안에 있는 10을 모두 제거하려면 어떻게 하면 좋을까요? 아래 코드를 봅시다.

 

 100만개의 10이 있습니다. 이것을 while 루프를 일일히 돌면서 remove 메서드를 호출하면 어떨까요?

 

 

 173초, 2분 53초가 걸립니다. 이는 루프마다 O(size)의 복잡도로 수행하기 때문입니다. 제거하기 전의 list 크기가 n이라고 하고, 제거해야 할 대상이 n개 있다고 하면, O(n^2)의 복잡도인 건 당연해 보입니다.

 

 

 개선책 1

 이를 개선하기 위해서는, 한 번 돌면서, 제거해야 할 것들을 무시하는 방법이 있습니다.

 

 

 그러면, 시간이 훨씬 줄어들었음을 알 수 있습니다.

 

 

혹은, 제거할 원소들을 Collection에다 넣어서 removeAll에 넘겨주는 방법도 있습니다.

반응형

댓글을 달아 주세요