[Java] 배열(Array) vs. 배열리스트(ArrayList) vs. 연결리스트(LinkedList)

프롤로그

프론트엔드에서 백엔드로 전향하면서 java를 공부하기 시작했는데, 알고리즘 스터디 문제도 되도록 java로 풀려고 노력중이다.

BFS/DFS 부분을 공부하며 스터디원에게 자바에서 Array, ArrayList, LinkedList 이 3가지의 각각 차이점이 무엇인가요? 라는 질문을 받았는데 명확하게 무엇인지 몰라 이번 기회에 정리해두려고 한다.

설명 중 잘못 된 부분이 있으면 피드백 대환영입니다 :)

---

Array

• 배열이란 같은 데이터 타입의 변수들로 이루어진 자료구조로, 자바에서 기본적으로 지원하는 자료구조이다.

• 배열을 구성하는 각각의 값은 요소 혹은 원소라고 부른다.

• 배열에서의 위치를 가르키는 숫자는 인덱스라고 부른다.

• 배열의 인덱스는 0부터 시작한다. 파이썬에서는 배열과 비슷한 list에서 맨 끝 원소를 가르키는 인덱스 -1도 존재하나, Java에서 배열의 인덱스는 0을 포함한 양의 정수만가질 수 있다.

• 배열을 선언할 때 배열의 크기도 지정하게 되는데, 이는 선언 이후 변경될 수 없다. 즉, 배열의 크기는 고정적이다.

• 선언할 때 별도의 초기화를 해주지 않는다면, 배열에는 배열의 크기만큼 기본값이 채워진다.

  • 여기서 기본값이란, int배열같은 경우는 0, String 배열같은 경우는 null이다.

• 배열의 물리 주소와 논리 주소는 동일하다.

• 메모리 공간이 연속적으로 구성된다.

• 기본적으로 특정 원소에 대한 읽기와 쓰기, 배열의 길이에 대한 것만 지원한다. (java.util.Arrays 클래스에 구현되어 있는 배열을 위한 추가적인 기능들은 있음.)

• 인덱스 연산자를 사용할 수 있기에, 특정 위치에 있는 원소에 대한 접근의 시간복잡도, 특정 위치에 있는 원소를 수정하는 시간복잡도 모두 O(1)이다.

• 배열의 크기가 고정적이라 더 많은 데이터를 저장하기 위해서는 더욱 큰 배열 생성 후 이전 배열의 데이터를 새로 만든 배열로 복사해야 하는 불편함이 있다. => 새로운 배열로 데이터를 이동시키는 데에 O(n) 시간복잡도 소요
• 배열 중간에 있는 원소를 제거하거나, 배열 중간에 원소를 삽입해야 하는 경우 => 시간 복잡도는 O(n).

---

List 인터페이스

• List를 설명하기 전에 List 인터페이스라고 하는데 인터페이스가 정확하지 무엇인가에 대한 의문이 생겨 짚고 넘어가야 좋을 거 같아 간략한 설명을 첨부합니다.

  자바에서 다수의 데이터를 쉽고 효과적으로 처리할 수 있는 표준화된 방법을 제공하는 클래스의 집합을 컬렉션 프레임워크라고 한다. 이러한 컬렉션 프레임워크는 자바의 인터페이스를 사용하여 구현되며, 리스트(List)는 컬렉션 프레임워크의 주요 인터페이스 중 하나다.

• 리스트 인터페이스는 중복을 허용하면서 저장순서가 유지되는 데이터의 집합이다.
  (set 인터페이스는 순서가 없는 데이터의 집합으로, 데이터의 중복을 허용하지 않는다.)

• 배열과 다른 점은 저장 공간의 크기가 가변적이라는 점과 중간에 빈 공간을 허용하지 않는다는 점이다.

• ArrayList와 LinkedList에 대해 다뤄보려 한다.

---

ArrayList

