배열
- 배열: 일정한 메모리 공간을 차지하는 여러 요소들이 순차적으로 나열된 자료 구조
- 접근 속도: O(1)
- 검색 속도: O(n)
- 특정 요소 추가, 삭제 속도: O(n)
연결 리스트
- 노드의 모음으로 구성된 자료 구조
- 모든 노드들이 한 쪽 방향으로 꼬리에 꼬리를 무는 형태
- 연속적으로 구성되어 있는 데이터를 불연속적으로 저장할 때 유용
- 접근 속도: O(n)
- 추가, 삭제 속도: O(1), 재정렬이 불필요
- 싱글 연결 리스트: 단방향 리스트로 다음 노드의 위치만 알 수 있고 이전 노드의 위치는 알 수 없다
- 이중 연결 리스트: 이전 노드의 위치 정보도 포함
- 원형 연결 리스트: 꼬리 노드가 헤드 노드를 가리켜 원형으로 구성됨, 이중 연결로도 구성 가능
