선형 자료 구조

본 포스팅은 '면접을 위한 CS 전공지식 노트'를 기반으로 작성되었습니다.

 

선형 자료 구조

• 요소가 일렬로 나열되어 있는 자료 구조

 

연결 리스트(Linked List)

• 데이터를 감싼 노드를 포인터가 연결해서 공간적인 효율성을 극대화 시킨 자료구조
• 삽입, 삭제 : O(1)
• 탐색 : O(n)

• 단일 연결 리스트: next 포인터만 가짐
• 이중 연결 리스트: next 포인터와 prev 포인터를 가짐
• 원형 이중 연결 리스트: 이중 연결 리스트와 같지만 마지막 노드의 next포인터가 헤드 노드를 가리키는 것

배열(Array)

• 같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있음.
• 인접한 메모리 위치에 있는 데이터를 모아놓은 집합
• 탐색: O(1)
• 삽입, 삭제 : O(n)

벡터(vector)

• 동적으로 요소를 할당할 수 있는 동적 배열
• 컴파일 시점에 갯수를 모르면 벡터를 써야함.
• 중복 허용, 순서 존재, 랜덤 접근 가능
• 탐색, 맨뒤 요소 삭제, 삽입 : O(1)
• 이 외에는 O(n)

스택(Stack)

• 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나옴(LIFO, Last in First out)
• 재귀적인 함수, 알고리즘에 사용, 웹 브라우저 방문 기록등에 쓰임.
• 삽입, 삭제 : O(1)
• 탐색 : O(n)

큐(Queue)

• 선입 선출(FIFO, First In First Out)
• 삽입, 삭제 : O(1)
• 탐색 : O(n)
• CPU 작업을 기다리는 프로세스, 스레드 행렬 등에 사용