5.2 선형 자료 구조

'면접을 위한 CS 전공지식 노트' 책을 보며 공부한 내용입니다.

 

연결 리스트

• 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화한 것이다.
• prev와 next로 연결한다.
  • 싱글 연결 리스트: next만 사용
  • 이중 연결 리스트: prev와 next 사용
  • 원형 이중 연결 리스트: prev와 next를 사용하고, 마지막 노드의 next는 첫 노드를 가리킨다.
• 삽입과 삭제는 O(1), 탐색은 O(n)

배열

• 같은 타입의 변수들로 이루어져 있다. 
• 크기가 정해져 있고, 인접한 메모리 위치에 있는 데이터들을 모아놓은 집합이다.
• 중복을 허용하고, 순서가 있다.
• 접근(참조)에 O(1)이고 랜덤 접근이 가능하다. 삽입과 삭제는 O(n)
  
  • 랜덤 접근
    • 직접 접근
    • 동일한 시간에 배열과 같은 순차적인 데이터가 있을 때, 임의의 인덱스에 해당하는 데이터에 접근할 수 있는 기능이다.
    • 이는 데이터를 저장된 순서대로 검색하는 순차적 접근과는 반대이다. 

배열은 상자를 순서대로 나열한 데이터 구조, 몇번째 상자인지만 알면 요소를 끄집어 낼 수 있다.

연결리스트는 상자를 선으로 연결한 상태로 상자 안의 요소를 알려면 하나씩 확인해야 한다.

배열은 접근이 빠르고, 데이터 추가, 삭제가 느리다.

연결리스트는 접근이 느리고, 데이터 추가, 삭제가 빠르다.

벡터

• 동적으로 요소를 할당할 수 있는 동적 배열
• 컴파일 시점에 개수를 모르면 벡터를 사용한다.
• 중복을 허용하고, 순서가 있고, 랜덤 접근이 가능하다.
• 탐색과 맨뒤 요소 삭제는 O(1), 맨뒤가 아닌 요소를 삭제와 삽입하는 것은 O(n), 맨 뒤 요소 삽입은 O(1)

스택

• LIFO
• 삽입 삭제는 O(1), 탐색은 O(n)
• 재귀 함수, 알고리즘에 쓰이고, 웹 브라우저 방문 기록등에 쓰인다.

큐

• FIFO
• 삽입 삭제는 O(1), 탐색은 O(n)
• CPU 작업을 기다리는 프로세스, 스레드 행렬 또는 네트워크 접속을 기다리는 행렬, 너비 우선 탐색, 캐시 등에 사용한다.