해설 — StringBuilder 의 내부 구조와 성장

난이도: 중

요약

StringBuilder 는 하나의 커다란 버퍼가 아니라 char 청크(char[])들의 연결 리스트다 (.NET Core 기준). 각 청크는 이전 청크를 가리키고, 최신 데이터는 마지막 청크에 있다. Append 는 현재 청크에 쓰고, 가득 차면 새 청크만 할당해 연결한다 — 매번 전체 버퍼를 재할당·복사하는 순진한 문자열 결합의 O(n^2) 를 피한다.

실행 결과(예측)

10
ababababab
>>ababababab
>

핵심 개념 / 단계별

• 내부 구조(청크 연결 리스트): 각 StringBuilder 인스턴스는 현재 청크의 char[] 와 "이전 청크" 참조를 갖는다. 논리적 문자열은 (이전 청크들 …) + (현재 청크)의 연결이다. 마지막 청크가 tail 이며 Append 는 여기에 쓴다.
• Append 가 재할당을 피하는 법: 현재 청크에 여유가 있으면 그 자리에 복사한다. 여유가 없으면 새 청크(대개 기존 용량을 배로 늘린 크기, 필요분 이상) 를 만들어 현재 청크로 삼고 이전 청크로 링크한다. 기존 데이터는 복사하지 않는다(옛 청크를 그대로 두고 링크만 함). 그래서 총 Append 비용이 분할상환 O(1) 이다.
  • 대조: s = s + "x" 반복은 매번 새 문자열 전체를 복사해 O(n^2).
• 연산별 복잡도:
  • Append(끝에 추가): 분할상환 O(1).
  • 중간 Insert/Remove: 삽입 지점 이후를 옮겨야 하고 청크 분할/이동이 필요 → 최악 O(n)(예제의 Insert(0, ">>") 는 앞쪽 삽입이라 청크 조정 발생).
  • 인덱서 sb[i]: 원하는 위치의 청크를 찾으려 청크 리스트를 순회할 수 있어 문자 하나 접근이 O(청크 수)까지. 문자 단위 루프에서 sb[i] 를 쓰면 느리다.
  • ToString(): 전체 길이의 단일 string 을 만들어 모든 청크를 복사 → O(n) 할당·복사.
• 출력 해설: 5회 Append("ab") → 길이 10, 내용 ababababab. Insert(0,">>") 로 앞에 >> 가 붙어 >>ababababab. sb[0] 는 첫 문자 >.

흔한 오해·함정

• ToString() 을 루프 안에서 반복 호출하면 매번 O(n) 문자열을 새로 만들어 이득이 사라진다. 최종에 한 번만 호출.
• 인덱서로 문자 순회는 청크 순회 비용 때문에 느릴 수 있다. 대량 처리엔 ToString() 후 string/Span<char> 로 다루거나 GetChunks() 로 청크 단위 처리.
• Capacity 튜닝: 최종 크기를 대략 알면 new StringBuilder(capacity) 로 초기 청크를 크게 잡아 청크 할당 횟수를 줄인다. 반대로 과도하게 크게 잡으면 메모리 낭비.
• 작은 결합에는 오히려 손해: 두세 개 문자열은 +/string.Concat/보간이 더 싸다. StringBuilder 는 반복/누적 결합에서 이득.

면접 포인트

• 청크 연결 리스트 구조 → Append 분할상환 O(1), 전체 재할당 회피.
• 인덱서/중간 삽입의 숨은 비용(청크 순회/이동), ToString 의 O(n) 복사.
• Capacity 초기값 튜닝의 트레이드오프와 "작은 결합엔 +가 낫다".