배열과 리스트

전성수·2024년 4월 5일

면접 준비 해보기

목록 보기

2/5

배열과 링크드 리스트

배열과 링크드리스트는 데이터를 저장하고 관리하는데 사용되는 두 가지 기본적인 자료구조

배열과 링크드 리스트의 비교

배열

연속된 메모리 공간에 데이터를 저장
인덱스를 사용해서 원소에 빠르게 접근이 가능, O(1)의 시간복잡도.
- 인덱스 : 추가적인 쓰기 작업과 저장 공간을 활용해서 검색속도를 향상시키는 자료구조
- 인덱스를 활용하면 검색 뿐 아니라 수정, 삭제의 성능도 향상되는데 이유는 이 작업들에 항상 검색이 선행되기 때문
- 장점
  - 테이블 조회 속도 상승으로 인한 성능 향상
  - 전반적인 시스템의 부하를 줄일 수 있음
- 단점
  - 인덱스를 관리하기 위해 추가적인 저장공간이 필요
  - 검색을 자주하는 테이블에 인덱스를 거는게 좋음
  - 수정, 삭제, 입력이 잦은 테이블에 인덱스를 걸게 되면 인덱스의 크기가 비대해져서 성능이 오히려 저하됨
    - 규모가 큰 테이블
    - 입력이 자주 발생하지 않는 컬럼
    - JOIN 이나 WHERE, ORDER BY에 자주 사용되는 컬럼
    - 데이터의 중복도가 낮은 컬럼
- 인덱스는 해시 테이블이나 B+Tree로 구현함
  - 해시 테이블 기반의 DB 인덱스는 검색에 유리하지만 해시가 = 연산에 특화되었기 때문에 해시 함수의 특성상 값이 1이라도 달라지면 완전히 다른 해시 값을 생성하므로 부등호 연산이 자주 사용되는 데이터 베이스 검색에는 적합하지 않음
  - B+Tree는 리프노드만이 인덱스와 함께 value(데이터)를 가지고 있고 나머지 노드들은 인덱스만을 가지고 있음.
    - 리프노드들은 LinkedList로 연결되어 있음
    - 데이터베이스의 인덱스 컬럼은 부등호를 이용한 순차 검색 연산이 자주 발생될 수 있으므로 B+Tree의 리프노드들을 LinkdedList로 연결해 순차검색을 용이하게 하는 등 B+Tree를 인덱스에 맞게 최적화.
    - 인덱스 공부에 참고한 블로그
- 고정된 크기를 가지고 크기 변경이 어려움. 미리 할당된 메모리 크기를 초과하면 새로운 메모리 공간을 할당하고 데이터를 복사해야함.
- 원소를 삽입하거나 삭제할 때 원소들을 이동시켜야 해서 시간이 오래 걸릴 수 있음. O(n)의 시간복잡도.
- 메모리 사용이 효율적. 각 원소는 인덱스로 접근되고 추가적인 메모리를 사용하지 않음