[자료구조] - 자료구조 정리1

링딩·2023년 4월 2일

CS지식 자료구조

Computer Science

목록 보기

16/49

자료구조 정리

...

1. Array & LinkedList

배열 (Array)

정적 자료구조
-> 입력된 데이터들이 메모리 공간에서 연속적으로 저장되어 있는 자료구조
메모리 상에서 연속적으로 저장되어 있는 특징을 가지기에, index를 통한 접근이 용이
배열의 크기는 처음 생성할 때 정하며 이후에는 수정이 어렵다

시간 복잡도

탐색 : O(1) _접근하고자 하는 인덱스를 알고 있어야 함
-> 순차적으로 탐색시 O(n)
삽입 / 삭제 :
- 배열의 처음 또는 중간에 삽입 및 삭제 : O(n)
  (삽입 지점 이후의 데이터를 옮겨야 하기 때문.)
- 배열의 끝에 삽입 및 삭제 : O(1)

연결 리스트 (Linked List)

동적 자료구조
->여러 개의 노드들이 순차적으로 연결된 형태를 갖는 자료구조이며, 첫번째 노드를 head, 마지막 노드를 tail이라고 한다.
각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있다.
배열과는 다르게 메모리를 연속적으로 사용하지 않는다.
배열과는 다르게 순차적으로 접근해야 하는 면에서 불리할 수도 있으나, 노드가 연결된 구조이기 때문에 삽입, 삭제에 용이하다.

시간 복잡도

탐색 : O(n)
삽입 / 삭제: 삽입과 삭제 자체는 O(1)이다

1-2. 정리

👍 장점

배열 : 인덱스를 통한 빠른 접근 가능
연결 리스트 : 삽입/삭제 용이

🤦‍♂️ 단점

배열 :
- 삽입/삭제가 오래 걸림
  배열 중간에 있는 데이터가 삭제되면, 공간 낭비가 발생함
연결 리스트 :
- 임의 접근이 불가능하여, 처음부터 탐색을 진행해야 함

💬 용도

배열 : 빠른 접근이 요구되고, 데이터의 삽입과 삭제가 적을 때
연결 리스트 : 삽입과 삭제 연산이 잦고, 검색 빈도가 적을 때

Q. 배열과 링크드 리스트의 차이를 설명해주세요.

배열(Array)	연결 리스트 (Linked List)
정적 자료구조	동적 자료구조
크기를 미리 정함	크기를 정하지 않아도 됨
접근, 탐색 용이	추가, 삭제 용이
인덱스로 접근	노드로 접근

2. Stack & Queue

스택

: 어떤 자료를 쌓아서 올려놓은 형태의 자료구조

스택의 구조를 '후입선출' 즉, FILO(First In Last Out)의 구조
자료의 삽입과 삭제는 한 곳(top)에서만 이루어 진다.
스택 언더플로우(Stack Underflow)
->스택이 비어있을 때, 자료를 꺼내려고 시도를 하면 발생
스택 오버플로우(Stack Overflow)
->반대로, 스택이 꽉 차있을 때 자료를 넣으려고 하면 발생
ex) 웹 브라우저 뒤로가기, 문서작업(ctrl + z), 역순 문자열 만들기, 재귀적 알고리즘

큐

: 데이터들이 일렬로 줄 서서 기다리는 형태의 자료구조
마치 음식점 번호표나 놀이기구 대기표 같다.

선형 자료구조
큐의 구조를 선입선출 FIFO(First In First Out) 구조이다.
-> 먼저 들어간 것이 가장 먼저 나옴
작업의 우선순위, Heap 구현, BFS 에서 쓰임

우선순위 큐

: 우선순위 큐 또한 '큐'와 비슷하지만 다른 점은 들어간 ~~순서에 상관없이~~, 우선순위가 높은 데이터가 먼저 나오는 자료구조

When?
시뮬레이션 시스템, 작업 스케줄링, 수치해석 계산

배열이나 연결 리스트로 쉽게 구현이 가능

but 이들은 데이터 삽입/삭제 과정에서 데이터를 밀거나 당겨야 하는 연산이 필요

단점 : 삽입 위치를 찾기 위해 모든 데이터를 비교해야 함
=> 일반적으로 '우선순위 큐'는 힙(Heap)을 이용해서 구현한다.

힙의 시간복잡도

삽입 O(log N)
삭제 O(log N)

힙(Heap)

'우선순위 큐'를 위해 만들어진 자료구조

완전 이진트리 형태의 자료구조
-> 이진트리랑 다르게 중복값 허용 ⭕

최댓값, 최솟값을 찾을 때 유리(빨리 찾아냄)
부모 노드는 항상 자식 노드보다 큰 값을 가진다.
-> 자식 노드들의 정렬 상태는 중요치 x, 루트 노드의 값은 가장 큰 값이다.