| Главная » Статьи » Java » Java Ranger Basic |
День 14/21
| Dynamic Data Structures Рассмотрим сначала статическую структуру данных. Co статической структурой и статическим наполнением – класс String. У строки неизменны ни длина, ни содержимое: String s = “Hello!”; Если посмотреть, то у класса String нет ни одного способа изменить эту строку. Там есть методы, похожие на мутацию, toUpperCase(). Однако наша строка не поменяется, а метод toUpperCase() вернет новую строку “HELLO!”. То есть принято решение, что строки в Java менять нельзя, и поэтому строки в Java – immutable. Теперь рассмотрим массив. int a = {1, 2, 3}; У массивов длина неизменна, но содержимое изменно. Эта структура не полностью статическая, ее значения можно менять: a[1] = 10; тогда массив будет {1, 10, 3}. То есть значения элементов мы можем менять, однако структура неизменна. У массивов по факту всего одна характеристика структуры – это длина. При конструировании массива сразу задается его длина и потом эта характеристика неизменна. В этом смысле массив – это статическая структура с динамическим наполнением. Если нам нужно добавить в массив еще один элемент, то фактически единственный разумный способ – это создать другой массив большего размера, при помощи System.arraycopy скопировать в него старый массив и добавить еще один элемент. Теперь рассмотрим динамические структуры данных – это структуры данных, у которых вообще все меняется. Начнем с односвязного списка, он очень напоминает массив, но его длина может увеличиваться и уменьшаться. Затем рассмотрим двусвязный список. И бинарное дерево. java.util.ArrayList – это реализация интерфейса List на основе массива. java.util.LinkedList – это дважды связанный список, также реализация List. Одна из особенностей памяти, которая используется в современных компьютерах – то, что у нее значения привязаны к местоположению. То есть если память сразу за массивом уже занята чем-то другим, то мы не сможем увеличить массив. В односвязных же списках такое сделать можно – просто в любом свободном месте выделить кусочек памяти под новый объект и дать на него ссылку. Но если свободного места в памяти нет, то JVM выдаст OutOfMemoryError. На самом деле, если посмотреть, то динамические структуры данных – это много маленьких кирпичиков, размер которых неизменен, и из которых можно сложить любую структуру. В то время как массив можно сравнить с вагоном, который нельзя увеличить или уменьшить. При удалении одного среднего элемента из массива ArrayList вызывает System.arraycopy для правой части на один элемент влево и «запоминает», что одной последней ячейки нет. В связанных списках удалить можно по-настоящему – достаточно просто пройти и записать в элементе ссылку не на следующий элемент (который мы хотим удалить), а на следующий + 1 элемент. Со временем придет Garbage Collector, найдет, что на тот объект никто не ссылается, и уберет его – то есть произойдет реальное удаление элемента, не затрагивая все остальные. Отличия связанных списков от массивов в худшую сторону: Первое – на маленьких размерах динамические структуры данных требуют в 2-3 раза больше памяти, чем массивы. Так как там по каждой ссылке хранится еще и определенная техническая информация (ссылка на следующий и/или предыдущий объект), а в массиве хранится только небольшая техническая информация – длина массива. Вторая проблема более существенна. Массив – это по сути random access memory – кусок памяти с произвольным доступом. Скорость доступа к любому элементу будет одинаковой. А в односвязном списке мы никак не сможем узнать место 1000-го элемента, мы не сможем рассчитать его, придется 1000 раз перейти по ссылкам. В массивах – тяжело менять его структурно, удалять или добавлять данные, зато легко читать и писать без изменения структуры. В односвязном списке легко менять структуру, но тяжело находить элемент. И массив, и односвязный список хороши, когда нужно читать самый левый элемент. Если нужно читать элемент справа, то массив великолепен, а список – плох. Если нужно постоянно добавлять элементы в начало – то список великолепен, а массив плох. Если нужно вставлять элементы в середину: у массивов мгновенно можно найти середину, но потом тяжело вставлять элемент; у односвязного списка долго будет идти поиск середины, но быстрая вставка. В следующей теме мы рассмотрим: Character, Charater Set Источник: http://becomejavasenior.com/courses/?utm_source=Java+Email+Courses&utm_campaign=aa710df388-JavaRangerBasicIntro&utm_medi | |
| Просмотров: 397 | | |
| Всего комментариев: 0 | |