[Java] 배열(Array), ArrayList, LinkedList

 

1. 배열(Array)

1-1. 배열이란?

그림1. 배열(Array)

입력된 데이터가 메모리 공간에 연속적으로 저장되는 자료 구조이다. 메모리에 연속적으로 저장된다는 특징으로 인해 index를 통해 데이터에 접근이 가능하다. 연속적으로 저장하기 위해서는 미리 메모리의 크기를 할당받아야 하므로, 배열을 생성 후 크기를 수정할 수 없다.

 

1-2. 시간복잡도

• 삽입
  • 배열의 끝에 데이터를 삽입하는 경우 : O(1)
  • 끝이 아닌 처음이나 중간에 삽입하는 경우 : O(N)

전자의 경우 삽입될 메모리의 영역을 알고 있기 때문에 바로 삽입할 수 있다. 후자의 경우 특정 위치에 데이터를 삽입하게 되면 삽입된 지점 이후의 데이터를 뒤로 복사하여 이동시켜야 한다.

• 탐색
  • 특정 인덱스(Index) 탐색 : O(1)
  • 모든 데이터 탐색 : O(N)

배열의 특징으로 연속적으로 메모리가 할당되기 때문에, 데이터가 저장된 메모리 영역(Index)만 알면 바로 데이터를 가져올 수 있다.

• 삭제
  • 배열의 끝에 저장된 데이터 삭제 : O(1)
  • 특정 지점의 데이터를 삭제 : O(N)

삭제의 경우도 삽입과 동일한 이유로 시간 복잡도가 차이 난다.

 

 

2. 연결 리스트(LinkedList)

2-1. 연결 리스트란?

그림2. LinkedList

연결 리스트는 여러 개의 노드(Node)들이 연결된 형태를 갖는 자료 구조이며, 첫 번째 노드를 Head, 마지막 노드를 Tail이라고 한다. 각 노드는 데이터와 다음 노드를 가리키는 포인터로 구성된다.

 

배열과 달리 메모리를 연속적으로 사용하지 않기 때문에 포인터를 사용하여 노드들을 서로 가리킨다. 이는 순차적으로 데이터를 탐색해야 하나, 데이터 삽입 및 삭제 시에는 배열에 비해 유리하다.

 

2-2. 시간 복잡도

• 삽입
  • 연결 리스트의 처음에 삽입 : O(1)
  • 연결 리스트의 중간에 삽입 : O(N) → 탐색 시간 소요
  • 연결 리스트 끝에 삽입
    • 끝을 가리키는 포인터가 있을 경우 : O(1)
    • 끝을 가리키는 포인터가 없을 경우 : O(N) → 탐색 시간 필요

즉, 삽입 자체의 시간은 O(1)이 발생되나 삽입해야 하는 공간을 찾을 때 Head 노드부터 탐색해야 하므로 O(N) 시간이 발생한다.

• 탐색
  • 발생 시간 : O(N)

연결 리스트는 메모리를 연속적으로 사용하지 않기 때문에 Index가 존재하지 않는다. 따라서 모든 노드를 탐색해야 한다.

• 삭제

삽입과 동일하게 노드 삭제 자체는 O(1) 시간이 소요되나, Head 노드부터 삭제할 노드를 순차적으로 탐색이 필요한 경우 O(N) 시간이 발생한다.

 

 

3. Array vs LinkedList

그림3. Array와 LinkedList

 

 

4. 배열 리스트(ArrayList)

4-1. 배열 리스트란?

그림4. ArrayList

배열(Array)의 경우 메모리를 할당한 경우 나중에 크기를 수정할 수 없다. 이를 해결한 것이 ArrayList인데, 내부적으로 배열을 사용하지만 필요에 따라 자동으로 크기를 조절하여 메모리를 추가로 할당할 수 있다. 이 과정에서 기존의 데이터를 새로운 크기의 배열로 복사하는 작업이 필요한데, 기존 배열에 저장된 데이터가 많을수록 비용이 크게 발생한다.

 

배열과 마찬가지로 Index를 통해 데이터에 접근할 수 있고, 추가로 설정된 저장 공간을 초과하면 자동으로 부족한 만큼 용량을 늘린다. 또한 사진에서 볼 수 있듯이, 삽입 및 삭제에서 배열과 동일하게 중간 위치의 데이터를 작업을 하게 되면 복사가 발생한다.