배열과 리스트

배열(Array)

• 고정된 크기를 갖는 같은 자료형의 원소들이 연속적인 즉, 논리적 저장 순서와 물리적 저장 순서가 일치한 형태로 구성된 자료구조 ⇒ 연속적인 메모리 할당 ⇒ 인덱스 사용 가능
• 시간복잡도
  • 삭제: 빈자리가 남게되어 메모리가 낭비 ⇒ 마지막 값 삭제할 때만 O(1)이고 그 외에는 O(N)
  • 삽입: 연속적인 형태 유지를 위해 shift 연산이 필요 ⇒ O(N) (맨 뒤에 추가할 것이고 배열에 공간이 남아 있으면 예외적으로 O(1))
  • 검색, 수정: 인덱스를 통한 검색과 수정이 용이 ⇒ O(1)

 

리스트(Linked List)

• 불연속적인 메모리 공간에 저장하므로 크기 제한에서 자유로움
• 노드 간에 연결을 통해 리스트로 구현된 객체
• 시간복잡도
  • 삭제: 삭제하려는 데이터의 위치가 맨 앞이면 O(1), 그 외에는 모두 O(N)
  • 삽입: 맨 앞의 경우 O(1), 그 외에는 어느 곳에 삽입하던지 O(N)
  • 검색, 수정: 처음부터 끝까지 순차적으로 검색하면서 찾음 ⇒ O(N)

 

⇒ 이 둘의 차이를 왜 알아야 하는가?

데이터의 접근, 탐색이 중요하다면 배열을 쓰고, 데이터의 추가, 삭제가 중요하면 연결 리스트를 사용하자

 

⇒ Array와 ArrayList의 차이점은 무엇인가?

길이를 조정할 수 있는가 없는가의 차이