선형 자료구조 (Linear)

자료구조 : 데이터 값의 모임, 데이터의 관계

• 자료들 간의 앞뒤 관계가 1:1의 선형관계를 이루는 자료구조

배열과 연결 리스트

배열 (Array)

• 크기와 형식이 정해진, 순서가 있는 데이터의 집합
• 입력된 데이터들이 메모리 공간에서 연속적으로 저장되어 있다
  - index를 통한 접근이 용이하다
• 빠른 접근이 요구되고, 데이터의 삽입과 삭제가 적을 때 유리하다.

시간 복잡도

• 접근하고자 하는 인덱스를 알고 있을 경우 O(1) / 순차 탐색 시 O(n)
• 배열의 처음이나 중간에 삽입, 삭제 시 O(n) / 끝에 삽입, 삭제 시 O(1)
  - 삽입 지점 이후의 데이터를 앞이나 뒤로 옯겨야 하기 때문이다.
  

연결 리스트 (Linked List)

• 순서가 있는 데이터의 집합
• 메모리를 연속적으로 사용하지 않는다
  - 배열에 비해 index를 통한 접근에 속도가 오래 걸린다
  • 삽입, 삭제에 용이하다
• 삽입, 삭제가 잦고, 검색 빈도가 적을 때 유리하다.
  

시간 복잡도

• 탐색 시 O(n)
• 삽입, 삭제 시 O(1)

스택과 큐

스택

• 리스트의 한쪽 끝으로만 자료의 삽입 / 삭제 작업이 이루어진다.
• Last In First Out 나중에 들어간 값이 먼저 조회된다.
• 값을 넣는 Push 동작, 값을 읽음과 동시에 삭제하는 Pop 동작
• 저장할 공간이 없는 상태에서 삽입 시 Overflow가 발생
• 삭제할 데이터가 없는 상태에서 삭제 시 Underflow가 발생

시간 복잡도

• 탐색 시 O(n) : 특정 데이터를 찾을 때까지 수행
• 삽입, 삭제 시 O(1) : 항상 맨 위에 데이터를 삽입 / 삭제하기 때문

활용

• 브라우저 사용 시 뒤로가기 버튼
• 연산자 우선 순위, 괄호 검사, 후위 표기법

큐

• 한쪽에서 데이터를 넣고, 반대쪽에서 데이터를 뺄 수 있는 집합
• First In First Out 먼저 들어간 순서대로 값을 조회할 수 있다.
• 시작을 나타내는 Front Pointer, 끝을 나타내는 Rear Pointer
• 큐의 맨 뒤에 데이터를 추가하는 Enqueue 동작, 큐의 맨 앞의 데이터를 삭제하는 Dequeue 동작

시간 복잡도

• 탐색 시 O(n)
• 삽입, 삭제 시 O(1)

활용

• 순차적으로 처리해야 하는 일 (=우선순위가 동일한 일)
• 너비 우선 탐색 (BFS, Breath-First Search) 구현
• 캐시 (Cache) 구현
• 일상생활에서 찾을 수 있는 고객센터, 놀이 공원 및 고객센터 대기 줄 등

스택과 큐의 차이점

참고 : oeueoo.log, zzooo's log. sbinha.log, 폐관코딩