백엔드에서는 목록, 최근 항목, 작업 대기열의 접근 패턴을 먼저 보고 자료구조를 고른다.
배열
- 같은 타입의 원소를 연속된 공간에 두고 인덱스로 접근하는 구조
- 위치(인덱스)를 알면 바로 접근할 수 있지만, 중간에 값을 끼워 넣으려면 뒤쪽 원소를 이동해야 함.
동적 배열
- 내부 배열의 capacity를 가지고 있다가 공간이 부족하면 더 큰 배열을 만들고 기존 원소를 복사
- Java의 ArrayList가 이 방식
- capacity가 부족할 때마다 기존 배열을 복사해야 하므로 특정 순간엔 복사 비용이 발생.
- 사용자 목록 조회 후 인덱스로 접근하는 경우 유리
연결 리스트
- 노드가 값, 이전 노드, 다음 노드의 참조를 가짐.
- Java의 LinkedList: doubly-linked list. List, Deque, Queue 인터페이스를 구현
- 인덱스만 있는 경우 해당 위치까지 노드를 따라가야 함
- 검색보단 추가/삭제에 유리한 자료구조
- 위치를 찾는 traversal 비용이 존재 → 삽입/삭제에 무조건 유리하지 않음
ArrayDeque