[자료구조 & 알고리즘] 2. 자바의 배열과 리스트

자바의 배열과 리스트

1. 배열(Array)

• 번호와 그 번호에 대응하는 데이터들로 이루어진 자료 구조

• 같은 종류의 데이터들이 메모리에 순차적으로 저장됨.

• 선언시 length를 정함.

• 랜덤 액세스가 가능

     - ※ 랜덤 액세스(Random Access)란?

          - 집합 내 요소의 수와 관계 없이 임의의 데이터에 바로 접근하는 기능.

          - 데이터에 접근하기 위해 순차적으로 조사하지 않고도 저장 장치로부터 정보의 특정 부분을 직접 검색할 수 있는 접근 방법.

     - 배열의 주소는 첫 인덱스의 주소를 배열의 주소로 함.

     - 배열은 데이터를 순차적으로 저장하고, 이 데이터들의 자료형이 모두 같기 때문에 첫 인덱스의 메모리 주소만 알면 특정 인덱스의 주소도 바로 알 수 있음.

     - ex) int형을 담고 있는 배열의 주소가 0x0000일 때 이 배열의 인덱스가 3인 요소에 접근하고 싶다면, 순차적으로 인덱스 0, 1, 2, 3을 찾을 필요없이 바로 0x000c라는 주소를 알고 접근 가능.

     - 때문에 배열은 데이터를 접근할 때 O(1)의 시간 복잡도를 가짐.

 

• 선언 및 초기화 방법

int[] nums1 = {1, 2, 3, 4}; // 선언과 초기화 동시에 할 경우

Integer[] nums2; // 선언만 먼저 하는 경우
nums2 = new Integer[] {1, 2, 3, 4} // 초기화 작업

 

2. 리스트(List)

• 자바에서 순차적인 데이터를 저장하기 위한 컬렉션 중 하나

• List 인터페이스의 구현체로는 ArrayList, LinkedList 등이 있음.

 

3. ArrayList

• 배열의 단점

     - 배열은 선언시 데이터의 크기를 정해야 함.

     - 데이터의 크기가 동적일 경우 length를 넉넉하게 하여 배열을 생성해야 하는데, 이는 메모리의 비효율 발생.

• 내부적으로 배열을 이용하지만 배열의 단점을 해소

     - ArrayList 선언시 내부적으로 적당한 크기(default값 10)의 배열이 선언됨.

     - 요소의 개수가 이 크기를 넘지 않는다면 그냥 배열과 같음.

     - 요소의 개수가 이 크기를 넘는다면 Size를 자동으로 늘려줌. 이를 Resize라고 함.

• Resize 과정

     - 현재 size보다 더 큰 배열 새로 생성

     - 기존 배열의 요소들을 새 배열에 모두 옮김. 이때 O(n)의 시간 복잡도 발생.

     - 그 후 기존 배열 삭제

 

4. LinkedList

• Node가 연결되는 형식으로 데이터를 저장

     - Node는 데이터 값과 다음 노드의 주소 값을 저장하는 구조체

• 메모리상에서는 비연속적으로 저장되어 있음.

     - 메모리 사용에 조금 더 자유로움.

• 각각의 노드가 다음 노드의 주소값을 가리킴으로써 논리적인 연속성을 갖게 됨.

     - 주소도 저장해야 하기 때문에 데이터 하나당 차지하는 메모리가 더 큼.

• 생성할 때 사이즈나 값 등을 미리 할당하지 않음. 데이터가 추가될 때 마다 노드들이 생성되어 동적으로 추가

 

※ 시간 복잡도 비교

• Array

     - 접근/수정 : O(1) -> 랜덤 액세스가 가능하기 때문

     - 맨 뒤 삽입/삭제 : O(1)

     - 중간 삽입/삭제 : O(n) -> 기존 데이터 최대 n개를 이동시켜야 하기 때문.

     - Arrays.sort : O(n²)

• ArrayList

     - 접근/수정 : O(1) -> 랜덤 액세스가 가능하기 때문

     - 맨 뒤 삽입 : 평균적으로 O(1) -> 가끔 내부의 배열 크기보다 요소가 많아질 경우, 더 큰 크기의 배열을 만드는 작업을 해야하지만, 이러한 연산은 자주 일어나느 연산이 아니기 때문에 평균적으로 O(1)의 시간 복잡도가 일어남.

     - 맨 뒤 삭제 : O(1)

     - 중간 삽입/삭제 : O(n) ->  기존 데이터 최대 n개를 이동시켜야 하기 때문.

     - Collections.sort : O(nlogn)

• LinkedList

     - 맨 앞 또는 맨 뒤 접근/수정 : O(1) -> 순차적으로 접근할 필요없이 맨 앞 또는 맨 뒤 노드에 바로 접근하여 수정.

     - 맨 앞 또는 맨 뒤 삽입/삭제 : O(1) -> 요소를 삽입할 시 그 요소와 인접한 노드의 주소만 삽입한 노드의 주소로 바꾸어주면 되고, 요소를 삭제할 시 마찬가지로 인접한 노드의 주소만 내 이전/다음 노드의 주소로 바꿔주면 되기 때문에 O(1)의 시간 복잡도.

     - 중간 접근/수정/삽입/삭제 : O(n) -> 순차적으로 연결된 노드를 따라 하나하나 검색해가며 요소를 찾아가야 하기 때문에 접근에 O(n)이 걸림.