배열(Array)와 리스트(List)의 차이


배열의 특징

  1. 같은 자료형을 가진 변수를 하나로 나타낸 것
  2. 연속된 메모리 공간으로 이루어져 있는 것
  3. 정적 표현
  4. 인덱스를 이용하여 표현
  5. 지역성을 가지고 있다

배열의 장점

  1. 인덱스를 통한 검색이 용이함
  2. 연속적이므로 메모리 관리가 편하다

배열의 단점

  1. 한 데이터를 삭제하더라도 배열은 연속적이므로 공간이 남는다. 즉, 메모리 낭비가 있다
  2. 정적이므로 배열의 크기를 컴파일 이전에 정해주어야 한다.
  3. 컴파일 이후 배열의 크기를 변동할 수 없다.

배열의 시간 복잡도

  1. 삽입/삭제
    • 배열의 맨 앞에 삽입/삭제하는 경우 : O(n)
    • 배열의 맨 뒤에 삽입/삭제하는 경우 : O(1)
    • 배열의 중간에 삽입/삭제하는 경우 : O(n)
  2. 탐색
    • O(1)

배열은 언제 사용하나?

  1. 데이터 개수가 확실하게 정해져 있을 때
  2. 데이터의 삭제와 삽입이 적을 때
  3. 검색을 해야할 때

리스트(List)의 특징

  1. 순서가 있는 데이터의 집합(데이터를 순차적으로 저장하는 선형 자료구조)
  2. 불연속적으로 메모리 공간을 차지
  3. 동적 표현-크기가 고정되어 있지 않음
  4. 인덱스가 없음-인덱스 접근이 불가능하다.
  5. 포인터를 통한 접근

리스트의 장점

  1. 포인터를 통하여 다음 데이터의 위치를 가리키고 있어 삽입 삭제가 용이하다.
  2. 동적이므로 크기가 정해져 있지 않다.
  3. 메모리의 재사용 편리
  4. 불연속적이므로 메모리 관리의 편리

리스트의 단점

  1. 검색 기능이 좋지 않다.
  2. 포인터를 통해 다음 데이터를 가리키므로 추가적인 메모리 공간 발생

리스트의 시간 복잡도

  1. 삽입/삭제
    • 리스트의 맨 앞/뒤에 삽입/삭제하는 경우 : O(1)
    • 리스트의 중간에 삽입/삭제하는 경우 : O(n) (탐색하는 시간)
  2. 탐색
    • O(n)

리스트는 언제 사용하나?

  1. 크기가 정해져 있지 않을 때
  2. 삽입과 삭제가 자주 일어날 때
  3. 검색을 자주 하지 않을 때

+유니티로 개발을 하다가 여러 객체를 만들어 걔네들 한꺼번에 관리해야 하는 일이 생겨서 배열로 할당할까 리스트로 할당할까 고민을 했었다.

지금 구현하고 있는 로직 상 검색이 많이 이루어질 것 같아 정적 배열을 선언한다음 객체를 넣었는데, 검색 시간은 그렇게 많이 차이가 나지 않고 리스트로 하는 것이 편하다고 매니저님께서 말씀해주셨다.

그래서 그냥 웬만해서는 리스트를 쓰는 게 좋겠다고 생각했다.

+ ArrayList 와 LinkedList?

Java에서는 배열(array) 이외에 ArrayList와 LinkedList 2종류의 리스트를 제공한다.

Array, Linked에서 유추할 수 있듯이 인덱스를 이용해서 데이터를 가져오는 것이 빈번하다면 내부적으로 배열을 이용하는 ArrayList가 훨씬 빠르다. 하지만 데이터의 추가/삭제가 빈번하다면 LinkedList가 훨씬 효과적이다.

list

처리하고자 하는 데이터에 따라 어떤 데이터 structure를 선택할지 판단하는 것도 대규모 시스템 구축에 필수적인 능력이다.

ArrayList

  • Array List는 배열을 이용