자료 구조 한방에 정리

자료구조 한방에 정리

주기적으로 자료구조의 핵심 특징들을 머리에 되새김 하기 위해서 이렇게 한방에 자료구조를 정리하는 포스팅을 올린다!

목차

1. Array
2. Linked List
3. Stack
4. Queue
5. Hash Table
6. Graph
7. Tree

Array

Array는 물리적 주소와 논리적 주소 같은 자료구조이다.

장점

• 인덱스 로 접근하며 원소 접근이 O(1)로 빠르다.
• 구현이 쉽다.

단점

• 삽입, 제거시 뒤의 원소들을 앞으로 이동시켜 주어야 하므로 비용이 크다
• 크기가 정해져 있어 한정적이다.
• 원소가 삭제되면 그 자리가 비어버리므로 공간이 낭비된다.

이미지 출처: https://beginnersbook.com/2018/10/data-structure-array/

Linked List

Linked List는 물리적 주소와 논리적 주소 다른 자료구조이다.
Singly Linked List와 Doubly Linked List로 나뉜다.
Singly Linked List는 노드에 노드의 값과 다음노드의 주소를 가지고 있다. Stack 자료구조 구현시 사용된다. Doubly Linked List는 노드에 노드의 값과 이전노드와 다음노드의 주소를 가지고 있다. Queue자료구조 구현시 사용된다.

장점

• 삽입, 제거가 빠르다.
• 빈 공간이 있을 수 없다
• 크기가 유동적이다.

단점

• 특정 원소에 접근시에 Front 노드부터 탐색을 시작해야 한다.
• 배열과 비교헀을때 node마다 이전노드의 주소 또는 다음노드의 주소를 참조해야 하므로 포인터라는 메모리가 추가적으로 필요한다.

이미지 출처: https://beginnersbook.com/2013/12/linkedlist-in-java-with-example/

Stack

Stack은 선형자료구조로써 FILO 또는 LIFO 특성을 가지고 있다. 가장 처음 들어온 원소가 가장 마지막에 나온다는 뜻으로 후에 깊이 우선 탐색시 사용되는 자료구조이다. 배열 또는 링크드 리스트 자료구조로 구현할 수 있다. 배열로 구현할 때에는 스택의 크기가 정해지기 떄문에 오버플로우 현상이 나타날 수 있어 비효율적이다. 따라서, 링크드 리스트 자료구조로 구현하는 것이 효율적이다,

이미지 출처: https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D

Queue

Queue는 선형자료구조로써 FIFO 특성을 가지고 이다. 가장 처음 들어온 원소가 먼저가 오는 뜻으로 후에 너비 우선 탐색시 사용되는 자료구조이다. 배열 또는 링크드 리스트 자료구조로 구현할 수 있다. 배열로 구현할 때에는 front 노드의 값을 제거할 때 나머지 노드들을 앞으로 옮겨줘야 하기 때문에 비효율적이다. 따라서, 링크드 리스트 자료구조로 구현하는 것이 효율적이다.

이미지 출처: https://en.wikipedia.org/wiki/Queue(abstractdata_type)

Hash Table

Hash Table은 Key-Value로 데이터를 저장하는 자료구조이다. 빠르게 데이터를 검색할 수 있다. 그 이유는 내부에서 배열 또는 버킷을 사용하여 데이터를 저장하기 떄문이다. Hash Table은 각각의 Key값에 해시함수를 적용하여 배열 또는 버킷의 고유한 Index값을 얻고, 이 Index를 통해 값을 검색한다. 해시 함수를 적용시킨 이 해시 테이블의 평균 시간복잡도는 O(1)이다.

이미지 출처: https://en.wikipedia.org/wiki/Hash_table

Graph

노드와 그 노드를 연결하는 간선을 모아 놓은 추상적인 비선형 자료구조이다. 객체와 객체간의 관계를 표현할 수 있는자료구조이다. 노드를 Vertex라고 부르고 노드를 연결하는 간선을 Edge라고 부른다. 뱡향성을 띄고 있는지에 따라 방향 그래프와 무방향 그래프로 나뉜다. 방향 그래프의 대표적인 예시로는 트리가 있다.

그래프 용어

• 정점(Vertex, Node): 아래 그림에 있는 숫자
• 간선(Edge, Link): 정점과 정점을 연결하는 선
• 가중치: 간선에 특정 값을 매기는 것, 쉽게말해 해당 간선을 지나갈때 나타내는 비용
• 방향 그래프: 방향성이 있는 그래프
• 무방향 그래프: 방향성이 없는 그래프
• self-loop: 정점에서 자기 자신으로 돌아오는 간선
• Adjacency: 뱡향성이 있는 방향 그래프에서 간선으로 연결된 인접 정점, 쌍방으로 적용되는 것이 아님, 노드 1은 노드2를 Adjacency하고 노드2는 노드1에 Adjacency하지 못하다고도 할 수 있다.
• Degree: 각 정점들에 연결되어 있는 Edge들의 수
• Path: 정점1과 정점2로 이동할 수 있는 경로
• Cycle: 그레프가 경로를 따라 동일한 정점으로 되돌아올 수 있는 경우
• Forest: 그래프중 싸이클이 없고 방향성이 없는 경우 Forest라고 부른다,

이미지 출처: https://www.geeksforgeeks.org/graph-data-structure-and-algorithms/

Tree

그래프의 한 종류 이다. 노드와 노드와 노드를 잇는 간선으로 이루어진 비선형 자료구조이다. 계층적인 특징을 가지고 있다.

특징

• 단 하나의 루트 노드를 가지고 있다.
• 부모 노드는 0개 이상의 자식 노드를 가지고 있다.
• 자식노드는 1개의 부모 노드를 가지고 있다.
• 트리에는 사이클이 존재할 수 없다.
• 노드는 순서대로 나열되어 있을 수도 있고 그렇지 않을 수도 있다.

이미지 출처: https://towardsdatascience.com/8-useful-tree-data-structures-worth-knowing-8532c7231e8c

트리의 용어

• Root(루트 노드): 최상위의 노드로써 트리는 하나의 루트 노드만을 가진다.
• Leaf nodes(말단 노드): 자식이 없는 노드이다
• Edge(간선): 노드를 연결하는 선이다.
• Sibling(형제 노드): 같은 부모를 가지는 노드이다.
• Degree(노드의 차수): 특정 노드의 자식 수를 말한다.
• Degree of tree(트리의 차수): 트리의 최대 차수
• Height(트리의 높이): 루트 노드에서 가장 깊숙히 있는 노드의 깊이이다.
• Subtree(서브트리): 자신의 자식을 루트로 하는 트리를 서브 트리(Sub Tree)라고 부르며 차수와 서브 트리의 개수는 같다.

트리의 종류

• 이진 트리(Binary Tree): 트리 중에 모든 노드의 차수가 2 이하로 구성하는 트리입니다.
• 포화 이진 트리(Full Binary Tree, 꽉 찬 이진 트리): 마지막 레벨까지 모든 노드가 있는 이진 트리입니다.
• 완전 이진 트리(Complete Binary Tree): 노드를 삽입할 때 왼쪽부터 차례대로 추가하는 이진 트리입니다.
• 사향 트리(Skewed Binary Tree),: 한쪽으로 기울어진 트리, 편향 트리라고도 부릅니다.

트리의 종류

이미지 출처: https://towardsdatascience.com/5-types-of-binary-tree-with-cool-illustrations-9b335c430254