Array, ArrayList, LinkedList, Stack, Queue

yshjft·2022년 6월 8일
0

CS 자료구조

목록 보기
1/3

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는 인터페이스다.
profile
꾸준히 나아가자 🐢

0개의 댓글