Array(배열)
Array란?
고정된 크기를 갖는 같은 자료형의 원소들이 연속적인 형태로 구성된 자료구조
- 배열 안의 데이터들은 같은 자료형으로 나열되어 있음
- 데이터가 연속된 메모리 공간에 순차적으로 저장
- 따라서 배열의 논리적 순서(인덱스)와 원소값의 물리적인 순서(메모리 주소)가 동일함
장점
- 인덱스를 가지고 있기 때문에, 탐색이 빈번한 경우 효율적
- 연속된 메모리 공간에 존재하기 때문에 관리가 수월
단점
-
삽입/삭제가 어렵다
- 삽입/삭제는 해당 위치에서 작업 후, 해당 원소 뒤의 모든 원소들을 이동(shift)시켜야 하기 때문
-
배열은 처음 생성할 때 크기를 선언하면, 그 크기를 변경할 수 없음
시간 복잡도
삽입/삭제
- 배열의 맨 앞에 삽입/삭제: O(n)
- 배열의 맨 뒤에 삽입/삭제: O(1)
- 배열의 중간에 삽입/삭제: O(n)
탐색 및 수정: O(1)Linked List
링크드 리스트란?
노드를 연결해 데이터를 적재하는 자료구조
- 배열의 문제점을 해결하기 위한 자료구조
- 인덱스가 없음
- 불연속적인 메모리 공간에 원소와 다음 노드의 주소를 가진 노드가 계속해서 이어져 있어 선형의 형태를 유지
장점
- 삽입/삭제 시 전후 노드의 참조관계만 수정하면 되기 때문에 효율적
- 크기가 가변적
- 메모리 낭비가 적다
- 연속적으로 메모리를 할당할 필요가 없어서 메모리 낭비가 적음
- 메모리 재사용 가능 (삭제 시 해당 노드의 참조가 사라져 GC에 의해 가용 메모리로 전환)
단점
- 구현이 상대적으로 복잡하다
- 인덱스 탐색이 안되기에 탐색이 비효율적이다 (처음부터 순차적으로 검색해야함)
- 다음 노드의 주소를 저장하는 메모리 추가적으로 필요
시간 복잡도
삽입
- 리스트의 맨 앞에 삽입: O(1)
- 리스트의 중간에서 삽입: O(n)
삭제
- 리스트의 맨 뒤에 삽입/삭제: O(1)
- 리스트의 중간에서 삭제: O(n)
탐색: O(n)리스트의 다양한 종류
- 단일 연결 리스트(Single Linked List)
- 이중 연결 리스트(Double Linked List)
- 원형 연결 리스트(Circular Linked List)
- 순환 이중 연결 리스트(Dobuly Circular Linked LIst)
참고
[ 자료구조 ] 배열(Array) vs 리스트(List) - 특징, 차이
