선형 자료구조

• 자료간의 관계가 1:1인 자료구조

선형 자료구조 종류

배열

• 메모리 상에 데이터가 연속적으로 저장
• 고정된 크기
• 삽입 삭제 O(N)
• 접근 O(N)
• 높은 Cache Hit Rate

  Cache Hit Rate: CPU가 참조하고자 하는 메모리가 캐시에 존재하는 경우
  공간 지역성: 참조된 주소와 인접한 주소의 내용이 다시 참조되는 특성
  시간 지역성: 최근에 참조된 주소는 빠른 시간 내에 다시 참조되는 특성

리스트

ArrayList

• 크기가 가변적인 배열이라 생각하면 된다.
• 인덱스로 접근이 가능하다.
• 데이터가 메모리에 순차적으로 저장
• 삭제 O(N)
• 끝에 삽입시 O(1)
• 접근 O(1)

LinkedList

• 단방향과 양방향이 있다.
• 메모리 상에 데이터가 비연속적으로 저장
• 삽입 O(1)
• 삭제 O(N)
• 접근 O(N)

삽입 삭제가 빈번하면 LinkedList
조회가 빈번하면 ArrayList가 유리

스택

• 후입선출
• 재귀, DFS에 사용됨

큐

• 선입선출
• 선형 큐, 원형 큐가 있다.
• BFS, 순차적 처리가 필요할때

덱(Deque)

• 양방향 큐
• 데이터를 앞, 뒤쪽에서 모두 삽입 삭제하는 과정이 필요한 경우
• 0-1 BFS