[자료구조 리스트] 배열(Array)

  배열(Array)은 동일한 타입의 원소들이 연속적인 메모리 공간에 할당되어 각 항목이 하나의 원소에 저장되는 기본적인 자료구조입니다. 특정 원소에 접근할 때에는 배열의 인덱스를 이용하여 O(1) 시간에 접근할 수 있습니다. 그러나 새 항목을 배열 중간에 삽입하거나 중간에 있는 항목을 삭제하면, 뒤따르는 항목들을 한 칸씩 뒤로 또는 앞으로 이동시켜야 하므로 삽입이나 삭제 연산은 항상 O(1) 시간에 수행할 수 없다.

  배열은 이미 정해진 크기의 메모리 공간을 할당받은 뒤 사용해야 하므로, 빈자리가 없어 새 항목을 삽입할 수 없는 상황(Overflow)에 직면할 수도 있습니다. Overflow가 발생하면 에러 처리를 하여 프로그램을 정지시키는 방법이 주로 사용됩니다. 하지만 프로그램 안정성을 향상시키기 위해 Overflow가 발생할 때, 배열 크기를 2배로 확장합니다. 또는 배열의 3 / 4이 비어 있다면 배열 크기를 1 / 2로 축소합니다.

 

배열의 선언과 생성

• 타입[] 변수이름;
  • 배열을 선언
• 변수이름 = new 타입[길이]
  • 배열을 생성
• 타입[] 변수이름 = new 타입[길이];
  • 배열의 선언과 생성을 동시에
• 타입[] 변수이름 = new 타입{원소}
  • 배열의 선언과 초기화를 동시에
  • 'new 타입'은 생략할 수 있음
  • 배열의 선언과 생성을 따로하는 경우에는 생략 불가
  • 괄호에 아무 것도 넣지 않는 경우 길이가 0인 배열 생성

 

배열에서의 용어

• 요소(또는 원소, element): 생성된 배열의 각 저장공간
• 인덱스(index): 배열의 요소마다 붙여진 일련번호

 

배열의 장단점

• 장점
  • 인덱스를 이용하여 요소에 접근이 빠름, O(1)
  • 연속적인 메모리 공간을 이용하므로 메모리 관리 수월
• 단점
  • 요소의 삽입, 삭제가 느림 및 비효율적
  • 크기가 고정이므로 실제 크기보다 작은 경우에도 메모리가 할당되어 메모리 낭비가 발생할 수 있음

 

  ※ "자바와 함께하는 자료구조의 이해", "자바의 정석"이라는 책을 참고하여 쓴 게시글입니다. 책에는 없는 내용을 추가하여 작성된 부분이 있습니다. 문제가 되거나 부정확한 부분이 있다면 알려주시면 감사하겠습니다.

  ※ 책은 게시글보다 정확한 내용을 담고 있으며 코드, 그림, 예제를 이용하여 개념을 자세히 설명합니다.