В предыдущей статье мы проанализировали основную реализацию ArrayList и знали, что базовая реализация ArrayList основана на массивах, поэтому она имеет характеристики быстрого поиска и модификации при медленной вставке и удалении. LinkedList, представленный в этой статье, является еще одной реализацией интерфейса списка. Его базовый уровень основан на двунаправленном связанном списке. Следовательно, он имеет характеристики быстрого вставки и удаления при медленном поиске и модификации. Кроме того, функции очередей и стеков могут быть реализованы посредством операции двунаправленного связанного списка. Основная структура LinkedList показана на рисунке ниже.
F представляет ссылку на узел головного узла, L представляет ссылку на хвостовой узел, и каждый узел в связанном списке имеет три элемента, а именно ссылку на прямом узл (P), значение элемента узла (E) и последующую ссылку на узла (n). Узел представлен внутренним узлом класса, давайте посмотрим на его внутреннюю структуру.
// Узел Внутренний класс Приватный статический узел класса <e> {e item; // Узел элемента <e> Далее; // Next Node Узел <e> prev; // предыдущий узел узла (узл <e> prev, e element, node <e> Далее) {this.item = element; this.next = Далее; this.prev = prev; }}Узел внутреннего класса на самом деле очень прост, только с тремя переменными членами и конструктором. Элемент представляет значение узла, следующим является ссылка на следующий узел, а Prev - это ссылка на предыдущий узел. Эти три значения передаются через конструктор. Затем давайте посмотрим на переменные участника и конструкторы LinkedList.
// Количество элементов установки переводится int size = 0; // Ссылки на узл заголовка Trackient Node <e> First; // Хвостовой узл ссылок Transient Node <e> Last; // Конструктор без параметра. addall (c);}
LinkedList содержит ссылку на узел заголовка и ссылку на хвостовой узел. Он имеет два конструктора, один из них является конструктором без параметра, а другой - конструктор, переданный внешней коллекции. В отличие от ArrayList, LinkedList не указывает начальный конструктор размера. Проверьте его методы добавления, удаления, изменения и поиска.
// добавить (добавить) public boolean add (e e) {// добавить Linklast (e); return true;} // добавить (вставить) public void add (int index, e element) {chectpositionIndex (index); if (index == size) {// добавить Linklast (element); } else {// вставить linkbefore (element, node (index)); }} // DELETE (указать индекс) public e Remove (int index) {// Проверьте, является ли подписчик Legal CheckElementex (index); вернуть Unlink (node (index));} // delete (заданный элемент) public boolean remove (object o) {if (o == null) {for (node <e> x = первое; x! вернуть истину; }}} else {// Список ссылок на транвиль для (node <e> x = first; x! = null; x = x.next) {if (o.equals (x.item)) {// delete unlink (x); вернуть истину; }}} вернуть false;} // Изменение public e set (int index, e element) {// Проверьте, является ли подписка законным контролем checkelementex (index); // Получить ссылку на узел указанного узла индекса <e> x = node (index); // Получить значение указанного узла индекса e oldval = x.item; // Установить элемент узла в новое значение x.item = element; // возвращать предыдущее значение возвращать oldval;} // проверить public e get (int index) {// Проверьте, является ли подписчик Legal CheckElementex (index); // Возвращение значения узла указанного узла возврата подписания (index) .item;}Метод добавления элементов в LinkedList в основном для вызова двух методов Linklast и Linkbefore. Метод Linklast состоит в том, чтобы связать элемент, стоящий за связанным списком, а метод Linkbefore - вставить элемент в середину связанного списка. Метод удаления LinkedList удаляет элемент из связанного списка, вызывая метод UNLINK. Давайте посмотрим на основной код операций вставки и удаления связанного списка.
// Перед ссылкой на указанный узел void linkbefore (e e, node <e> succ) {// Получить предыдущую ссылку на узел заданного узла окончательного узла <e> pred = succ.prev; // Создать новый узел, предыдущая ссылка на узел нового узла указывает на предыдущий узел данного узла // Ссылка на следующий узел нового узла указывает на заданный узел окончательного узла <e> newnode = new Node <> (Pred, E, SUCC); // укажите предыдущий узел данного узла на новый узел succ.prev = newnode; // Если предыдущий узел данного узла пуст, это означает, что заданный узел является узлом заголовка if (pred == null) {// указать ссылку на узел заголовка на новый узел First = newNode; } else {// в противном случае укажите следующую ссылку на узел на новый узел pred.next = newnode; } // Добавить количество элементов установки один размер ++; // Добавить количество модификаций One ModCount ++; } // разгрузить указанный узел e Unlink (node <e> x) {// Получить элемент заданного узла final element e element = x.item; // Получить ссылку на следующий узел данного узла окончательного узла <e> next = x.next; // Получить ссылку на предыдущий узел данного узла окончательного узла <e> prev = x.prev; // Если предыдущий узел данного узла пуст, объяснение: заданный узел является узлом заголовка if (prev == null) {// указать ссылку на узел заголовка на следующий узел данного узла First = Next; } else {// ссылаться на узел преемника предыдущего узла, указывающий на последующий узел данного узла PREV.NEXT = NEXT; // Ссылка на предыдущий узел данного узла x.prev = null; } // Если следующий узел данного узла пуст, это означает, что заданный узел представляет собой хвостовой узел, если (next == null) {// укажите ссылку на хвостовой узел на предыдущий узел данного узла Last = prev; } else {// ссылаться на прямой узел следующего узла, указывающего на предыдущий узел данного узла next.prev = prev; x.next = null; } // опустошить элемент данного узла x.item = null; // Вычитайте количество элементов установки по размеру-; // добавить modcount ++; возвратный элемент;} Linkbefore и Unlink являются репрезентативными операциями связывания узлов и удаления узлов. Другие методы связывания и удаления узлов на обоих концах похожи, поэтому мы сосредоточены на методах Linkbe и Unlink.
Диаграмма процесса Linkbe перед методом:
Диаграмма процесса метода Unlink:
Благодаря вышеупомянутой иллюстрации временная сложность операций вставки и удаления связанного списка составляет O (1), а операции поиска и модификации связанного списка требуют пересечения связанного списка для поиска элементов. Обе операции называются методом Node (Int Index) для поиска элементов, чтобы увидеть, как они определяют элементы с помощью подписок.
// Получить узел узла <e> node (int index) {// Если индекс находится в первой половине связанного списка, проверьте с начала if (index <(size >> 1)) {node <e> x = First; for (int i = 0; i <index; i ++) {x = x.next; } return x; } else {// Если индекс находится во второй половине связанного списка, проверьте из конечного узла <e> x = last; for (int i = size-1; i> index; i--) {x = x.prev; } return x; }} При позиционировании индекса сначала определите, находится ли он в верхней половине или в нижней половине связанного списка. Если это в верхней половине, начните с начала, и если это нижняя половина, начните с конца. Следовательно, временная сложность работы поиска и изменения индекса составляет O (N/2). Благодаря операции связанного списка двунаправленного связанного списка, также могут быть реализованы функции одноэтажных очередей, двусторонних очередей и стеков.
Операция в одностороннем очереди:
// Получить заголовок Node public e peek () {final Node <e> f = First; возврат (f == null)? null: f.item;} // Получить узл заголовка public e element () {return getFirst ();} // вспять узл заголовка public e опросом () {final Node <e> f = First; возврат (f == null)? null: unlinkfirst (f);} // Удалить узлом заголовка public e remove () {return removefirst ();} // Добавить узел в конце очередиДвухсторонняя операция очереди:
// Добавить публичное логическое предложениефирст (e e) {addfirst (e); return true;} // Добавить общедоступную логическую предложение (e e) {addlast (e); return true;} // Получите заголовок Node public e peekfirst () {final Node <e> f = First; возврат (f == null)? NULL: F.Item; } // Получить хвостовой узел public e peeklast () {final node <e> l = last; возврат (l == null)? null: l.item;}Операция стека:
// размещение стека public void push (e e) {addfirst (e);} // размещение стека public e pop () {return removefirst ();} Будь то односторонняя очередь, двусторонняя очередь или стек, они фактически работают на головных и хвостовых узлах связанного списка. Их реализации основаны на четырех методах: addfirst (), addlast (), removeFirst () и removeLast (). Их операции аналогичны linkbefore () и unlink (), за исключением того, что один из них должен работать на обоих концах связанного списка, а другой - работать в середине связанного списка. Можно сказать, что эти четыре метода являются особыми случаями LinkBefore () и методов Unlink (), поэтому нетрудно понять их внутренние реализации, поэтому я не буду их здесь. На этом этапе наш анализ LinkedList заканчивается, и мы суммируем ключевые моменты всего текста:
1. LinkedList реализован на основе двухстороннего списка Linked. Будь то метод сложения, удаления, модификации и поиска или реализация очередей и стеков, он может быть реализован с помощью рабочих узлов.
2. LinkedList не нуждается в том, чтобы указывать емкость заранее, потому что, основываясь на связанных операциях списка, емкость коллекции автоматически увеличится с добавлением элементов.
3. Память, занятая коллекцией после удаления LinkedList, автоматически уменьшается, и нет необходимости вызывать метод TrimtoSize (), как ArrayList
4. Все методы LinkedList не синхронизированы, поэтому он не безопасен для потока, и их следует избегать в многопоточных средах.
5. Приведенный выше анализ основан на JDK1.7, а другие версии будут иметь некоторые различия, поэтому он не может быть обобщен.
Выше всего содержание этой статьи. Я надеюсь, что это будет полезно для каждого обучения, и я надеюсь, что все будут поддерживать Wulin.com больше.