Array, ArrayList, LinkedList, Stack, Queue

Array

• index로 빠르게 값을 찾는 것이 가능하다.
  • 논리적 저장 순서와 물리적 저장 순서가 일치한다.
• 선언할 때 크기를 지정해야 한다.
  • 할당할 메모리 공간 사이즈가 고정되어 있다.
  • 데이터가 계속 증가하여 최대 사이즈를 알 수 없을 때는 사용하기에 부적합하다.
• 데이터를 삽입 하거나 삭제할 때도 매우 비효율적이다.
  • ex) 4번째 index 값에 새로운 값을 넣는다고 가정할 경우 원래 값들을 뒤로 밀어내고 해당 index를 덮어 씌워야한다.

ArrayList(List)

• 크기가 고정되어 있지 않다.
• index로 데이터를 빠르게 찾을 수는 있다.
  • 논리적 저장 순서와 물리적 저장 순서가 일치한다.
  • O(1)
• 데이터 추가 및 삭제시 Array의 문제점(덮어 쓰기)을 해결할 수 있다.
  • 하지만 느리다.(데이터가 당겨지거나 밀려날 때 연산이 추가적으로 발생)
  • O(n)

LinkedList

• 노드가 연결되어 있는 방식으로 데이터가 구성되어있다.
  • 노드가 연결되어 있는 노드의 위치(주소)를 가리키는 방식으로 구성 되어 있다.
  • ex) [node1] → [node2] → [node3] …
• 데이터의 삽입 및 삭제가 빠르다.
  • 데이터 전체를 순회할 필요 없이 주소만 변경하여 연결하면 된다.
  • 다만 원하는 위치(데이터를 삽입 및 삭제하길 원하는 위치)를 순차 탐색해야한다.
  • 결과적으로 시간 복잡도는 O(n)이다.
• 값을 찾는 것은 느리다.
  • 데이터의 논리적 저장 순서와 물리적 저장 순서가 다르다.
  • index가 없기에 전체를 순회하며 찾아야한다.
  • O(n)

Stack

• Last In First Out
• 나중에 들어간 원소가 가장 먼저 나온다.

Queue

• First In First Out
• 먼저 들어간 원소가 가장 먼저 나온다.
• 참고) Java에서 Queue는 인터페이스다.