List
2019. 02. 27 (Wed)
순서를 가진 데이터의 집합
데이터 중복 가능
I. 주요 연산
addToFirst(): 리스트 앞쪽에 원소 추가
addtoLast(): 리스트 마지막에 원소 추가
add(index): index 위치에 원소 추가
delete(index): index 위치의 원소 제거
get(index): index 위치 원소 반환
II. 구현 방법
1. 순차 리스트
배열기반
삽입, 삭제 연산시 원소를 옮겨야 해서 연산 시간이 많이 걸린다
- O(n)
삽입, 삭제 연산이 빈번한 상황에 부적절
index기반 원소 접근이 빠름
- O(1)
크기가 제한적이고, 원소의 변경이 없을 때 유리
2. 연결 리스트
메모리 할당기반, 원소를 연결
삽입, 삭제 연산이 빠르다
- 탐색은 원소 옮기는 것 보다 빠르다
자료의 크기 동적으로 조정. 메모리 효율적 사용 가능
원소의 변경이 많을 때 유리
(1) 기본 구조
노드
- 데이터 필드: 원소의 값을 저장
- 링크 필드: 다음 노드의 주소를 저장
헤드
- 리스트의 처음 노드
III. 적용 예시
1. 삽입 정렬
정렬된 부분, 정렬되지 않은 부분으로 나눠서 정렬
뒤에서부터 정렬된 내용들과 비교하며 자기보다 원소가 클 때 까지 들어가기
원소를 순차적으로 정렬된 부분에 넣기
연결 리스트를 사용하면 빠르다
2. 병합 정렬
별도의 배열에 담아가며 정렬
배열을 2개 부분으로 나눈 후 각각을 정렬하여 합침
(1) 정렬 과정
- 분할: 전체 자료를 1개의 자료가 될 때 까지 2개로 분할
- 병합: 2개의 부분집합들을 합치면서 정렬
- 왼쪽, 오른쪽 부분으로 나뉜 배열을 원소를 비교하며 새로운 배열에 삽입
- 연산 후에도 원소가 남아있는 경우에는 새로운 배열 뒤에 이어붙이기
3. 우선순위 큐
연결 리스트를 사용하여 우선순위 큐 구현