어레이와 링크드리스트
어레이(배열): 크기가 정해진 데이터 공간. 한 번 정해지면 바꿀 수 없음
배열은 각 원소에 즉시 접근 가능(rooms[0]): 상수 시간 내에 접근 가능(O(1))
배열은 원소를 중간에 삽입/삭제 하려면 모든 원소를 옮겨야 함. O(N)의 시간복잡도를 가짐
새로운 원소를 추가하기 위해서는, 새로운 공간을 할당해야 하므로 매우 비효율적
링크드 리스트: 연결고리로 이어져 있음. 크기가 정해지지 않은 데이터의 공간. 연결고리로 이어주기만 하면 자유자재로 늘어남
특정 원소에 접근하려면 연결 고리를 따라 탐색해야함. O(N)의 시간복잡도를 가짐.
연결 고리: 포인터
데이터 공간: 노드
원소를 중간에 삽입/삭제 하려면 앞 뒤의 포인터만 변경하면 됨. O(1)의 시간 복잡도
| 어레이 | 링크드 리스트 | |
| 특정 원소 조회 | O(1) | O(N) |
| 중간에 삽입 삭제 | O(N) | O(1) |
| 데이터 추가 | 데이터 추가 시 모든 공간이 다 차버렸다면 새로운 메모리 공간을 할당받아야 한다 | 모든 공간이 다 찼어도 맨 뒤의 노드만 동적으로 추가하면 된다. |
| 정리 | 데이터에 접근하는 경우가 빈번하다면 Array를 사용하자 | 삽입과 삭제가 빈번하다면 LinkedList를 사용하는 것이 더 좋다. |
클래스: 분류, 집합과 같은 속성과 기능을 가진 객채를 총칭
예: 클래스가 사람 -> 객체는 유재석, 박명수 등
클래스를 이용하면 같은 속성과 기능을 가진 객체를 묶어서 정의 가능