요구사항 정리

• 새로운 채팅 메시지 수신: roomId를 확인하여 채팅방 목록에 해당 roomId가 있는지 찾는다.
• 기존 채팅방이 있을 경우: 해당 채팅방을 목록에서 최상단으로 올리고, 채팅방 정보를 업데이트한다.
• 새로운 채팅방일 경우: 새로운 채팅방을 생성하여 목록의 최상단에 추가한다.

고려했던 자료구조

• List, LinkedHashMap

1. List

• 구조: 단순한 순차 배열로, 각 채팅방을 List의 요소로 관리
• 장점: 배열 형태로 접근이 간단하며, List 자체가 MutableStateFlow와 잘 어울림
• 단점: 특정 roomId를 찾을 때 O(n)의 시간 복잡도가 발생. 채팅방을 최상단으로 옮기려면, 요소를 삭제하고 다시 삽입해야 하므로 비효율적일 수 있음. (불변 리스트 + 불변 리스트거나 가변 리스트에 새로운 주소값을 할당시켜 리컴포지션을 야기하려면 O(N)의 시간복잡도가 들어감)

2. LinkedHashMap

• 구조: roomId를 키로 하고, 채팅방 데이터를 값으로 가지는 LinkedHashMap을 사용.
• 장점: 키를 통해 O(1) 시간 복잡도로 특정 채팅방을 찾을 수 있음. 새로운 채팅방을 추가하거나 기존 채팅방을 최상단으로 이동할 때에는 LinkedList의 성질을 이용하면 O(1)의 순서로 조정할 수 있음.
• 단점: 이를 MutableStateFlow로 사용하려면 List로 변환해야 함. (O(N))

결론

• 어차피 리컴포지션을 야기하려면 List나 LinkedHashMap이나 둘다 O(N)은 불가피함.
• O(1)로 특정 채팅방을 찾을 수 있고, 채팅방을 생성하거나 제거할 때 O(1)로 수행가능한 LinkedHashMap이 더 적합할 것이라고 판단.