Week01_ArrayList

 1. 리스트란? 

 

1) 정의

- 자료를 순서대로 저장하는 자료구조

- 여러 개의 자료가 일직선으로 연결된 선형 구조

- 배열 리스트 : 배열을 이용하여 구현된 리스트

 

2) 주의점

- 리스트는 한 줄로 저장

- 줄을 세울 때 앞 항목과 뒤 항목이 1개로 연결되는 구조

 

3) 배열과 배열리스트

- 배열 : 같은 자료형의 데이터가 메모리 상에 연속적으로 저장

- 배열 리스트 : 자료가 일직선으로 서로 연결

 

 

 

 2. 자료형 

 

1) 정의

- 기초적인 자료형 : 정수, 실수, 문자열 등

- 새로운 자료형 : 스택, 큐, 리스트, 트리 등

 

2) int 자료형

- INT_MIN : 컴퓨터가 나타낼 수 있는 가장 작은 정수

- INT_MAX : 컴퓨터가 나타낼 수 있는 가장 큰 정수

- 복잡한 자료형 구현 시 연산자가 아닌 함수로 작성

 

3) 추상 자료형 (Abstract Data Type, ADT)

- 추상적, 수학적으로 자료형을 정의한 것

- 자료구조는 추상 자료형을 프로그래밍 언어로 구현한 것

- 자연수를 나타내는 추상 자료형 : Nat_Number

① 객체 : 0~INT_MAX까지의 순서화된 정수의 부분 범위

② 함수

Nat_number zero()::= 0

Nat_number successor(x) ::= if(x == INT_MAX) return x                                            else return x + 1

Boolean is_zero(x) ::= if(x) return FALSE                                      else return TRUE

Boolean equal(x,y) ::= if(x == y) return FALSE                                      else return FALSE

Nat_number add(x,y) ::= if((x + y) <= INT_MAX)                                       else return INT_MAX

Nat_number sub(x,y) ::= if (x < y) return 0                                         else return x – y;

 

 

 

 3. 리스트 ADT 

 

1) 정의

- 리스트는 자료를 정리하는 방법 중의 하나

 

2) 리스트 ADT

- 리스트를 추상 데이터 타입으로 정의한 것

① 객체 : n형으로, element형으로 구성된 순서 있는 모임

② 함수

insert(list, pos, item) ::= pos 위치에 요소 추가

insert_last(list, item) ::= 맨 끝에 요소 추가

insert_first(list, item) ::= 맨 처음에 요소 추가

delete(list, pos) ::= pos 위치의 요소 제거

clear(list) ::= 리스트의 모든 요소 제거

get_entry(list, pos) ::= pos 위치의 요소 반환

get_length(list) ::= 리스트의 길이

is_empty(list) ::= 리스트가 비었는지 검사

is_full(list) ::= 리스트가 꽉 찼는지 검사

print_list(list) ::= 리스트의 모든 요소 표시

 

3) 리스트 구현

- 배열을 이용한 구현

① 장점 : 리스트 ADT를 가장 간단하게 구현 가능

② 단점 : 크기 고정 → 메모리 낭비

- 연결 리스트를 이용한 구현

① 장점 : 크기 제한 X, 포인터를 이용한 유연한 진행 가능

② 단점 : 구현이 복잡

 

 

 

 4. 배열 리스트  

 

1) 정의

- 순차적 표현(sequential representation) : 배열을 이용한 리스트 구현은 순차적인 메모리 공간 할당

- 배열 사용 시 리스트의 항목을 자연스럽게 저장 가능

 

2) 실습