자료구조 #List

List

 

1. Array List

- 크기가 가변적으로 변하는 선형리스트

- 인덱스로 내부의 객체를 접근

- 용량이 부족하다면 용량이 늘어난다.

 

1-1) Static Array

- 저장공간이 고정됨.

- 순차적으로 저장됨

 

1-2) Dynamic Array

- Static Array의 단점을 보완하여, 용량이 부족할 시 용량을 늘리는 Array

- 보통 기존 크기의 2배로 늘리지만 일정 크기부턴 정해진 크기만큼만 늘어난다.

- Static Array를 보완한 것이기 때문에 Dynamic Array 또한 Static Array로 이루어져 있다.

 

2. Linked List

- 노드와 다음 데이터의 주소 값이 저장된 포인터가 저장된 형태의 리스트이다.

- 크기가 정해져 있지 않은 동적 자료구조이다.

 

- 장점

• 데이터 추가, 삭제가 용이
• 비연속적이기 때문에 메모리 효율이 높음

- 단점

• 다음 노드의 주소값을 가지고 있는 포인터의 저장공간 때문에 추가적인 메모리가 필요함
• 탐색에 비교적 더 많은 시간이 걸림
• 알고리즘 구현이 쉽지 않음