📌 배열(Array)
특징
논리적 저장 순서와 물리적 저장 순서가 일치하는 자료구조. 따라서 인덱스(Index)로 해당 원소에 접근할 수 있으며 Random Access가 가능합니다. 하지만 삽입/삭제 시 해당 원소에 접근하여 작업을 완료한 후 빈 공간이 생기지 않도록 shift 해줘야 하므로 O(N)의 시간이 소요됩니다.
장점 ⭕️
논리적 저장 순서 = 물리적 저장 순서
메모리상에서 원소들이 연속적으로 붙어있어 인덱스 값을 이용하여 랜덤 접근(Random Access)이 가능
단점 ❌
삽입/삭제가 번거로움
초기에 배열의 크기를 지정해야 하며, 고정적이고 변경할 수 없음
📌 동적 배열(Dynamic Array)
특징
배열과는 조금 다르게 동적 배열의 크기를 유동적으로 할 수 있고 메모리상에서 원소들이 연속적으로 붙어있어 인덱스 값을 이용하여 랜덤 접근(Random Access)이 가능합니다.
장점 ⭕️
배열의 크기가 유동적
메모리상에서 원소들이 연속적으로 붙어있어 인덱스 값을 이용하여 랜덤 접근(Random Access)이 가능
단점 ❌
삽입/삭제가 번거로움
📌 연결 리스트(Linked List)
특징
어떠한 노드가 데이터와 다음 노드에 대한 주소 정보(포인터)를 가지고 노드들끼리 순차적으로 연결되어 있는 방식의 자료구조 입니다.
장점 ⭕️
삽입/삭제가 빠름
필요할 때 크기를 늘리거나 줄일 수 있어 메모리 관리가 효율적
연속된 메모리 공간이 필요 없음
단점 ❌
메모리 연속성을 가지지 않기 때문에 랜덤 접근(Random Access)이 불가능
검색 시 반드시 처음 노드부터 순차적으로 순회해야 합니다.
📌 시간 복잡도 비교
📚 정리
데이터 접근(탐색, 조회)이 빈번할 경우 => Array
데이터 수정(삽입, 삭제)이 빈번할 경우 => Linked List
'CS지식 > 자료구조' 카테고리의 다른 글
| [자료구조] 스택(Stack)과 큐(Queue) (0) | 2023.02.21 |
|---|---|
| [자료구조] 자료구조 (Data Structure) (0) | 2023.02.21 |
| [Python 자료구조] 큐 (Queue) (0) | 2023.02.20 |
| [Python 자료구조] 스택 (Stack) (0) | 2023.02.20 |