• 내부적으로 배열(Array)을 이용하여 요소를 저장하는 자료구조로, 배열의 정적인 크기라는 한계점을 극복하기 위해 나온 자료구조이다.
• ArrayList를 선언할 때 별도의 크기는 지정해 줄 필요가 없고 크기를 관리해줄 필요도 없다.
• ArrayList의 저장 공간 크기는 가변적이다. 배열의 요소를 복사하여 새로운 배열로 옮기는 과정은 배열과 동일하며 그에 따른 시간 소요도 동일하다.
• 내부적으로 배열을 사용하기 때문에 배열 리스트 또한 물리 공간과 논리 공간이 동일하며, 그에 따라 인덱스 연산자를 활용할 수 있다.
  • **인덱스 연산자를 직접 활용하는 것이 아니라, get 혹은 set 메서드를 활용한다.
• 배열과의 큰 차이점
  • 배열 리스트의 저장 공간 크기가 가변적인 것처럼 만들어준 것.
  • 배열에서는 지원하지 않는 List 인터페이스에서 정의한 다양한 메서드를 사용할 수 있다는 점
  • 배열을 확장시키거나 중간에 원소를 삽입/삭제하여 발생하는 번거로운 일들을 메서드로 손쉽게 새결할 수 있다는 점
• 인덱스 연산자를 활용하는 get 메서드가 지원되므로, 특정 위치에 있는 원소에 대한 접근의 시간 복잡도는 O(1)이다.
  • 내부적으로 배열의 인덱스를 벗어난 곳에서 원소를 가져오려고 시도하는지 bound를 체크한다고 한다.
• 인덱스 연산자를 활용하는 set 메서드가 지원되므로, 특정 위치에 있는 원소에 대한 수정의 시간 복잡도는 O(1)이다.
  • bound를 체크한다.
• 배열 리스트의 중간에 빈 공간을 허용하지 않기 때문에 배열에 비해 메모리 공간의 낭비가 없다.
  
  
• 배열 리스트 중간에 원소를 삽입/삭제, 저장 공간을 확장 및 복사하는 과정의 시간복잡도는 O(n)이다.

---

LinkedList

• 배열 리스트는 배열의 정적인 크기라는 한계를 극복하기 위해 나온 자료구조이지만, 원소를 삽입/삭제할 때 새로운 저장 공간을 재할당하여 시간복잡도가 O(n)이라는 한계가 있었다. 연결리스트는 이러한 한계점을 극복하기 위해 나온 자료구조이다.
• 일반적인 자료구조에서 연결 리스트는 단방향 연결리스트, 양방향 연결리스트가 존재한다. 자바에서 LinkedList 컬렉션 클래스는 양방향 연결 리스트로 만들어져 있다.
• 연결 리스트의 저장 공간 크기 또한 가변적이다.
• 물리 공간과 논리 공간이 일치하지 않으며, 메모리 공간이 연속적으로 구성되어 있지 않다. => 인덱스 연산자 활용기 불가능하다. but, List 인터페이스의 구현체인 만큼 get, set 메서드를 활용할 수는 있다.
  • 배열 리스트의 get, set 메서드와 차이점 => 연결되어 있는 노드를 따라가서 n번째에 있는 노드를 찾아간다는 것

• 배열이나 배열 리스트와 달리 저장 공간 맨 앞 또는 맨 뒤에 원소를 삽입하는 시간복잡도가 O(1)이다.
• 저장 공간에 새로운 원소가 삽입되거나 삭제될 때, 저장 공간을 확장하거나 축소하여 재할당해줄 필요가 없다. 각 노드의 next와 prev라는 간선(링크)만 수정해주면 되기 때문. => 데이터 추가와 삭제에 대한 효율이 높아진다.
  
  
  
• 특정 위치에 있는 원소에 대한 접근의 시간복잡도는 O(n)이다.
• 특정 위치에 있는 원소에 대한 수정의 시간 복잡도도 O(n)이다.
• 연결 리스트 중간에 원소를 삽입하거나 삭제하는 시간복잡도 역시 O(n)이다. 결국 삽입하거나 삭제할 위치를 찾아가기 위해 탐색을 수행해야 하는데, 이 탐색의 시간복잡도가 O(n)이기 때문이다.