알고리즘 이론 깨부수기 Array, Linked List, Stack, Queue, Tree

Array

가장 기본적인 자료구조로 논리적 저장 순서와 물리적 저장 순서가 일치한다.

따라서 인덱스로 해당 언소에 접근할 수 있어 찾고자하는 인덱스 값을 알고 있다면 O(1)의 시간 복잡도를 갖는다.

 

하지만 삭제하는 과정에서 원하는 값을 삭제하면 빈 공간이 생기고 그 빈 공간을 없애기 위해 뒤에 있는 값들을 당겨와야하기 때문에

O(N)의 시간복잡도를 갖는다.

 

삽입의 경우도 마찬가지이다. 만약 첫번째 자리에 새로운 원소를 추가하고자 한다면 모든 원소들의 인덱스를 1 씩 shift 해줘야 하므로 이 경우도 O(n)의 시간을 요구하게 된다.

 

Linked List

배열의 문제점을 해결하기 위한 자료구조가 linked list이다.

링크드 리스트는 삽입과 삭제시 O(1)의 시간 복잡도를 가지게된다.

추가

0과 2라는 노드가 있을 때 그 사이에 1이라는 노드를 삽입하고 싶다고 한다면 1 노드의 next를 2노드를 가르키게 하고 0 노드의 next를 1노드를 가르키게 하면 됩니다.

삭제

삭제 과정은 이와 반대입니다.

탐색

어떠한 원소를 삭제 또는 추가하고자 했을 때, 그 원소를 찾기 위해서 O(n)의 시간이 추가적으로 발생하게 된다.

 

Stack

선형 자료구조의 일종으로 Last In First Out (LIFO). 즉, 나중에 들어간 원소가 먼저 나온다. 이것은 Stack 의 가장 큰 특징이다.

Queue

선형 자료구조의 일종으로 First In First Out (FIFO). 즉, 먼저 들어간 놈이 먼저 나온다. Stack 과는 반대로 먼저 들어간 놈이 맨 앞에서 대기하고 있다가 먼저 나오게 되는 구조이다.

Tree

트리는 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다. 트리는 계층적 관계(Hierarchical Relationship)을 표현하는 자료구조이다.

• Node(노드) : 트리를 구성하고 있는 각각이 요소를 의미한다.
• Edge(간선) : 트리를 구성하기 위해 노드와 노드를 연결하는 선을 의미
• Root Node(루트 노드) : 트리구조에서 최상위에 있는 노드를 의미
• Terminal Node ( = leaf Node, 단말 노드) : 하위에 다른 노드가 연결되어 있지 않은 노드를 의미한다.
• Internal Node (내부노드, 비단말 노드) : 단말 노드를 제외한 모든 노드로 루트 노드를 포함한다.