Data structure 비교하기

다시 복습하는 데이터 구조

Array vs Linked List

Array를 먼저 살표보면 index를 통해 직접적으로 접근할 수 있으면서 Random Access를 지원합니다. // 시간 복잡도는 O(1) 
삽입과 삭제 연산은 memory 위치가 연속적이고 고정적이기 때문에 많은 시간을 소모합니다 // Static Memory Allocation

사이즈는 Array 선언 때 정해집니다.

 

LinkedList에서는 새로운 요소가  node에 저장되고, 할당된 memory 주소는 linked list의 이전 node에 저장되어집니다. 찾고자 하는 값에 도달할 때까지 순차적으로 검색하면서 찾아야 합니다. // 시간 복잡도는 O(n)
새로운 요소는 첫 번째 사용 가능한 빈 Memory 위치에 저장되며, 이전 Node에 Memory 위치의 주소를 저장하는 단 하나의 overhead만이 존재합니다. 따라서 삽입과 삭제 연산이 상대적으로 빠릅니다. // Dynamic Memory Allocation
사이즈는 노드가 추가될 때마다 커지기 때문에 변동적입니다.

 

Stack vs Queue

Stack은 후입선출(LIFO, Last-In-First-Out) 구조로 마지막에 삽입된 자료부터 삭제가 된다. 정해진 방향으로만 데이터를 저장할 수 있으며, Top은 항상 최근에 들어온 자료를 가르킨다. 

- 웹브라우저 사용기록

- 실행취소

- 수식의 괄호 검사

 

Queue는 선입선출(FIFO, First in first out) 방식으로 먼저 들어온 자료부터 삭제가 된다. 자료가 저장되는 rear 부분과 삭제가 일어나는 front 부분으로 나눈다. 

- 고객 대기시간

- 우선 순위가 있는 작업

- 캐시 시스템

- 너비 우선 탐색

 

스택과 큐 비교