유튜브에 mycodeschool의 Data Structure 강의를 참고 하였습니다.
자료구조를 배우는 이유
영어 사전은 A-Z까지 순서대로 단어들이 정렬되어 있다. 만약 정렬되있지 않다면 단어를 찾기도 힘들고 수정하기도 힘들다. 지도도 마찬가지로 geometry를 기준으로 근처에 있는 값들이 정돈되어있기 때문에 쉽게 위치라는 값을 이용할 수 있다. 컴퓨터의 동작도 마찬가지로 특정 데이터들을 쉽게 찾거나, 수정, 삭제등의 조작을 효율적으로 하기 위해서 상황에 맞는 자료 구조들을 사용하는 것이 중요하다.
Data Structures : List as Abstract Data Type (ADT)
Abstract Data Type
explain data, operations but no implementation
데이터와 자료 구조별로 데이터들이 어떻게 동작할지 서술 한 것으로 List, Stack. Queue ADT 등이 있다.
ADT 로써의 List의 기능은 아래와 같다.
- 주어진 데이터 타입의 갯수만큼의 숫자들을 저장할 수 있다.
- 리스트 내의 특정 위치의 값들을 읽거나 수정할 수 있다.(get, modify)
- 특정 위치의 값을 삭제(remove)하거나 중간에 삽입(insert) 할 수 있다.
- 리스트 내의 값들을 카운트(count) 할 수 있다.
- 데이터 타입을 정할 수 있다.
implementaion: 이러한 자료 구조들을 어떻게 실제로 구현하기 위한 방법
이러한 특징들을 가지고 있는 리스트를 실제로 구현(implementaion)하기 위해서는 우리가 잘 알고 있는 array data structure를 이용할 수 있다.
Abstract Data Type으로써의 list(abstract_data_type)는 일반적으로 linked list(singly or doubly linked)나 dynamic arrays(동적 배열)로 구현된다.
리스트의 크기가 fixed되어 있는 static 한 list말고, dynamic list를 만들고 싶을 때 array를 이용해서 만들 수 있다.
- empty list has size 0
- insert
- remove
- count
- read / modify at a position
- specify data-type
A[2]에 5라는 값을 insert 하면, A[2] 보다 큰 인덱스들의 값들은 오른쪽으로 한칸 씩 shift된다.
만약 array 가 가득 찼다면 새로운 값을 더 추가하기 위해서, 새로운 array를 만들고 기존 array에 있는 값들을 복사하여 새로운 array에 입력한다. 이때 이전의 array의 메모리는 비워지게된다.
time complexity
1) read, modify : constant time, O(1)
2) insert : 첫번째 인덱스에 값을 삽입하면 모든 값들이 오른쪽으로 한칸씩 shift되어야 하기 때문에 리스트의 크기만큼 시간 소요된다. O(n)
3) remove : O(n)
4) Add : 만약 array가 다 찬 경우, 값을 추가한다면 새로 array를 만들고 값을 넣어야하기 때문에 리스트의 크기만큼 시간 소요 . O(n)
꽉찬 배열에 새로 값을 추가하려면 또 새로운 배열을 만들어야하고 이 과정이 계속 반복되어야하기 때문에 이러한 dynamic list는 memory의 관점에서는 비효율적인 구조이다.
dynamic list의 특징도 유지하면서, 메모리를 효율적으로 사용하기 위해서 만든게 linked list 이다.
