Главная » Java » LinkedList

0

 

   Класс обеспечивает реализацию модели двусвязного списка (doubly-linked list). Характеристики производительности операций над данными объекта во многом противоположны тем, которые присущи операциям, выполняемым объектом ArrayList: трудоемкость добавления элемента в конец списка описывается, правда, той же функцией, 0(1), но все остальные методы ведут себя по-иному — добавление элемента в середину списка или удаление его оценивается функцией О(1) (поскольку выполнять копирование не требуется), а для получения объекта, расположенного на заданной позиции i, придется осуществить O(i) элементарных операций, так как перемещение к объекту по списку сопряжено с просмотром всех предыдущих объектов, начиная с первого.

   В составе класса определены два конструктора и несколько методов, полезных и уместных в контексте модели двусвязного списка.

public ()

Создает новый пустой объект .

public Ccollection coll)

Конструктор копии: создает новый объект , содержимое кот рого копируется из coll в том порядке, который устанавливается итер тором коллекции.

public object getFirst()

Возвращает первый объект в текущем списке.

 

public Object getLast()

                   Возвращает последний объект в текущем списке.

 public Object removeFirstO

                   Удаляет из текущего списка первый объект.

 public object removeLastO   ;

                  Удаляет из текущего списка последний объект.

 public void addFirst(Object elem)

                  Добавляет объект elem на первую позицию текущего списка.

 public void addLast(object elem)

Добавляет объект elem на последнюю позицию текущего списка.

  Класс — это удачный начальный выбор при проектировании очередей и иных типов списков, для которых характерно то, что большинство операций выполняется над элементами, расположенными не в конце списка. Для создания стеков и списков, пополняемых динамически по мере поступления новых элементов, более предпочтительным решением, однако, окажется класс ArrayList, поскольку он предполагает создание только одного объекта массива вместо множества объектов для каждого элемента списка. Помимо того, для обеспечения возможности последовательного просмотра содержимого ArrayList не обязательно строить объект итератора — в качестве индексов элементов могут быть использованы значения типа int. Поэтому в тех случаях, когда требуется частое сканирование данных, целесообразно пользоваться именно объектами ArrayList.

  Рассмотрим пример класса Polygon, который обеспечивает поддержку списка объектов типа Point, представляющих вершины многоугольника.

 

import Java.util.List;

 import Java.util.ArrayList;

 

public class  Polygon  {

   private List vertices = new ArrayList();

 

public void add(Point  p){

     vertices.add(p);

}

public void  remove(Point p) {

      vertices.remove(p);

}

 

public int numvertices()   {

     return vertices.size() ;

}

// ….Объявления других методов…..

 }

 

Обратите внимание, что ссылка на создаваемый объект ArrayList присваивает-полю типа List. Переменными "более абстрактных" типов следует пользо-ться во всех случаях, когда это возможно, — в рассматриваемой ситуации ъявлению переменной конкретного типа ArrayList целесообразно предпо-Сть поле абстрактного типа Li St. Если поступить именно так, впоследствии, при необходимости изменения реализации класса Polygon, скажем, в пользу , средства которого могут оказаться более эффективными, вам при. дется исправить только одну строку кода, связанную с созданием списка, — весь остальной код, возможно, изменения не потребует.

 

Источник: Арнолд, Кен, Гослинг, Джеймс, Холмс, Дэвид. Язык программирования Java. 3-е изд .. : Пер. с англ. – М. : Издательский дом «Вильяме», 2001. – 624 с. : ил. – Парал. тит. англ.

По теме:

  • Комментарии