백준 2346번 문제풀다가 ArrayDeque 자료구조를 보고 굉장히 놀랬음..
당연히 LinkedList를 사용해서 푸는 문제일거라고 생각했는데 메모리 초과가 발생했다.
그래서 정답을 찾아보니 ArrayDeque을 쓰신 분들이 있어서 고쳤는데 바로 정답이 되었다.
그래서 LinkedList와 ArrayDeque은 도대체 어떤 차이점이 있을까 궁금해서 이 글을 쓰게 되었다.
혹시나 위 문제를 풀어보지 않은 분들은 꼭 한번 풀어보길 추천한다.
어떤 구조일까
내가 머리속으로 대충 생각하던 그림은
이런 그림이었다. 근데 전혀 아니었음
그럼 LinkedList를 한번 들어가보자 Ctrl + 클릭해서 들어가보면
LinkedList는 Deque와 List 인터페이스의 구현체였다..
그리고 Deque를 다시 Ctrl + 클릭해서 들어가보면
Deque는 또 Queue를 상속받네? 그럼 Queue는?
Queue는 다시 Collection을 상속받는다.
오랜시간 자바를 사용해왔지만 이런 구조라고는 생각하지 못한 내가 한심했다..
그럼 이번에는 List 는 어떻게 되어있나 궁금했다.
List는 Collection을 상속받고 Collection은 Iterable을 상속받는 구조로 되어있었다.
그럼 Collection은 Iterable 한테 어떤걸 상속받는가 가장 근본적인걸 상속받겠지? 생각했는데 바로 요소 순회였다.
Collection 에서는 순회를 바탕으로 가장 근본적인 삽입, 삭제 등등 여러 메소드가 있었다.
그리고 List 또한 interface 이므로 Collection 의 삽입 삭제를 Overload하여 더 세부적인 기능을 만들고 더불어 다른 메소드가 몇개가 추가된다.
찾아보니까 sort(), replaceAll() 메소드가 좀 추가된 것 같다.
자료구조 공부가 꼭 필요한 이유를 알게되었다..
다음에는 Set하고 Map도 한번 보는걸로!
그리고 위에 사진을 다시 정리하자면 사실 위에서는 일직선으로 순서로 표현했지만 implements와 extends 특성상 계층이라고 표현되는 것이 더 올바르다.
