SW 문제해결 기본 - List

하루입니다.

 

1차시 : List

2차시 : 삽입정렬

3차시 : 병합정렬

4차시 : List의 활용

 

 

---

 

1차시 : List

List의 특성

• 순서를 가진 데이터의 집합을 가리키는 추상자료형
• 중복 데이터 가능
• 구현 방법에 따라 순차 List(배열 기반), 연결 List(메모리의 동적할당 기반) 로 나뉨

 

 

List의 주요 함수

 

 

순차 List

구현 방법

• 1차원 배열에 항목들을 순서대로 저장한다. 
• 데이터의 종류와 구조에 따라 구조화된 자료구조를 만들어 배열로 구현할 수도 있다.
• 배열의 인덱스를 이용해 원하는 위치의 데이터에 접근할 수 있다.

 

삽입연산, 삭제연산

 

 

 

연결 List

• 단순 배열을 이용한 순차 List의 단점을 보완한 자료 구조

 

• 노드 : 연결 List에서 하나의 원소에 필요한 데이터를 갖고 있는 자료단뒤
• 데이터 필드 : 원소의 값을 저장하는 자료구조
•                       : 저장할 원소의 종류나 크기에 따라 구조를 정의하여 사용함
• 링크 필드 : 다음 노드의 주소를 저장하는 자료구조

 

• 헤드 : List의 처음 노드를 가리키는 자료구조

 

단순 연결 List

 

 

삽입연산

A, C, D를 원소로 가지고 있는 List의 두 번째에 B 노드를 삽입할 때

 

삭제 연산

 

 

이중 연결 리스트

 

 

이중 연결 리스트에서 삽입하는 과정!

 

 

이중 연결 리스트에서 삭제하는 과정!

 

 

---

 

2차시 : 삽입정렬

• 책 정렬할 때를 생각해 보자.
• 자료 배열의 모든 원소를 앞에서부터 차례대로 이미 정렬된 부분과 비교하여, 자신의 위치를 찾아냄으로써 정렬을 완성한다.

 

삽입 정렬의 정렬 과정

 

 

 

---

 

3차시 : 병합정렬

• 여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방식이다.

 

 

병합 정렬의 과정

 

 

연결리스트로 구현하면 더 효과적이다!

 

 

 

 

---

 

4차시 : List의 활용

 

ㅗ

 

 

 

우선순위 Queue