[Data Structure] Array, ArrayList, Stack, Queue

• Array vs Array List
  • Array
    • 가장 기본적인 자료구조로 논리적 저장순서와 물리적 저장순서가 동일하다.
      • Index로 element에 접근할 수 있으므로 Big-O(1)에 해당한다.
      • Random Access가 가능하다
    • 삭제 또는 삽입은 시간이 더 걸린다
      • element에 접근 → 동작 필요 : O(1) + a
      • 두 경우 모두 빈공간 혹은 추가 공간에 대한 shift가 필요하기 때문에 O(n)이 필요
  • Linked List
    • 삭제와 삽입에 대한 추가 시간 할애를 해결하기 위해 Linked List를 사용한다.
    • 각각 원소들은 자기 자신 다음에 어떤 원소가 오는 지만 기억하고있다. ⇒ 그래서 중간에 끼워넣든 빼든 상관없기때문에 삭제와 삽입이 O(1)이다.
    • 그러나 원하는 위치를 찾기 위해서는 Searching의 과정이 필요하기때문에 O(n)의 시간이 추가로 소요된다.
      • Linked list는 논리적 저장순서와 물리적 저장순서가 다르기 때문이다.
    • 그럼에도 Tree에 사용되므로 중요함.

💡 Array를 기반으로한 Linked List 구현 ArrayList를 기반으로한 Linked List 구현

• Stack & Queue
  • 선형 자료구조
  • Stack
    • Last In First Out (LIFO) .= First In Last Out(FILO)
    • 차곡차곡 쌓이는 구조
  • Queue
    • First In First Out(FIFO)
    • Java Collection에서 Queue는 인터페이스이다. 이를 구현하고있는 Prioirity queue를 사용할수있다.

 

지식 출처

https://www.youtube.com/channel/UCReNwSTQ1RqDZDnG9Qz_gyg/featured

쉬운코드