TIL (Today I Learned)

5월 18일 (수)

문제점 / 고민한 점

• 새롭게 알게 된 부분이 있는데 클래스 인스턴스를 프로퍼티로 갖고 있으면 구조체가 아닌 클래스로 선언해주어야한다는 것이다. 왜냐하면 구조체의 immutable 특성이 사라지기 때문에 클래스로 선언해주는 것이 맞다. node를 만드는 것은 참조 타입으로 구현해야 하기에 class가 맞기 때문에 LinkedList, Queue모두 class로 구현하는게 맞다. 하지만 큐의 경우 구조체의 특성을 갖는게 더 유용하기 때문에 LinkedList 보단 Array로 구현하는게 더 적합하다는 생각을 했다. 하지만 이번 프로젝트에서는 class로 구현해보려 한다.

• 시간 복잡도
  시간 복잡도라는 개념을 처음 접하게 됐다. 메서드마다 시간복잡도가 존재하는데 queue를 Array로 구현했을 때 removeFirst() 메서드를 이용할 때 처음 인덱스를 삭제하고 한 칸씩 넘겨주는 과정때문에 O(n)의 시간 복잡도를 갖게 된다. 이 부분은 시간복잡도가 O(1)인 DoubleStack 이나 Node로 연결되어 추가/삭제에 용이한 LinkedList를 이용하여 해결할 수 있다.