본 포스트는 '면접을 위한 CS 전공지식 노트'를 기반으로 공부한 내용을 정리한 포스트입니다.

연결 리스트

연결 리스트
연결 리스트, 링크드 리스트(linked list)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다.
출처

사진 출처

next 포인터만 있는 singly linked list
next, prev 포인터가 있는 doubly linked list

• 이중 연결 리스트 최악 시간 복잡도

자료구조	접근	탐색	삽입	삭제
이중 연결 리스트 (doubly linked list)	O(n)	O(n)	O(1)	O(1)

---

배열

일반적으로 배열은 같은 타입의 변수들로 이뤄짐
크기가 정해져 있고, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합
중복을 허용하며 순서가 있다

• 배열 최악 시간 복잡도

자료구조	접근	탐색	삽입	삭제
배열(array)	O(1)	O(n)	O(n)	O(n)

---

벡터

동적으로 요소를 할당할 수 있는 배열
중복 허용되며, 순서가 있고, 랜덤 접근이 가능함

• 벡터 최악 시간 복잡도
  • 임의의 위치 원소 접근 : O(1)
  • 맨 뒤에 원소 삽입/삭제 : 평균적으로 O(1), 최악의 경우 O(n) (꽉 차서 크기를 늘릴경우 원래있던 n개의 원소 옮겨야함)
  • 맨 뒤가 아닌 원소 삽입/삭제 : O(n)

---

스택

LIFO(Last In First Out) 성질을 가진 자료구조

• 스택 최악 시간 복잡도

자료구조	접근	탐색	삽입	삭제
스택(stack)	O(n)	O(n)	O(1)	O(1)

---

큐

FIFO (First In First Out) 성질을 가진 자료구조

• 큐 최악 시간 복잡도

자료구조	접근	탐색	삽입	삭제
큐(queue)	O(n)	O(n)	O(1)	O(1)