자료구조의 분류

1. 개요

자료구조는 프로그래밍시 가장 중요한 개념중 하나로, 특정 데이터를 어떻게 저장할 것인가에 대한 방법론이다. 자료구조에는 list(링크드리스트), map(딕셔너리), array등이 있다.

2. 내용

2.1 선형 자료구조

2.1.1 Array

자료구조 중 가장 기초가 되는것으로, array[i]의 형태를 띄고있는것이 일반적이다. Python 에서는 list라고도 한다(그 외에서는 일반적으로 Linked List를 의미 할 수 있으니 유의)

2.1.2 Linked List

연결리스트로 각각의 자료가 다음자료, 이전자료의 주소값을 가지고 있으며 처음과 끝 또한 연결되어있다. 따라서 시작점이라는 개념이 존재하지 않으며 어떤 값을 검색하더라도 O(N)의 시간에 찾아낼 수 있다.

2.1.3 Stack

Last-In First-Out인 자료구조 중 하나. 선형 자료구조의 하단에 먼저 들어온 데이터 부터 쌓이기 시작하여, 가장 상단에 마지막으로 들어온 데이터가 축적된다. 반대로 가장 마지막으로 들어온 데이터부터 사용된다.

2.1.4 Queue

First-In First-Out인 자료구조. 먼저 추가한 데이터부터 사용된다.

2.1.5 Map

Python에서는 Dictionary라고 불리는 자료구조. (mapping과는 다르다) 모든 데이터가 key:value쌍으로 이루어지며, key의 해시값을 통해 value값을 return하므로, 자료구조에 순서가 존재하지 않고, index의 시간복잡도가 O(1)이다. key가 저장되므로 key의 변경이 어려우며(삭제 후 재생성을 통해 가능하긴 하다), 직접적으로 key값을 계산하기에 힘들어, key에는 immutable한 자료형을 넣어야 한다.

2.2 비선형 자료구조

2.2.1 Tree

트리자료구조는 나무와 같이 head노드로부터 하위노드로 내려가는 인접한 노드끼리 서로 연결된 자료구조이다. 모든 노드는 결국 연결되어 있으며, 정렬방법에 따라 RB-tree, 완전이진트리 등으로 명칭할 수 있다.