컬렉션 클래스들(자료구조)의 구조를 시간 복잡도 관점에서 분석해보자

[charlesuu]

(자바의 정석에 메서드들의 시간 복잡도 관련 내용이 한 번에 정리되어 있지 않아서 정리할겸 이슈 올립니다)

각각의 컬렉션 클래스들은 데이터를 검색, 삽입, 삭제 할 때 시간 복잡도가 다릅니다. 내부 구현이 다르게 되어있기 때문입니다. 컬렉션 클래스 내부 구조를 보면서 이들의 시간 복잡도가 형성된 이유를 공부해보면 좋겠습니다. 컬렉션 클래스들을 좀 더 이해하고, 각 클래스의 구현에 쓰인 아이디어를 알아두면 도움이 될 것이라고 생각합니다.

[charlesuu]

( 예를 들어 아래 같은 방식으로 가볍게 정리해보면 좋겠습니다. ) (Linked List 첫 번째 변수에 null들어간건 실수입니다ㅜㅜ head포인터의 주소가 들어가 있어야합니다.)

[ArrayList] 와 [LinkedList]는 둘 다 List인터페이스를 구현하고 있습니다. 그로 인해 사용시에는 매우 비슷한 컬렉션으로 보입니다. 그러나 데이터를 삽입, 삭제할 때의 시간 복잡도는 O(n)대 O(1)로 굉장히 큰 차이가 납니다.
이는 두 컬렉션 클래스의 내부구현이 다르기 때문입니다. ArrayList는 배열과 비슷하게 모든 데이터를 메모리 블럭 한 공간에 저장합니다. 반면 LinkedList는 모든 데이터가 분산 되어있고 하나의 데이터가 다음 데이터의 주소를 참조하는 식으로 구현되어있습니다. 때문에 삽입, 삭제시에 메모리 블럭 공간을 늘리거나, 다른 데이터를 한 칸씩 뒤로 밀고 당기는 연산을 할 필요가 없습니다. 데이터들이 참조하는 주소만 조금씩 바꾸어 주면 됩니다.

(참고하면 좋을 블로그 : https://www.nextree.co.kr/p6506/)

[anthologia]

앗 ㅎㅎㅎ 저도 이 내용 정리해봤는데 넘 좋네용

[charlesuu]

댓글 하나씩 추가해가면서 컬랙션 프레임워크 정복 가시져!!

[anthologia]

@songks0922, @charlesuu head 앞에는 왜 null이 들어가야 하나요?

[charlesuu]

@anthologia null이 아니라, 첫 노드의 주소가 들어가 있어야하는데 만들다가 실수했습니다ㅜㅜ

[charlesuu]

@anthologia 스터디 중에 첫 노드 전에 참조 변수가 꼭 와야 하는가에 대한 논의가 있었는데요. 조사해보니 꼭 그래야하는 것은 아니고 구현하는 사람 마음이라고 합니다. 참조 변수를 따로 두는 경우 LinkedList 안에 노드가 하나도 없는 경우를 판단하는 코드가 단순해져서 종종 그렇게 구현한다고 합니다.

[charlesuu]

@anthologia 자바 컬렉션 프레임워크의 링크드 리스트는 참조 변수 없이 노드로만 구현되어 있네요.

참고로 링크드리스트.add() 하면 호출되는 함수인 linkLast()는 이렇게 구현 되어 있습니다. 맨 앞, 맨 뒤 노드를 관리해주고 있고, Node 매개변수를 보니 이중연결리스트네요.)