[자료구조] 배열, 동적 배열, 연결 리스트, ArrayDeque

자료구조 | Notion

자료구조

백엔드에서는 목록, 최근 항목, 작업 대기열의 접근 패턴을 먼저 보고 자료구조를 고른다.

배열

• 같은 타입의 원소를 연속된 공간에 두고 인덱스로 접근하는 구조
• 위치(인덱스)를 알면 바로 접근할 수 있지만, 중간에 값을 끼워 넣으려면 뒤쪽 원소를 이동해야 함.

동적 배열

• 내부 배열의 capacity를 가지고 있다가 공간이 부족하면 더 큰 배열을 만들고 기존 원소를 복사
• Java의 ArrayList가 이 방식
• capacity가 부족할 때마다 기존 배열을 복사해야 하므로 특정 순간엔 복사 비용이 발생.
• 사용자 목록 조회 후 인덱스로 접근하는 경우 유리

연결 리스트

• 노드가 값, 이전 노드, 다음 노드의 참조를 가짐.
• Java의 LinkedList: doubly-linked list. List, Deque, Queue 인터페이스를 구현
• 인덱스만 있는 경우 해당 위치까지 노드를 따라가야 함
• 검색보단 추가/삭제에 유리한 자료구조
• 위치를 찾는 traversal 비용이 존재 → 삽입/삭제에 무조건 유리하지 않음

ArrayDeque

• 양쪽 끝에서 삽입 가능
• addFirst(), pollFirst()는 head/tail 위치를 움직여 큐 연산을 처리
• Java에서 ArrayDeque는 deque 구현으로 제공. 단순 스택/큐에는 Stack보다 ArrayDeque를 우선 고려

Stack 자료구조가 비효율적인 이유

• 최근 N개의 데이터 저장에 유리: 앞에서 제거하고 뒤에서 추가하는 과정이 반복
• 순수 배열 기반 원형 버퍼라 오버헤드가 적다
  • 원형 버퍼: 배열 끝까지 갔으면 다시 처음 칸으로 돌아가서 재사용하는 배열. 큐에서 앞 원소를 제거할 때 인덱스를 하나씩 당길 필요가 없이, tail값만 바꿔주면 된다. O(N) 시간복잡도에서 O(1) 시간복잡도로 단축된다.
  • ArrayDeque가 스택/큐 다 성능이 좋은 이유는 앞뒤 삽입/삭제를 포인터(head/tail)만 움직여서 처리하기 때문이다.

LIFO, FIFO

• 스택은 LIFO, 큐는 FIFO
• 덱(deque)은 양쪽 끝에서 삭제와 삽입이 가능해 스택과 큐를 모두 구현할 수 있다.