[면접준비] 자료구조 (24/04/15)

Array와 Linked List의 비교

1. Array
   
   • 정적 자료구조. 특정 크기의 연속적인 메모리 공간에 데이터를 저장하는 자료구조.
   • 생성시 크기가 정해지며, 동적으로 변경하기 어렵다.
   • 연결된 메모리 주소를 할당 받기 때문에 index를 가지게 되고, 임의 접근이 가능하다는 장점을 가진다.
   • index를 가지기 때문에 접근과 탐색이 용이하다.
   • 크기를 미리 정했기 때문에 수정이 불가능하며, 정해진 크기 이상의 데이터를 저장할 수 없다. 
2. Linked List
   
   • 동적 자료구조. 크기를 정할 필요도 없으며, 메모리 주소또한 연속되지 않는다.
   • 데이터와 다음 데이터를 가리키는 주소가 담긴 노드(Node)를 가지고 노드끼리 연결된 형태이다.
   • 크기를 정해놓지 않았기 때문에 크기 제한이 없으며, 데이터 추가 삭제가 자유롭다.
   • 연속적인 메모리 주소를 할당받지는 않았기 때문에, 임의 접근이 불가능하다. 즉, 데이터 탐색시 순차적 접근이 필요하다는 뜻이다.
3. 간단 비교(배열 vs 연결리스트)
   1. 정적 vs 동적
   2. 미리 정해진 크기 vs  크기정할 필요 없는
   3. 연속된 메모리 주소 vs 연속되지 않음
   4. 접근, 탐색 용이 vs 추가, 삭제 용이
      1. 데이터 조회 : 시간 복잡도 O(1) vs O(N)
      2. 데이터 첨삭 : 시간 복잡도 O(N) vs O(1)
   5. Index vs Node 
   6. 정보 저장 vs 연결된 정보

 

Stack과 Queue의 비교설명

1. Stack
   
   • 같은 구조와 크기의 자료를 정해진 방향으로 쌓아 올린 형태의 자료구조(후입선출 LIFO)
   • Top 원소로만 접근 가능.
   • Top(가장 위의 자료)는 가장 최신의 자료를 가리키며, 삽입되는 자료는 top위에 쌓여 새로운 top이 된다(Push).
   • 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다(Pop).
   • 활용 예시 
     • 웹 브라우저 방문기록(뒤로가기) : 가장 나중에 열린 페이지 부터
     • 역순 문자열 : 가장 나중에 입력된 문자부터 
     • 실행 취소 : 가장 나중에 실행된 것 부터
2. Queue
   
   • 줄, 혹은 순서 대기. 선입선출(FIFO)방식의 자료구조
   • 큐의 한쪽 끝에서(Rear) 삽입(enQueue) 작업이, 다른 쪽 끝에서(Front) 삭제(dnQueue) 작업이 이루어진다.
   • 첫 원소와 끝 원소로만 접근 가능
   • 활용 예시
     • 우선순위가 같은 작업 예약
     • 은행업무
     • 콜센터
     • 프로세스 관리
     • 너비 우선 탐색(BFS)
     • 캐시(Cache)
3. 간단비교(Stack vs Queue)
   1. LIFO vs FIFO
   2. push,pop vs enQueue,dnQueue
   3. 함수호출,짝맞추기 vs 대기열, 캐시, 스캐쥴링
   4. 둘 모두 배열과 연결리스트로 구현된다.

 

 

답변