리스트(List)
개념 간단 - 사용 편한 - 소스 구현 쉬움 - 제일 먼저 다루는 부분
자료를 순서대로 저장 - 구현의 편의성
다른 자료구조 구현의 수단으로도 사용 - 복잡한 자료구조를 구현하기 위해 내부적으로 리스트 사용
배열 리스트
배열을 이용해 구현된 리스트
//자료를 저장할 때 가장 많이 사용하는 방법은 자료를 순서대로 저장하는 것 근데 이게 리스트라는 자료구조니까 많이 사용
주의할 점)
리스트는 '한 줄'로 저장 (선형구조)
한 줄로 줄을 세우기 때문에 앞 항목과 뒤 항목이 모두 1개
1번째 - 2번째 - 3번째 순으로 연결
배열과 배열 리스트
배열 : 같은 자료형의 데이터가 메모리 상에 연속적으로 저장되는 자료형
배열 리스트 : 자료가 일직선으로 서로 연결
배열이 메모리 상에 연속적으로 저장된다는 특징 때문에 배열을 이용한 리스트를 구현하기 편리함
자료형(data type) : 데이터의 종류
자료형 선택 시 연산도 고려할 요소
추상 자료형(Abstract Data Type, ADT)
추상적, 수학적으로 자료형을 정의한 것
자료구조는 추상 자료형을 프로그래밍 언어로 구현한 것
ADT가 구현될 때 보통 구현 세부 사항의 외부에 저희가 알리지 않고 외부와 인터페이스만 공개, ADT 사용자는 구현 세부사항이 아니고 인터페이스만 사용해서 추상자료형 구현 방법은 언제든지 안전하게 변경 가능
인터페이스만 지켜진다면 ADT가 다양하게 여러가지 방법으로 구현 됨 - 정보 은닉 기본적 개념이기도 함.
추상자료형과 TV의 유사성
| TV | 추상 자료형 (ADT) |
| - TV의 인터페이스가 제공하는 특정 작업만 할 수 있음(채널 돌리거나 음량 조절 등) - 사용자는 TV의 특정 작업들을 이해하고 사용해야 함 - TV 내부에서 무엇이 일어나고 있는지를 몰라도 이용할 수 있음- - 누군가가 TV 내부의 기계장치를 교환한다고 하더라도 인터페이스만 바꾸지 않는 한 그대로 사용 가능 |
- ADT가 제공하는 연산만을 사용할 수 있음 - ADT가 제공하는 연산들을 사용하는 방법을 알아야 함 - ADT 내부의 데이터를 접근할 수 없음 - ADT가 어떻게 구현되는지 모르더라도 ADT는 사용할 수 잇음 - 다른 사람이 ADT의 구현을 변경하더라도 인터페이스가 변경되지 않으면 사용자들은 여전히 ADT와 같은 방식으로 사용할 수 있음 |
리스트 소개
리스트에서의 기본적인 연산 : 새로운 항목 추가(add), 항목 삭제(delete), 특정한 값 가져오기(get)
리스트가 사용되는 시나리오 살펴보기
- 새로운 자료 추가
- 값 가져오기
- 기존 자료의 제거
리스트 ADT
리스트를 추상 데이터 타입으로 정의한 것
1. insert(list, pos, item) ::= pos 위치에 요소를 추가
2. insert_last(list, item) ::= 맨 끝에 요소를 추가
3. insert_first(list, item) ::= 맨 처음에 요소를 추가
4. delete(list, pos) ::= pos 위치의 요소를 제거
5. clear(list) ::= 리스트 전체를 삭제
6. get_entry(list, pos) ::= pos 위치의 요소를 반환
7. get_length(list) ::= 리스트의 길이를 반환
8. is_empty(list) ::= 리스트가 비었는지 검사
9. is_full(list) ::= 리스트가 다 찼는지 검사
10. print_list(list) ::= 리스트의 모든 요소 표시
리스트 구현
배열을 이용한 구현 : 리스트 ADT를 가장 간단하게 구현할 수 있지만 크기가 고정되는 단점이 있음
연결 리스트를 이요한 구현 : 포인터를 이용해 연결 리스트를 만듬
'자료구조' 카테고리의 다른 글
| [C 자료구조] 큐(Queue) (0) | 2021.04.12 |
|---|---|
| [C 자료구조] 스택(Stack) (0) | 2021.04.06 |
댓글