리스트에서 원소 삭제

A quick summary of 리스트에서 원소 삭제

리스트에서 원소 삭제

인터뷰 문제로 물어볼법한 내용은 아니다. 하지만 매우 초보적인 실수를 막기 위해 언급한다.

문제 배경

대부분의 코딩 인터뷰는 열거형 데이터를 다루게 된다.
LINQ 등을 활용할 수 있는 현실 코딩과 달리, 제한 시간 동안 구현하는 경우 인덱스를 직접 다루게 될 확률이 높다.

그런데 배열과 달리 리스트는 원소를 삭제하는 순간 자동으로 Trim이 일어난다.

따라서 어떤 리스트에서 2,3,5 번 원소를 삭제할때 다음과 같은 코드를 실행하게 되면 두가지 문제가 생긴다.

for(var i = 0; i < list.Count; i++) {
    if(i == 2 || i == 3 || i == 5) {
        list.RemoveAt(i);
    }
}
  • 원소가 삭제될때 마다, 해당 원소 이후의 원소들은 인덱스가 한칸씩 왼쪽으로 Shifting 된다.
    • 따라서 위 코드는 2, 3, 5가 아니라, 2, 4, 7 번 원소를 삭제하려 시도하게 된다.
  • for 문 조건으로 사용한 Count의 값이 계속 감소한다.
    • 따라서 위 코드는 본래 의도된 횟수보다 적은 횟수의 루프를 실행한다.

또한 이것은 foreach 문을 사용해서 순번 기반이 아닌 값 비교로 원소를 삭제해도 같은 현상을 일으킨다.

형편없는 해결법

결론적으로 문제는 전체 인덱스가 감소하는 것이다.

첫번째 방법

이 문제를 해결하는 형편없는 방법 중 하나는, 전체 인덱스를 루프전 별개의 변수로 저장하는 것이다.
그런 다음, 원소를 삭제할때 마다 인덱스 shifting을 고려해서 다음 원소를 좀더 앞당겨 삭제하는 것이다.

int count = list.Count;

위 방식은 여전히 삭제한 원소들의 갯수에 대한 기억이 필요하므로 코드가 매우 더러워진다.

두번째 방법

전체 리스트를 크기가 변하지 않는 배열로 임시 변환해서 사용한다.

var convertedArray = list.ToArray();

for(var i = 0; i < convertedArray.Length; i++) {
    if(i == 2 || i == 3 || i == 5) {
        convertedArray[i] = null;
    }
}

list = new List(convertedArray);
list.RemoveAll(null);

하지만 위 문제는 불필요한 보일러플레이트 코드와 형편없이 많은 레퍼런스와 값 복제를 일으킨다.

제대로된 해결법

두가지 현상을 이용하면 간결하게 처리할 수 있다.

전체 원소를 지우면 마지막 원소의 인덱스는 변하지만, 첫 원소의 인덱스 0은 변하지 않는다.
인덱스 쉬프팅은 원소를 삭제한 지점에서 오른쪽 원소들에게 일어난다.

예를 들어 3번 원소를 삭제하면, 3번 이후의 원소들이 한칸씩 앞당겨지지만, 반대로 3번 이전의 원소들은 쉬프팅이 되지 않는다.

위 두 현상을 결합하면 다음 결론이 나온다.

마지막 인덱스에서 첫번째 인덱스 방향으로 순회하면서 원소를 삭제한다.

따라서 다음 코드로 원소를 삭제한다.

for(var i = list.Count-1; i >= 0; i--) {
    if(i == 2 || i == 3 || i == 5) {
        list.RemoveAt(i);
    }
}

foreach 문으로 작성하면 다음과 같이 거꾸로 방향으로 순회하여 적용할수 있다.

foreach (var item in list.Reverse()) {
    if(IsRemoveTarget(item)) {
        list.Remove(item);
    }
}

부록 : 또다른 트릭

대부분의 경우에 적용할 수 있는 다음과 같은 트릭도 있다.
간결하지만, C#만의 트릭인지는 확인 필요.

  • C# Collection 타입의 내장된 기능 사용
list.RemoveAll(item => item.Value == someValue);
  • list의 복제본을 하나더 만들어 순회하는 방법 (정확하게는 복제본이 아니라 레퍼라서 성능 이슈 적음)
 foreach (var item in list.ToList()) {
     list.Remove(item);
 }