배열(Array)와 리스트(List)의 차이
in CS on 공부, 배열, 리스트
배열의 특징
- 같은 자료형을 가진 변수를 하나로 나타낸 것
- 연속된 메모리 공간으로 이루어져 있는 것
- 정적 표현
- 인덱스를 이용하여 표현
- 지역성을 가지고 있다
배열의 장점
- 인덱스를 통한 검색이 용이함
- 연속적이므로 메모리 관리가 편하다
배열의 단점
- 한 데이터를 삭제하더라도 배열은 연속적이므로 공간이 남는다. 즉, 메모리 낭비가 있다
- 정적이므로 배열의 크기를 컴파일 이전에 정해주어야 한다.
- 컴파일 이후 배열의 크기를 변동할 수 없다.
배열의 시간 복잡도
- 삽입/삭제
- 배열의 맨 앞에 삽입/삭제하는 경우 :
O(n)
- 배열의 맨 뒤에 삽입/삭제하는 경우 :
O(1)
- 배열의 중간에 삽입/삭제하는 경우 :
O(n)
- 배열의 맨 앞에 삽입/삭제하는 경우 :
- 탐색
O(1)
배열은 언제 사용하나?
- 데이터 개수가 확실하게 정해져 있을 때
- 데이터의 삭제와 삽입이 적을 때
- 검색을 해야할 때
리스트(List)의 특징
- 순서가 있는 데이터의 집합(데이터를 순차적으로 저장하는 선형 자료구조)
- 불연속적으로 메모리 공간을 차지
- 동적 표현-크기가 고정되어 있지 않음
- 인덱스가 없음-인덱스 접근이 불가능하다.
- 포인터를 통한 접근
리스트의 장점
- 포인터를 통하여 다음 데이터의 위치를 가리키고 있어 삽입 삭제가 용이하다.
- 동적이므로 크기가 정해져 있지 않다.
- 메모리의 재사용 편리
- 불연속적이므로 메모리 관리의 편리
리스트의 단점
- 검색 기능이 좋지 않다.
- 포인터를 통해 다음 데이터를 가리키므로 추가적인 메모리 공간 발생
리스트의 시간 복잡도
- 삽입/삭제
- 리스트의 맨 앞/뒤에 삽입/삭제하는 경우 :
O(1)
- 리스트의 중간에 삽입/삭제하는 경우 :
O(n)
(탐색하는 시간)
- 리스트의 맨 앞/뒤에 삽입/삭제하는 경우 :
- 탐색
O(n)
리스트는 언제 사용하나?
- 크기가 정해져 있지 않을 때
- 삽입과 삭제가 자주 일어날 때
- 검색을 자주 하지 않을 때
+유니티로 개발을 하다가 여러 객체를 만들어 걔네들 한꺼번에 관리해야 하는 일이 생겨서 배열로 할당할까 리스트로 할당할까 고민을 했었다.
지금 구현하고 있는 로직 상 검색이 많이 이루어질 것 같아 정적 배열을 선언한다음 객체를 넣었는데, 검색 시간은 그렇게 많이 차이가 나지 않고 리스트로 하는 것이 편하다고 매니저님께서 말씀해주셨다.
그래서 그냥 웬만해서는 리스트를 쓰는 게 좋겠다고 생각했다.
+ ArrayList 와 LinkedList?
Java에서는 배열(array) 이외에 ArrayList와 LinkedList 2종류의 리스트를 제공한다.
Array, Linked에서 유추할 수 있듯이 인덱스를 이용해서 데이터를 가져오는 것이 빈번하다면 내부적으로 배열을 이용하는 ArrayList가 훨씬 빠르다. 하지만 데이터의 추가/삭제가 빈번하다면 LinkedList가 훨씬 효과적이다.
처리하고자 하는 데이터에 따라 어떤 데이터 structure를 선택할지 판단하는 것도 대규모 시스템 구축에 필수적인 능력이다.
ArrayList
- Array List는 배열을 이용