Java의 동적 배열

다양한 수준의 복잡성을 지닌 프로그램을 만들 때 각 개발자는 배열을 포함한 다양한 데이터 유형을 사용합니다. 이 구조는 한 가지 유형의 세트를 저장하는 데 매우 적합하고 뛰어난 성능을 제공하며 일반적으로 편리합니다. 배열의 중요한 단점은 정적이라는 점입니다. 크기를 미리 지정해야 합니다. 그러나 프로그래머는 아직 미래를 예측하는 방법을 모릅니다 (물론 정보를 엄청나게 빠르게 처리하고 모든 이벤트를 예측할 수 있는 AI가 나타나지 않는 한). 이러한 이유로 우리는 프로그램이 실행되는 동안 크기를 변경할 수 있는 구조를 만들었습니다. 이를 동적 배열 이라고 합니다 .

JavaRush 과정의 동적 배열

이 주제는 Java Syntax 퀘스트의 JavaRush 과정 레벨 7 과 부분적으로 레벨 8 에서 매우 이해하기 쉽고 명확하게 다루어집니다 . 여러 강의와 최대 18개의 문제를 통해 주요 문제, 동적 배열 유형 및 성능을 포함한 이들 간의 차이점을 다룹니다. 동적 배열은 개발자의 우울증과 두통을 완화하고 엄청난 시간을 절약해주기 때문에 이 주제는 매우 중요합니다.

동적 배열이란 무엇입니까?

동적 배열은 프로그램 실행 중에 크기를 변경할 수 있는 배열입니다. Java에서는 주로 ArrayList 및 LinkedList 클래스가 이 역할을 수행합니다. 배열과 달리 ArrayList 및 LinkedList에는 참조 데이터 유형만 포함됩니다. 즉, 객체만 저장할 수 있습니다. 다행스럽게도 Java에는 기본 유형을 동적 배열에 저장할 수 있는 자동 박싱 및 자동 언박싱 메커니즘이 있습니다. 정적 배열과 마찬가지로 동적 배열은 동종입니다. 즉, 단일 데이터 유형을 저장할 수 있습니다. 그러나 상속 메커니즘과 인터페이스의 적절한 사용 덕분에 하나의 공통 클래스에서 상속된 다양한 클래스 전체를 하나의 동적 배열에 저장할 수 있습니다. 이에 대해서는 아래에서 자세히 설명합니다. 즉, 정적 배열은 다음과 같이 작동합니다. 그리고 Java의 동적 배열은 다음과 같이 작동합니다(세 번째 단계의 다이어그램을 계속합니다). Java에서는 배열을 복사하는 데 특별한 기본 함수가 사용됩니다. "별로 비싸지 않아요.

동적 배열이 필요한 이유는 무엇입니까?

Java의 동적 배열은 프로그램 작성 시 크기를 알 수 없는 동종 데이터 세트를 처리하는 데 사용됩니다. 예를 들어, 현재 애플리케이션을 사용하고 있는 모든 클라이언트의 데이터를 캐시할 수 있습니다. 그러한 고객의 수를 미리 예측하는 것은 불가능합니다. 동적 배열이 없으면 다음 옵션을 사용하여 이 문제를 해결할 수 있습니다.

1. 요구 사항을 100% 충족할 수 있는 대규모 어레이를 만듭니다.
2. 버퍼 역할을 할 정적 배열을 만듭니다.
3. 세트와 같은 다른 동적 구조를 적용합니다.

첫 번째 옵션은 범위가 엄격하게 제한된 경우에만 적합합니다. 다른 경우에는 이러한 배열이 많은 양의 메모리 공간을 차지하므로 매우 비효율적입니다. 두 번째는 버퍼 지우기, 읽기 등을 위한 추가 메커니즘의 구현이 필요합니다. 세 번째도 기능의 차이로 인해 단점이 있습니다.

Java에서 동적 배열의 기능은 무엇입니까?

Java 언어에서 ArrayList 및 LinkedList 클래스는 동적 배열 역할을 합니다. 가장 일반적으로 사용되는 것은 ArrayList입니다. 이는 이중 연결 목록 개념을 구현하는 LinkedList와 달리 고전적인 배열로 작동하기 때문입니다. 이에 대해서는 조금 나중에 이야기하겠습니다.

ArrayList, LinkedList - 개념 및 운영 규칙

ArrayList는 프로그램 실행 중에 확장할 수 있는 고전적인 배열입니다. 이는 일반 배열을 기반으로 합니다. 생성 시 크기는 10개 요소입니다. 크기가 커지면 용량도 늘어납니다. ArrayList가 작동하는 규칙은 다음과 같습니다.

• 정적 배열과 마찬가지로 0부터 인덱스가 지정됩니다.
• 끝에 삽입하고 인덱스를 통한 액세스가 매우 빠릅니다. - O(1);
• 시작 또는 중간에 요소를 삽입하려면 모든 요소를 ​​한 셀 오른쪽으로 복사한 다음 필요한 위치에 새 요소를 붙여넣어야 합니다.
• 값에 의한 접근은 요소의 수에 따라 달라집니다 - O(n);
• 기존 배열과 달리 null을 저장할 수 있습니다.

LinkedList의 경우 모든 것이 조금 더 복잡합니다. 이는 이중 연결 목록을 기반으로 합니다. 즉, 구조적으로 이 동적 Java 배열은 서로를 참조하는 흩어져 있는 여러 개체입니다. 그림으로 설명하면 더 쉽습니다. HeadLinkedList 내부에는 요소 수에 대한 정보와 첫 번째 및 마지막 요소에 대한 링크를 저장하는 기본 개체가 있습니다 . 이제 필드 size = 0는 , first및 입니다 last = null. 이 목록에 추가된 각 요소는 별도의 내부 개체의 콘텐츠입니다. 요소를 추가해 보겠습니다 Johnny. 이제 값이 "Johnny"인 노드가 있습니다. 기본 요소의 경우 첫 번째 요소와 마지막 요소에 대한 링크는 새 노드를 가리킵니다. 이 개체에는 이전 요소와 다음 요소에 대한 링크도 있습니다. 이전 항목에 대한 링크는 이것이 첫 번째 요소이므로 항상 null이고, 다음 항목에 대한 링크는 아직 존재하지 않기 때문에 항상 null입니다. 이 문제를 해결해 보겠습니다. 값이 "Watson"인 새 요소를 추가하여 두 번째 요소가 되었습니다. next첫 번째 요소 에는 다음 요소를 가리키는 필드가 있고 새 요소에는 previous이전 요소를 가리키는 필드가 있습니다. 기본 요소의 경우 이제 마지막 요소에 대한 링크가 새 노드를 가리킵니다. 다음 다이어그램은 목록 중간에 요소를 추가하는 방법을 보여줍니다. 새 요소 "Hamish"가 추가되었습니다. 목록 중간에 삽입하려면 그림과 같이 요소에 대한 링크를 다시 할당하면 됩니다. 이 그림은 자세히 설명하지 않고 최상위 수준의 이중 연결 목록 프로세스를 설명합니다. LinkedList에 대한 내용을 요약하면 해당 작업에 대한 몇 가지 규칙을 도출할 수 있습니다.

• 배열과 마찬가지로 0부터 인덱스가 지정됩니다.
• 첫 번째와 마지막 요소에 대한 액세스는 요소 수에 의존하지 않습니다 - O(1);
• 인덱스로 요소 가져오기, 목록 중간에서 삽입 또는 삭제는 요소 수에 따라 달라집니다. - O(n);
• 반복자 메커니즘을 사용할 수 있습니다. 그러면 삽입과 삭제가 일정한 시간에 발생합니다.
• 기존 배열과 달리 null을 저장할 수 있습니다.

코드 예시

몇 가지 예를 살펴보겠습니다. 코드 조각에는 ArrayList 및 LinkedList에 대한 예제가 모두 포함되어 있습니다.

창조

// Создаем новый список
ArrayList<String> arrayList = new ArrayList<>();
// Создается новый список и указывается начальный размер внутреннего массива
ArrayList<String> arrayListLarge = new ArrayList<>(100000);

// Создаем новый LinkedList
LinkedList<String> linkedList = new LinkedList<>();

요소 추가

// Новый элемент добавляется в конец
arrayList.add("Johhny");
// Новый элемент добавляется в указанную позицию (в данном случае — в начало)
arrayList.add(0, "Watson");

// Новый элемент добавляется в конец двусвязного списка
linkedList.add("Java");
// Новый элемент добавляется в нулевую позицию списка:
linkedList.addFirst("I think");
// Новый элемент добавляется в конец списка
linkedList.addLast("language");
// Новый элемент добавляется в указанную позицию
linkedList.add(2, "is a terrific");

// Получение размера списков
int arraySize = arrayList.size(); // 2
int linkedSize = linkedList.size(); // 4

언뜻 보기에 add()AND 메소드는 addLast()동일한 기능을 수행하지만 메소드는 add()인터페이스에서 LinkedList로 왔고 List메소드는 addLast인터페이스에서 왔습니다 Deque. LinkedList는 이 두 인터페이스를 모두 구현합니다. 이 경우 상황에 가장 적합한 방법을 사용하는 것이 좋습니다. LinkedList를 큐로 사용하는 경우 addLast. LinkedList를 리스트로 사용한다면 를 사용하는 것이 적절할 것입니다 add().

요소 제거

// Удаление element по индексу
arrayList.remove(0);
// Удаление element по значению
arrayList.remove("Johnny");

// Удаление первого element в списке
linkedList.removeFirst();
// Удаление первого element в списке, фактически вызов предыдущего метода
linkedList.remove();
// Удаление последнего element в списке
linkedList.removeLast();
// Удаление первого вхождения element в список
linkedList.removeFirstOccurrence("language");
// Удаление последнего вхождения element в список
linkedList.removeLastOccurrence("Java");
// Удаление по индексу
linkedList.remove(2);

객체가 인덱스별로 삭제되면 해당 메서드는 삭제된 객체를 반환합니다. 개체가 값에 따라 삭제되는 경우(또는 LinkedList의 첫 번째 또는 마지막 요소가 삭제됨) 해당 개체를 찾아서 삭제 하면 메서드는 true를 반환하고, 그렇지 않으면 false를 반환합니다 .

요소에 접근하고 목록 검색하기

// Доступ к элементу по индексу
String arrayElement = arrayList.get(2);
// Поиск element по значению
int arrayIndex = arrayList.indexOf("Watson");
// Поиск последнего индекса вхождения element в список
int lastArrayIndex = arrayList.lastIndexOf("Watson");

// Доступ по индексу
String linkedElement = linkedList.get(3);
// Получение первого element
String firstLinkedElement = linkedList.getFirst();
// Получение последнего element
String lastLinkedElement = linkedList.getLast();

// Поиск element по значению
int linkedIndex = linkedList.indexOf("Java");
// Поиск последнего индекса вхождения element в список
int lastLinkedIndex = linkedList.lastIndexOf("Java");

순환 걷기

// Использование обычного цикла
for(int i = 0; i<arrayList.size(); i++) {
  String value = arrayList.get(i);
  System.out.println(value);
}

for(int i = 0; i<linkedList.size(); i++) {
  String value = linkedList.get(i);
  System.out.println(value);
}

// Использование цикла for-each
for(String s : arrayList) {
  System.out.println(s);
}

for(String s : linkedList) {
  System.out.println(s);
}

여기서 검색에 대해 몇 마디 말할 가치가 있습니다. indexOf()많은 초보 개발자는 목록에서 요소를 검색할 때 메서드 및 가 있음에도 불구하고 모든 요소를 ​​검색된 요소와 비교하여 루프에서 검색을 시작합니다 lastIndexOf(). contains()또한 이 메서드를 사용하여 요소가 목록에 있다는 사실을 얻을 수도 있습니다.

boolean isContainsSherlock = arrayList.contains("Sherlock");
boolean isContainsPhp = linkedList.contains("Php");

추가 자료 링크

1. ArrayList에서 요소를 제거하는 방법에 대한 훌륭한 기사가 여기에 있습니다 . 이것이 동적 Java 배열 이라는 사실 때문에 요소를 제거하는 데에는 많은 미묘함이 있습니다.
2. ArrayList의 작동 방식은 여기 에 자세히 설명되어 있습니다 .
3. LinkedList에 대해 조금 더 자세히 설명합니다.
4. ArrayList 및 LinkedList 에 대한 Habr의 기사 몇 개입니다 .