면접을 위한 CS 전공지식 노트 (주홍철, 길벗) : 237p ~ 246p
선형 자료 구조 : 요소가 일렬로 나열되어 있는 자료 구조
1. 연결 리스트(linked list) : 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료 구조
삽입, 삭제 : O(1)
탐색 : O(n)
- 싱글 연결 리스트(단일 연결 리스트) : next 포인터만 가짐
- 이중 연결 리스트 : next 포인터, prev 포인터 가짐
- 원형 (이중) 연결 리스트 : 이중 연결 리스트와 같지만, 마지막 노드의 next 포인터가 헤드 노드(맨 앞, 즉 제일 왼쪽에 있는 노드)를 가리킴
2. 배열(array) : 같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합
중복 허용, 순서 o
탐색 : O(1) -> 랜덤 접근 가능
삽입, 삭제 : O(n)
-> 데이터 추가, 삭제 많으면 연결 리스트 / 탐색 많으면(=인덱스에 해당하는 원소를 빠르게 접근해야 하거나 간단하게 데이터를 쌓고 싶을 때) 배열 사용
* 연결 리스트 vs. 배열
| 연결 리스트 | 배열 | |
| 상자를 선으로 연결한 형태의 데이터 구조 | 상자를 순서대로 나열한 데이터 구조 | |
| 상자 안의 요소를 알기 위해서 | 하나씩 상자 내부를 확인해봐야 함 | 몇 번째 상자인지만 알면 가능 |
| 랜덤 접근 | 불가능, O(n) | 가능, O(1) |
| 탐색 | 느림 (= 상자를 열어야 하고, 주어진 선을 기반으로 순차적으로 열어야 함) | 빠름 (= 상자 위의 요소 탐색하면 됨) |
| 데이터 추가, 삭제 | 빠름 (=선 바꿔 연결해주면 됨) | 느림 (=모든 상자를 앞으로 옮겨야 추가가 가능) |
3. 벡터 : 동적으로 요소를 할당할 수 있는 동적 배열
컴파일 시점에 개수를 모르면, 벡터를 써야함
중복 허용, 랜덤 접근 가능
탐색, 맨 뒤의 요소를 삭제/삽입 : O(1)
맨 뒤나 맨 앞이 아닌 요소를 삭제/삽입 : O(n)
4. 스택(stack) : 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질을 가짐(LIFO, Last In First Out)
삽입/삭제 : O(1)
탐색 : O(n)
5. 큐(queue) : 먼저 집어 넣은 데이터가 먼저 나오는 성질(FIFO, First In First Out)
삽입/삭제 : O(1)
탐색 : O(n)
'CS > 자료구조' 카테고리의 다른 글
| [C#/자료구조]스택 , 큐 (0) | 2024.08.05 |
|---|---|
| [자료구조]복잡도 - 시간 복잡도, 빅오 표기법, 공간 복잡도 (0) | 2023.12.06 |