[Java] 읽기 전용 컬렉션(List, Set, Map), ArrayList, LinkedList, Array

List 인터페이스

• 순서가 있는 데이터의 집합
• 저장 순서가 유지되는 컬렉션을 구현하는 데 사용한다.
• 같은 요소의 중복 저장을 허용한다.
• 배열과 마찬가지로 index 로 요소를 접근하다.
• 리스트는 데이터 양에 따라 동적으로 크기가 조정될 수 있는 가변적인 구조인 반면, 배열은 고정된 크기를 가진다.
• 요소 사이에 빈공간을 허용하지 않아 삽입/삭제할 때마다 배열 이동이 일어난다.

 

ArrayList 클래스

• 배열을 이용하여 만든 리스트(배열 기반의 리스트 구현체)
• 데이터가 메모리 상에서 연속적인 공간에 데이터를 저장되는 자료구조
• 데이터의 저장순서가 유지되고 중복을 허용한다.
• 데이터량에 따라 공간이 자동으로 늘어나거나 줄어든다.
• 단방향 포인터 구조로 자료에 대한 순차적인 접근에 강점이 있어 조회가 빠르다.
• 삽입/삭제가 느리다. 단, 순차적으로 추가/삭제 하는 경우에는 가장 빠르다.

 

LinkedList 클래스

• 데이터가 메모리 상의 임의의 위치에 저장되는 자료구조
• 노드(객체)를 연결하여 리스트처럼 만든 컬렉션
• Doubly LinkedList(양방향 포인터 구조)로 이루어져 있다.
  • 각 노드는 다음 노드와 이전 노드를 가리키는 두 개의 참조를 포함하여, 리스트의 양쪽에서 탐색할 수 있도록 한다.
• 데이터의 중간 삽입, 삭제가 빈번할 경우 노드의 포인터만 변경하면 되기 때문에 빠른 성능을 보장한다.
• 특정 요소에 접근하려면 리스트의 시작부터 순차적으로 탐색해야 하기 때문에, 임의의 요소에 대한 접근 성능은 좋지 않다.
• 리스트 용도 이외에도 스택, 큐, 트리 등의 자료구조의 근간이 된다.

---

Set 인터페이스

• 데이터의 중복을 허용하지 않고 순서를 유지하지 않는 데이터의 집합 리스트
• 순서 자체가 없으므로 인덱스로 객체를 검색해서 가져오는 get(index) 메서드도 존재하지 않는다.
• 중복 저장이 불가능하기 때문에, 심지어 null 값도 하나만 저장할 수 있다.

---

Map 인터페이스

• 키와 값의 쌍으로 연관지어 이루어진 데이터의 집합
• 값은 중복되서 저장될 수 있지만, 키는 해당 Map 에서 고유해야만 한다.
• 만일 기존에 저장된 데이터와 중복된 키와 값을 저장하면, 기존의 값은 없어지고 마지막에 저장된 값이 남게 된다.
• 저장 순서가 유지 되지 않는다.

---

Array (배열)

• 하나의 변수에 여러 값을 저장하기 위해 연속된 메모리 공간을 차지하는 정적(Static)인 자료구조
• 연속적인 공간 다음의 공간이 비어 있을지 알 수 없기 때문에 안정성을 위해 배열의 크기는 생성할 때 정해지며, 이후에는 배열의 크기를 늘리거나 줄일 수 없다. (정적)
• 연속적인 공간을 차지하기 때문에, 특정 위치의 변수에 대한 *랜덤 엑세스이 가능하여 접근 속도가 빠르다.
  • 랜덤 엑세스(Random access) : 데이터 구조에서 특정 위치의 데이터에 직접 접근할 수 있는 기능
  • 찾고자 하는 원소의 위치만 안다면, O(1)의 시간 복잡도로 접근이 가능하다.
• 검색 : 크기 N 의 배열에서 검색을 하기 위해서는 처음부터 하나하나 확인을 하며 찾아가야 하기 때문에 O(N)의 시간 복잡도가 필요하다.

---

🧱 Java Collections Framework 종류 💯 총정리

Kotlin에서 Array(배열)은 어떻게 동작하는가? Array의 동작방식과 시간 복잡도, 공간 복잡도 정리