자료구조

CS/Algorithm

태나미 2022. 3. 3. 16:46

자료구조(data structure)는 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다. 자료 구조는 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다. - 위키백과

자료구조의 종류

배열은 대부분의 프로그래밍 언어에서, 가장 간단하고 가장 많이 쓰이는 자료구조형이다.
일반적인 배열은 인덱스로 배열 요소에 빠르게 접근할 수 있습니다. 하지만 특정 요소를 탐색하거나 요소를 삽입 또는 삭제하는 경우에는 효율적이지 않습니다.
자바스크립트 배열은 해시 테이블로 구현된 객체이므로 인덱스로 배열 요소에 접근하는 경우, 일반적인 배열보다 성능적인 면에서 느릴 수 밖에 없는 구조적인 단점을 갖습니다. 하지만 특정 요소를 탐색하거나 요소를 삽입 또는 삭제하는 경우에는 일반적인 배열보다 빠른 성능을 기대할 수 있습니다.
장점 : Fast lookup, Fast push/pop, Ordered
단점 : Slow inserts, Slow deletes, Slow searching, Fixed size

Hash Table은 Key와 Value가 쌍을 이룬 형태로 데이터가 저장되어 있는 자료구조형을 지칭합니다.
객체는 Hash Table이라는 자료구조의 종류 중 하나입니다.
배열 내 데이터도 Key와 Value로 이루어져 있기는 하지만 배열에서는 Key가 오직 index, 즉 숫자만 가능한 것에 비해
Hash Table에서는 문자열 또한 Key가 될 수 있습니다.
장점 : Fast Search, Fast Insertion, Fast Deletion, Fast lookup
단점 : 무작위 주소 할당으로 인한 문제

Linked List는 value와 pointer가 한 쌍인 노드가 모여있는 자료구조형을 의미합니다.
위 사진에서 푸른색 부분은 data를 저장하고 있고, 초록색 부분은 다음 노드를 가리키는 pointer 역할을 하는 address 부분입니다.
Linked List에서 가장 앞 쪽 시작부분을 Head,가장 마지막 부분을 Tail이라고 부릅니다.
Tail의 pointer는 더 이상 가리킬 노드가 존재하지 않으므로 Null을 가리키게 됩니다.
장점 : Fast Insertion, Fast Deletion, Ordered, Flexible Size
단점 : Slow lookup, More Memory

LIFO(Last In, First Out), 마지막으로 삽입된 데이터 제일 먼저 나가는 개념입니다.
자바스크립트에서 스택은 array 또는 Linked List를 이용하여 만들 수 있습니다.
- 1) array 각 element들이 서로 연관되어 있기 때문에 속도가 더 빠릅니다. 하지만 메모리 공간이 한정되어 있기 때문에 할당된 메모리를 다 사용하면 현재 배열을 다른 곳에 복사하기 때문에 메모리를 조금 더 사용하게 될 수도 있습니다.
- 2) Linked List 메모리 여기저기에 흩어져있기 때문에 상대적으로 느릴 수 있습니다. 하지만 반면 메모리 공간이 한정되어 있지 않고 얼마든지 계속 값을 추가할 수 있다는 장점이 있습니다.

FIFO(First In, First Out), 제일 먼저 들어온 데이터가 제일 먼저 나가는 개념입니다.
큐 또한 자바스크립트에서 스택은 array 또는 Linked List를 이용하여 만들 수 있습니다
- array의 경우 앞에서부터 element를 제거해야 하는데 그 경우 index를 다시 재조정해야 하기 때문에 O(n)이 됩니다.
- Queue는 Linked List로 만들게 되면 array보다 시간 복잡도가 훨씬 효율적입니다.
장점 : Fast Operation(removing, pushing), Fast Peek, Ordered
단점 : Slow Lookup

단순히 노드(N, node)와 그 노드를 연결하는 간선(E, edge)을 하나로 모아 놓은 자료 구조
루트 노드라는 개념이 없고, 부모-자식 관계라는 개념이 없습니다.
정점(vertex): 위치라는 개념. (node 라고도 부름),
간선(edge): 위치 간의 관계. 즉, 노드를 연결하는 선 (link, branch 라고도 부름)
그래프 종류로는 크게 방향 그래프와 무방향 그래프가 있습니다. 자세히
그래프의 탐색 방법으로는 깊이 우선 탐색(DFS) 와 너비 우선 탐색 (BFS)가 있습니다.
- 깊이 우선 탐색(DFS, Depth-First Search): 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
- 너비 우선 탐색(BFS, Breadth-First Search): 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

출처: