자료구조와 알고리즘_3_선형 자료의 종류

 

[✔️자료구조 ]

 

📍선형 vs 비선형 : 

1. 선형 구조 : 

• 자료가 순차적으로 나열된 형태
• 하나의 자료 뒤엔 또다른 자료가 하나만 올 수 있다.
• 배열 / 연결 리스트 / 스택 / 큐

 

2. 비선형 구조 : 

• 자료 뒤에 다수의 자료가 올 수 있는 형태
• 트리 / 그래프

 

---

[ ✔️배열 vs 동적 배열 vs 연결 리스트 ]

배열(array), 동적 배열(vector), 연결 리스트(list)는 어떤 프로그래밍 언어든 존재하는 자료구조다.

 

📍배열 : 

• 처음 할당된 메모리 공간 크기를 변경할 수 없다.
• 연속된 메모리 공간을 활용한다. → 임의접근(Random Access,RA) 가능
• 장점 : 연속된 메모리 공간, RA
• 단점 : 메모리 공간 크기 변경 불가

 

📍동적 배열 : 

• 할당된 메모리 공간 크기 변경 가능 (유동적으로 관리)
• 연속된 메모리 공간 활용 → RA
• 장점 : 메모리 공간 유동적으로 조정가능(수용 공간 설정으로 복사비용 최소화)
• 단점 : 복사 비용, 중간 삽입/삭제

 

📍연결 리스트 : 

• 연속되지 않은 메모리 공간을 활용한다.
• 장점 : 중간/삽입 삭제가 용이함
• 단점 : 데이터가 연속된 메모리 공간에 저장되어 있지 않기에 RA 불가능

 

 

================================

개인 공부 기록용 포스팅입니다.
댓글, 질문 환영해요~!

Refer : Inflearn_C++언리얼로 만드는...Part3
================================