기술 면접을 대비하여 대표적인 자료구조들의 개념을 정리해보았습니다.
잘못된 내용이 있다면 댓글로 알려주시면 감사하겠습니다.
자료형
Java
Java의 자료형은 크게 Primitive Type과 Reference Type으로 나뉘는데 Reference Type에는 Array, Class, Enum, Interface 등을 포함하고 있으며 Primitive Type에는 진위형(boolean), 정수(short, int, long), 실수(float, double), 문자(char)가 있다.
- Primitive Type은 Wrapper Class를 이용하여 Reference Type처럼 사용될 수 있다.
JavaScript
자바스크립트의 자료형에는 숫자형(Number), BigInt, 문자형(String), 진위형(boolean), null, undefined, Object, Symbol이 있다.
- JavaScript는 Java처럼 엄격한 자료형(Strongly Typed)을 따르지 않는다. 따라서 선언할 때 자료형이 정해지는 것이 아니라 할당할 때 정해진다.
- typeof 연산자를 통해 자료형을 확인할 수 있다.
- null은 비어있는, 존재하지 않는, 알 수 없는 값을 나타내며, undefined는 값이 할당되지 않은 상태를 나타낸다.
- 부동소수점 실수 탐구
문자열
Java
- immutable한 성질을 가지고 있다. 연산자 또는 매서드를 사용해서 변형하는 것은 새로운 문자열을 만들어내는 것이다. iterable하지 않다.
- 문자열(String)은 Reference Type의 Class Type(String Class)이지만 Primitive Type 처럼 사용된다.
- Java String의 메모리에 대한 고찰
- String, StringBuffer, StringBuilder 속도 실험
JavaScript
- immutable, iterable 성질을 가지고 있다. 따라서 str[pos]로 접근 가능
- char가 존재하지 않으며 String으로 문자와 문자열을 모두 다룬다.
선형구조
배열(Array)
선형 자료구조의 기본인 배열은 논리적 저장 순서와 물리적 저장 순서가 동일하다.
- 연속된 메모리 공간에 값을 저장하기 때문에 그 크기 만큼의 연속된 메모리 공간이 필요하다(메모리에 종속적).
- Index를 통한 접근이 가능하여 O(1)의 조회 성능을 가진다(Random Access).
- 연속성을 지키기 위해 shift연산이 사용되므로 삽입, 삭제의 성능이 떨어진다 O(n).
Java
- 선언시에 크기를 설정하여 고정된다.
- 선언시 지정한 자료형만 삽입 가능
JavaScript
- Java는 배열 본질의 요소만 가지고 있지만 JavaScript는 리스트와 같이 push(), pop(), shift(), unshift()가 구현되어 있으며 shift연산(삽입, 삭제에 따른 처리)이 자동으로 처리된다.
- 가변적인 크기를 가진다.
- Array.from 이용하여 다차원 배열 만들기 (ES6)
const array = Array.from(Array(row), () => Array(col));
리스트(List)
배열을 기반으로한 선형 자료구조로 처음, 끝, 중간 원하는 index의 데이터를 삽입, 삭제할 수 있으며 가변적인 크기를 가진다. shift연산이 자동으로 일어난다. 배열을 기반으로 하기에 조회는 O(1) 삽입, 삭제는 O(n)이다.
Java
- 선언시 지정한 자료형만 삽입 가능
- 다차원 리스트 만들기
ArrayList<ArrayList<Integer>> list; list = new ArrayList<>(); for (int i = 0; i < V + 1; ++i) { list.add(new ArrayList<>()); }
JavaScript
- JavaScript의 경우에는 배열(Array)가 리스트의 기능을 거의 다 가지고 있다. 다만 리스트의 중간에 삽입, 삭제를 위해서는 splice 매서드를 사용해야한다.
연결리스트(Linked List)
데이터 필드와 링크 필드로 이루어진 노드가 연결된 형태의 리스트로 단방향으로 연결된 단일 연결리스트(Singly Linked List)와 양방향으로 연결된 이중 연결리스트(Doubly Linked List) 그리고 마지막 노드가 다시 첫번째 노드를 가르키는 원형 연결리스트(Circular Linked List)가 있다.
- index 기반의 Random Access가 가능한 Array List와 다르게 head부터 target까지 순차적으로 탐색해야하므로 조회는 O(n)의 시간 복잡도를 가진다.
- 링크의 끊음과 맺음으로 연결되는 Linked List는 삽입과 삭제에서 O(1)의 시간 복잡도를 가진다. 하지만 실질적으로 사용할때 삭제 또는 삽입하려는 위치를 찾기위해 조회를 포함하기 때문에 O(n)이라고 할 수 있다.
Java
- Java의 LinkedList 컬렉션은 기본적으로 이중 연결리스트(Doubly Linked List)로 구현되어 있다.
- 직접 구현시 제네릭을 이용하여 자료구조의 데이터 형을 지정할 수 있다.
스택(Stack)
한쪽 끝에서만 자료를 삽입, 삭제할 수 있는 LIFO(Last In First Out)구조의 자료구조, 삽입 또는 삭제시에는 O(1)의 시간복잡도를 가지며 조회는 O(n)을 가진다. 하지만 대부분의 경우에 스택은 조회를 위한 용도로 사용되지 않는다.
Java
- Vector를 상속하는 Stack 클래스로 구현되어 있다.
- Stack 클래스는 push(), pop(), peek(), empty(), search() 매서드를 구현하고 있다.
- Vector는 Object 배열을 가지고있다.
JavaScript
- Stack의 구현체가 따로 존재하지 않지만 배열이 push(), pop() 매서드를 가지고 있어 배열을 Stack으로 활용할 수 있다.
큐(Queue)
한쪽 끝에서는 삽입만이 다른 한쪽 끝에서는 삭제만이 일어나는 FIFO(First In First Out)구조의 자료구조, 삽입 또는 삭제시에는 O(1)의 시간복잡도를 가지며 조회는 O(n)을 가진다.
- 구현방법에 따라서 선형 큐(Linear Queue), 환형 큐(Circular Queue)로 나뉜다.
- 특정 우선순위를 기준으로 삭제 연산이 일어나는 우선순위 큐(Priority Queue)도 존재한다.
Java
- Queue는 Interface로 구현되어있다. 그 구현체는 보통 LinkedList 클래스를 사용한다.
Queue<E> queue = new LinkedList<>(); - PriorityQueue는 별도의 클래스를 가진다. 삽입, 삭제시에 내부 데이터를 재정렬한다.
PriorityQueue<E> priorityQueue = new PriorityQueue<>();
JavaScript
- Queue의 구현체가 따로 존재하지 않지만 배열이 push(), shift() 매서드를 가지고 있어서 배열을 Queue로 활용할 수 있다.
덱(Deque)
양쪽 끝에서 삽입과 삭제가 가능한 형태의 자료구조다. 스택(Stack)과 큐(Queue)을 결합한 형태라고 보면 된다. 마찬가지로 삽입, 삭제는 O(1)의 시간복잡도를 조회에는 O(n)을 가진다.
Java
- Deque은 Interface로 구현되어있다. 그 구현체는 보통 LinkedList 클래스를 사용한다.
Deque<E> deque = new LinkedList<>();
JavaScript
- Deque의 구현체가 따로 존재하지 않지만 배열이 push(), pop(), shift(), unshift() 매서드를 가지고 있어서 배열을 Deque로 활용할 수 있다.
비선형구조
트리(Tree)
노드와 간선으로 이루어진 비선형 자료구조로 계층적 관계를 표현한다. 싸이클이 없는 하나의 연결 그래프 또는 DAG(Directed Acyclic Graph, 방향성이 있는 비순환 그래프)의 한 종류다.
- 간선의 개수는 노드의 개수 - 1 이다.
- 두 개의 정점 사이에는 한 개의 간선만 존재한다.
- 트리는 데이터 필드와, 양쪽 링크 필드를 가진 노드를 서로 이어서 구현한다.
- 그래프의 일종이기 때문에 인접 행렬, 인접 리스트로 표현이 가능하며 완전 이진 트리는 배열로 표현 및 구현이 가능하다.
힙(Heap)
완전 이진 트리의 일종으로 여러 개의 값들 중에서 최댓값 혹은 최솟값을 빠르게 찾기위해 만들어진 자료구조다. O(logn)의 시간복잡도를 가지고 있다. 우선순위 큐를 힙으로 구현하면 가장 빠르다.
- 최대 힙(Max Heap)
- 부모 노드의 값이 자식 노드의 값보다 크거나 같은 완전 이진 트리
- 최소 힙(Min Heap)
- 부모 노드의 값이 자식 노드의 값보다 작거나 같은 완전 이진 트리
그래프(Graph)
정점과 정점 사이를 연결하는 간선으로 이루어진 자료구조로 객체간의 관계를 나타내는데 사용된다. 그래프의 종류는 다음과 같다.
- 간선의 방향성에 따라 방향 그래프, 무방향 그래프로 나뉜다.
- 간선에 비용이나 가중치가 할당된 가중치 그래프
- 싸이클의 여부에 따라서 싸이클과 비순환 그래프
그래프는 인접 리스트 혹은 인접 행렬로 구현한다.
- 인접 리스트
- 희소 그래프(Sparse Graph)를 표현하는 경우에 좋다.
- 전체 조회에 O(N + E)의 시간복잡도를 가진다. (N: 정점의 수, E: 간선의 수)
- 인접 행렬
- 밀집 그래프(Dense Graph)를 표현하는 경우에 좋다.
- 전체 조회에 O(N^2)의 시간복잡도를 가진다. (N: 정점의 수)
그래프의 탐색은 넓이 우선 탐색(BFS)와 깊이 우선 탐색(DFS)가 사용된다.
