리스트
- 순서 또는 위치를 가진 항목들이 차례대로 저장되어 있는 자료구조
- 삽입 연산, 삭제 연산, 탐색 연산 등 기본적 연산 가능
- 집합은 항목 간에 순서의 개념이 없으므로 집합과는 다름
리스트 ADT
리스트의 구현
- 배열 또는 연결 리스트를 이용하여 리스트 구현 가능
1. 배열을 이용한 구현
- 구현이 간단하고 속도가 빠름
- 리스트의 크기가 고정되므로 동적으로 크기를 조절하는 것이 어려움
- 더 큰 배열을 만들어 기존 배열의 데이터를 복사하는 식으로 해결 가능하지만 CPU 시간이 낭비됨
- 리스트 중간에 새로운 데이터를 삽입하거나 삭제하기 위해 기존 데이터들을 이동해야 함
2. 연결 리스트를 이용한 구현
- 크기 제한이 없음
- 리스트 중간에서 쉽게 삽입하거나 삭제할 수 있음
- 구현이 복잡
- 임의의 i번째 항목을 추출하려 할 때 배열을 사용하는 방법보다 시간이 더 오래 걸림
