📌 배열(Array)
같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합이다.
- 중복을 허용하고 순서가 있다.
- 탐색 : O(1) -> 랜덤 접근(random access) 가능
- 삽입, 삭제 : O(n)
인덱스에 해당하는 원소를 빠르게 접근해야 하거나 간단하게 데이터를 쌓고 싶을 때 사용한다.
사용
- 엑셀의 스프레드시트 처럼 직사각형 테이블, 수학적 벡터 (vector) 및 행렬 (matrix)를 구현하는 데 사용된다
- 다른 데이터 구조에서 사용된다
📌 연결 리스트(Linked list)
데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료 구조이다.
종류
- 단일(Single) 링크드리스트 : 하나의 pointer를 가지며, next node만을 가리킨다.
- 이중(Double) 링크드리스트 : 두개의 pointer를 가지며 이전(prev), 다음(next) node를 가리킨다.
- 원형(Circular) 링크드리스트 : 일반적인 링크드리스트에서, 마지막 노드가 처음 노드를 가리킨다.
- 탐색 : O(n)
- 삽입, 삭제 : O(1)
사용
- 메모리 크기가 정해져 있지 않을 때
- 데이터를 연속적으로 빠르게 삽입/제거가 필요 할 때
- 이미지 뷰어, 갤러리
- 음악 플레이어
📌 배열과 연결 리스트 비교
-
배열은 순서대로 나열한 데이터 구조이며 몇 번째인지만 알면 해당 요소를 알 수 있다. -> 랜덤 접근이 가능 O(1)
-
연결 리스트는 선으로 연결된 형태의 데이터 구조이며 요소를 알기 위해서는 하나씩 확인해봐야한다. -> 랜덤 접근이 불가능 O(n)
탐색 : 배열이 더 빠름
삽입, 삭제 : 연결 리스트가 더 빠름
