728x90
Array vs Linked List
Data Structure 첫 번째 스터디 : Array와 Linked List
Array(배열) 기본 개념
- 인덱스를 사용하여 접근이 가능한 메모리 상에 데이터를 연속하게 배치한 자료구조
- 논리적 저장순서와 물리적 저장순서 일치 → 검색 시 용이
- 데이터 자료형들이 모두 동일
- 연속적인 메모리 공간 → 메모리 공간 활용에 제약 (초기에 할당 후에는 크기 불변)
- [종류] 다양한 차원의 배열을 가질 수 있음 (1차원, 2차원, 3차원 등)
- [특징 1] 검색 : 인덱스를 사용하여 빠르게 접근 가능! → O(1)
- [특징 2] 삽입/삭제 : 끝 부분을 제외한 임의의 원소에 접근하여 shift 한뒤 작업해야 하므로 → O(n)
Linked List(링크드리스트) 기본 개념
- 노드(데이터, 링크)로 구성되어 있어, 링크에 다음 데이터의 주소를 가리키고 있는 자료구조
- 논리적 저장순서와 물리적 저장순서 다름 → 검색 시 불편
- 사용자는 제일 첫 번재 노드의 위치만 알고 있음
- 일반적인 링크드 리스트에서 리스트의 처음은 Head, 끝은 Tail이라고 부름
- [종류] 링크드리스트(단일연결리스트), 이중연결리스트, 원형연결리스트, 다중연결리스트
- [특징 1] 검색: 원소를 찾기 위해 리스트를 순회해야하므로 → O(n)
- [특징 2] 삽입/삭제: 임의의 원소를 찾기 위해 순회 후 작업을 수행하므로 순회로 인해 → O(n)
Array와 Linked List의 비교
| 데이터 검색 | 인덱스 이용 → O(1) | 전체 순회 필요 → O(n) |
| 데이터 삽입 | Shift 필요 → O(n) | 삽입할 위치 찾기 → O(n) |
| 데이터 삭제 | Shift 필요 → O(n) | 삽입할 위치 찾기 → O(n) |
| 메모리 할당 | 정적메모리할당 (CompileTime에 할당) | 동적메모리할당 (RunTime에 할당) |
Array의 활용 (접근 유용)
- 불규칙한 정보의 저장
- 재사용할 정보의 저장
- 작업 결과 저장
Linked List의 활용 (삽입/삭제 유용)
- 배열의 한계를 극복하기 위해
- 삽입/삭제가 빈번한 경우 사용하기 위해
- 커널 모드 프로그래밍에서 사용(빠른 데이터 처리 - 삽입/삭제)
728x90
