자료구조란?
기본 적으로 두 가지 형태
Primitive Data Structure
int, char, float, double, ...
Non-Primitive Data Structure
- Linear: Array, Stacks, Queues, (Linked) List
- Non-Linear: Tree, Graphs
컴퓨터 프로그래밍에서의 자료구조는 non-primitive한 자료 구조를 어떻게 효율적으로 다룰 수 있는지가 중요
List (Array-Based Sequences)
사진 출처: https://www.geeksforgeeks.org/python-data-types/
List - Sequence Type
- list, tuple, str는 파이썬의 built-in sequence class
- Insertion, Removal: 주소를 이용해 관리하기 때문에 기존의 값들은 뒤로 한 칸 씩 밀리는 동작 - O(N)
- List가 다 찼을 때 전략
- Incremental strategy: 상수 c만큼 계속 사이즈를 증가 - T(n) = O(n + k^2)
- Doubling stratepy: 현재 사이즈의 두 배 만큼 계속 사이즈를 증가 - T(n) = O(n)
List-operations
max() min() next(iterator) pow() print() range() round() sorted() sum() type()
built-in function in python
Stacks
사진 출처: https://www.programiz.com/dsa/stack
-
Main stack operations
- push (object): 요소 삽입
- object pop(): 마지막에 삽입한 요소를 제거 및 반환
-
Auxiliary stack operations
- object top()/peek(): 제거 없이 마지막에 삽입한 요소를 반환
- integer len(): 저장된 요소들의 길이를 반환
- boolean is_empty()/is_full(): 요소가 있는지 없는지를 반환
-
단순하지만 효율저으로 동작
Array-Based Stack
- 배열을 사용하여 구현한 가장 쉬운 Stack 자료구조
- O(n) (Stack에 n개의 요소가 있을 때)
- 확장이 필요한 경우 block 단위의 copy operation이 필요할 수 있음 (기존 저장소에서 확장이 아닌 신규 저장소를 확보한 뒤 그 곳에 copy/paste를 해야하기 때문)
Applications
-
직접
- 웹 방문 기록
- Undo method
-
간접
- 자료구조의 기능으로 사용
-
괄호 찾기, HTML 태그 찾기, ...
Queues
사진 출처: https://www.programiz.com/dsa/queue
- Main queue operations
- enqueue (object): 큐의 끝에 요소를 삽입
- object dequeue (): 큐의 앞에 있는 요소를 제거 및 반환
- Auxiliary queue operations
- object first()/peek(index): 큐의 앞에 있는 요소/특정 인덱스를 제거하지 않고 반환
- integer len(): 저장된 요소들의 길이를 반환
- boolean is_empty()/is_full(): 요소가 있는지 없는지를 반환
Array-Based Queue
Applications
-
직접
- 웨이팅 리스트, CPU 스케쥴링, 디스크 스케쥴링
- 공용 리소스 처리(e.g., printer)
- 멀티 프로그래밍 / 스케쥴링
- 콜센터
-
간접
- 자료구조의 기능으로 사용
-
Round Robin Schedulers, Circular Queue, ...
Linked Lists
기존 List는 연속적인 메모리 공간을 할당받고 사용해야 List의 장점을 이용할 수 있었다.
동적으로 List를 관리하면 메모리가 필요할 때 언제든지 추가하고 삭제할 수 있는 형태가 되어서 조금 더 쉽게 사용할 수 있다는 가정으로 시작.
Singly Linked List
- 한 쪽 방향으로 연결된 Linked List
- Node = Data(요소) + Link(다음 노드 주소)
- 맨 앞의 노드에는 head, 맨 뒤의 노드에는 null
- Inserting at the Head
- Removing at the Head
- Inserting at the Tail
- Removing at the Tail
- Inserting at the Middle
- Removing at the Middle
Inserting과 Removing을 수행할 땐 양 쪽 주소를 잃어버리지 않도록 각 상황을 고려하여 제일 우선적으로 포인트할 수 있도록 동작.
Stack as a Linked List
Stack의 크기가 늘어났다 줄어들었다 하는 경우 Linked List를 이용해서 Stack을 구현하는 것이 유용하다. 일반 Stack은 길이를 확장할 때 메모리를 확장해야하기 때문.
- top 요소가 첫 번째 노드에 저장된다. Removing하는 경우 비교적 간단하기 때문.
- 일반적인 Stack은 요소를 넣어주기만 하면 됐지만 Linked List를 이용항 Stack은 요소와 다음 주소를 저장해야하기 때문에 메모리를 두 배 사용하게 된다. 그러나 확장성을 생각하면 Linked List를 이용한 Stack이 훨씬 유리하다.
Queue as a Linked List
- 앞 요소가 첫 번째 노드에 저장되고 뒷 요소가 마지막 노드에 저장된다.
- 하지만 head에서 빼는 것이 훨씬 유리하므로 반대로 저장하는 것이 유용하다. (enqueue - tail, dequeue - head)
Doubly Linked List
- 양 쪽 방향으로 연결된 Linked List
- prev에 앞 쪽 노드의 주소를 저장 (prev - elem - next)
- Insertion
- Deletion
Insertion과 Deletion을 수행할 땐 양 쪽 주소를 잃어버리지 않도록 각 상황을 고려하여 제일 우선적으로 포인트할 수 있도록 동작.
장점 : 모든 노드에서 동일하게 insertion과 deletion이 동작하기 때문에 훨씬 구조가 간단하다.
단점 : 메모리가 3배 더 많아진다.
