Data structure
: 데이터에 편리하게 접근하고 조작하기 위한 데이터를 저장하거나 조직하는 방법.
여러 구조가 있고 각각의 장단점을 잘 파악해서 적재적소에 활용.
ex) 화장품은 파우치, 해외여행은 캐리어.
"코딩은 알고리즘과 자료구조, 이 두가지로 이루어진다"
-Linus Torvalds
자료구조의 분류
- Primitive Data Structure : 프로그래밍에서 사용되는 기본 데이터 타입
- Non-primitive data structure: 단순히 데이터를 저장하는 구조가 아니라 여러 데이터를 목적에 맞게 효과적으로 저장하는 자료 구조
- Linear data structure : 저장되는 자료의 전후 관계가 1:1 (ex. List, Stacks, Queues)
- Non-linear data structure : 데이터 항목 사이의 관계가 1:n 또는 n:, (ex. Graphs, Trees)
일반적으로 가장 자주 사용되는 자료 구조
- Array (python에서는 List)
- Tuple
- Set
- Dictionary
- Stack & Queue
- Tree
Array (List)
Array의 특징
- 순차적으로 (ordered) 데이터를 저장한다.
- Array의 element들에게 순서대로 부여된 번호를 index라고 하며 첫번째 element의 index는 0, 가장 마지막 element의 index는 -1이다.
- 순서대로 저장되는 이유는 실제 메모리 상에서, 즉 물리적으로 데이터가 순차적으로 저장되기 때문. 이 때문에 indexing이 가능하고 slicing도 가능하다.
- 순서가 상관 없더라도 주로 서로 연결된 데이터들을 순차적으로 저장할때 사용한다.
- 삽입 순서대로 저장된다. (즉, 새로 삽입되는 요소는 array의 꼬리가 된다.)
- 이미 생성된 리스트도 수정 가능하다. (mutable)
- 동일한 값도 여러번 삽입 가능하다.
- Multi-dimentional Array : Array의 요소가 array가 될 수 있다. 이러한 array를 다중차원 array라고 하며 일반적으로 2D Array가 많이 사용된다.
Array의 단점
- 중간의 임의의 요소를 삭제한다고 하였을때 뒤의 요소들을 앞으로 한칸씩 당겨주어야하므로 코드상에서는 짧아도 실제 메모리 상에서 이루어지는 작업은 상당히 커지고 느리다 (expensive operation). 물론 추가하는 경우도 마찬가지다. 따라서 자주 삭제되거나 추가되는 데이터를 담기에는 적절하지 않다.
- Resizing을 할 경우 상당히 오래걸리는 operation이 발생한다.
따라서 사이즈 예측이 잘 되지 않는 데이터를 다루기에는 적절하지 않다.
Array는 그럼 언제?
- 순차열적인 데이터를 저장할 때 (ex. 주식 가격. 값보다는 순서가 중요한 데이터)
- 다차원 데이터를 다룰 때
- 어떤 특정 요소를 빠르게 읽어야 할 때
- 데이터의 사이즈가 급변하게 자주 변하지 않을 때
- 요소가 자주 추가/삭제 되지 않을 때
Tuple
Tuple의 특징
- List와 마찬가지로 데이터를 순차적으로 저장할 수 있는 순열 자료구조이다.
- 하지만 한번 정의되고 나면 수정할 수 없다. (Immutable)
- 2-3개 정도의 적은 수의 소규모 데이터를 저장할 떄 많이 사용
- 함수에서 리턴값을 한 개 이상 리턴하고 싶을 때 자주 쓰임
Tuple의 단점
- 데이터가 무슨 의미인지 명확하지 않다. 문맥에 맞게 추측해야함.
- 그렇기 때문에 named tuple이라는 것도 존재함. (python)
Tuple은 그럼 언제?
- array를 쓰기에는 간단한 데이터들 표현. array보다 가볍고 메모리도 더 적게 먹음.
Still learning