자료구조
- 사전에서 단어를 찾는 방식
- 지도에서 경로 찾기
- 계산서 정렬
-> 다른 데이터를 처리하는데 다른 자료구조가 필요
자료구조란 컴퓨터에 정보를 저장하고 정리하여 효율적으로 활용하기 위한 방법이다.
아래의 순서에 따라 자료구조를 확인해볼 예정
1) 수학적 / 논리적 모델 or Abstract Data types (ADT)
2) 활용 (Implementation) ~ Concrete Implementation. not abstract)
예)
TV - 전원을 키고 끈다.
- 신호를 받는다.
- 음성과 영상 재생 기능
-> 이것이 Abstract View
예2)
리스트(List) ~ ADT
-
주어진 정보나 요소를 저장
-
요소를 위치(position)에 따라 읽음
-
요소를 해당 위치(position)에서 수정함
배열 (Arrays) - Concrete Implementation
연결리스트 (Linked List)Abstract data type (ADT)
-
데이터와 연산(operation)은 정의하지만 구현 방법(implementation)은 정의하지 않음
-
아래 순서에 따라 자료구조를 분석할 예정
1) 논리적 구조파악(logical view)
2) 연산방식(operation)
3) 비용(cost of operation)
4) 구현(Implemtation)
List as abstract Data type
List
- Store a given number of elements of a given data-type
- Write / modify element at a position
- Read element at a position
Are you talking about Arrays?
int A[10];
A[i] = 2;
Print A[i];List
- empty list has size 0
- insert
- remove
- count
- Read / modify element at a position
- specify data-type
int A[MAX SIZE];
int end = -1; (-1은 null을 의미)
insert(2) // 0
insert(4) // 1
insert(6) // 2
insert(7) // 3
insert(9) // 4
insert(5, 2) // 5
remove(0) // 4
-
array가 가득 찼으면, 기존 array의 2배 크기의 새로운 array를 만들고 이전 array에 있던 요소들을 새 array로 복사해온다. 기존 array의 메모리는 해제(free)한다.
-
시간복잡도
(1) Access - Read / write element at an index - constant time, O(1)
(2) Insert - O(n) - 삽입하는 position 기준으로 하나씩 뒤로 옮겨야 하니까
(3) Remove - O(n) - Insert와 마찬가지 이유
(4) Add - O(n)
