자료구조 정리 #1 배열(Array), 리스트(LinkedList), 큐(Queue), 스택(Stack)

- 자료구조의 분류

선형구조

1. 배열 (Array) (선형 리스트)

배열의 특징은 논리적 순서와 물리적 순서가 일치한다. 즉, index값을 통해 원소 접근이 용이하며, 구현이 쉽다.
하지만 단점으로 삽입, 삭제 등에 대한 연산에 필요한 Cost가 높다.

삭제를 하는 경우 순서를 맞추기 위해 뒤의 원소들을 앞으로 Shift 연산을 해줘야 한다.

삭제

1

2

3

4

5

1

2

삭제

4

5

1

2

4

5

1

2

4

5

< Shift >

 

2. 연결 리스트(LinkedList)

배열의 삽입/삭제의 단점을 극복하고자 만든 개념이 리스트이다.
배열은 논리적, 물리적 저장이 순서대로 되어 있다.
하지만 리스트는 논리적으로는 순서대로 되어 있으나 물리적으로는 순서대로 되어있지 않다.
대신 각 원소가 index위치에 해당하는 물리적 주소를 가지고 있다.

이러한 특징으로 삽입/삭제를 할 경우 데이터를 Shift 할 필요 없이, 해당되는 원소의 물리적 주소만 변경해주면 된다.
하지만 이런 특징으로 원하는 index를 참조하려면, 1번 index부터 차례대로 접근해야 한다는 비효율적인 특성이 있다.

3. 스택(Stack)

스택은 선형 자료구조의 일종으로 FILO(First in Last Out)의 대표적인 예로 말 그대로 선입 후출 구조이다.(먼저 들어간 값은 나중에 뽑을 수 있다.)
즉, 다른 말로 가장 나중에 들어간 값을 먼저 꺼낸다는 것이다.
스택으로 가장 효율적인 문제는 미로 찾기, 괄호 유효성 체크 등에 활용한다.

4. 큐(Queue)

큐 역시 선형 자료구조 중 하나이며, 스택과 반대로 FIFO(First In First Out)의 대표적인 예로 말 그대로 선입선출 구조이다.(먼저 들어간 값은 먼저 나온다.)
즉, 나중에 들어간 값은 가장 나중에 나온다는 것이다.
큐의 응용문제로는 작업 우선순위, Heap 구현 등에 사용한다.

5. 데크(Deque)

데크는 큐와 스택의 장점만 모아서 만든 구조이다. 양쪽 끝에서 이벤트를 발생하는 자료구조이다.
입력 제한 데크는 Scroll 이 있고, 출력 제한으로는 Shelf가 있다.