LinkedList

LinkedList тоже реализует базовый интерфейс List, как и ArrayList, но выполняет некоторые операции (например, вставку и удаление в середине списка) более эффективно, чем ArrayList. И наоборот, операции произвольного доступа выпол­няются им с меньшей эффективностью. Класс LinkedList также содержит методы, позволяющие использовать его в качестве стека, очереди (Queue) или двусторонней очереди (дека). Некоторые из этих методов являются псевдонимами или модификациями для получения имен, более знакомых в контексте некоторого использования. Например, методы getFirst() и element() идентичны — они возвращают начало (первый элемент) списка без его удаления и выдают исключение NoSuchElementException для пустого списка. Метод peek() представляет собой небольшую модификацию этих двух методов: он возвращает null для пустого списка. Метод addFirst() вставляет элемент в начало списка. Метод offer() делает то же, что add() и addLast() — он добавляет элемент в конец списка. Метод removeLast() удаляет и возвращает последний элемент списка. Следующий пример демонстрирует схожие и различающиеся аспекты этих методов:

//: holding/LinkedListFeatures.java

import typeinfo.pets.*;

import java.util.*;

import static net.mindview.util.Print.*;

public class LinkedListFeatures {

public static void main(String[] args) {

LinkedList<Pet> pets =

new LinkedList<Pet>(Pets.arrayList(5));

print(pets);

// Идентично

print("pets.getFirst(): " + pets.getFirst());

print("pets.element(): " + pets.element());

// Различие проявляется только для пустых списков:

print("pets.peek(): " + pets.peek());

// Идентично, удаление и возврат первого элемента.

print("pets.remove(): " + pets.remove());

print("pets.removeFirst(): " + pets.removeFirst());

// Различие проявляется только для пустых списков:

print("pets.poll(): " + pets.poll());

print(pets);

pets.addFirst(new Rat());

print("After addFirst(): " + pets);

pets.offer(Pets.randomPet());

print("After offer(): " + pets);

pets.add(Pets.randomPet());

print("After add(): " + pets);

pets.addLast(new Hamster());

print("After addLast(): " + pets);

print("pets.removeLast(): " + pets.removeLast());

}

}

<spoiler text="Output:">

[Rat, Manx, Cymric, Mutt, Pug]

pets.getFirst(): Rat

pets.element(): Rat

pets.peek(): Rat

pets.remove(): Rat

pets.removeFirst(): Manx

pets.poll(): Cymric

[Mutt, Pug]

After addFirst(): [Rat, Mutt, Pug]

After offer(): [Rat, Mutt, Pug, Cymric]

After add(): [Rat, Mutt, Pug, Cymric, Pug]

After addLast(): [Rat, Mutt, Pug, Cymric, Pug, Hamster]

pets.removeLast(): Hamster

</spoiler> Результат Pets.arrayList() передается конструктору LinkedList для заполнения. Присмотревшись к интерфейсу Queue, вы найдете в нем методы element(), offer(), peek(), poll() и remove(), добавленные в LinkedList для использования в реализации очереди (см. далее).

Стек

Стек часто называют контейнером, работающим по принципу «первым вошел, последним вышел» (LIFO). То есть элемент, последним занесенный в стек, будет первым, полученным при извлечении из стека. В классе LinkedList имеются методы, напрямую реализующие функциональность стека, поэтому вы просто используете LinkedList, не создавая для стека новый класс. Впрочем, иногда отдельный класс для контейнера-стека лучше справляется с задачей:

//: net/mindview/util/Stack.java

// Making a stack from a LinkedList.

package net.mindview.util;

import java.util.LinkedList;

public class Stack<T> {

private LinkedList<T> storage = new LinkedList<T>();

public void push(T v) { storage.addFirst(v); }

public T peek() { return storage.getFirst(); }

public T pop() { return storage.removeFirst(); }

public boolean empty() { return storage.isEmpty(); }

public String toString() { return storage.toString(); }

}

Это простейший пример определения класса с использованием параметризации. Суффикс <Т> после имени класса сообщает компилятору, что тип является параметризованным по типу Т — при использовании класса на место Т будет подставлен фактический тип. Фактически такое определение означает: «Мы определяем класс Stack для хранения объектов типа Т». Stack реализуется на базе LinkedList, также предназначенного для хранения типа Т. Обратите внимание: метод push() получает объект типа Т, а методы реек() и рор() возвращают объект типа Т. Метод реек() возвращает верхний элемент без извлечения из стека, а метод рор() удаляет и возвращает верхний элемент. Простой пример использования нового класса Stack:

//: holding/StackTest.java

import net.mindview.util.*;

public class StackTest {

public static void main(String[] args) {

Stack<String> stack = new Stack<String>();

for(String s : "My dog has fleas".split(" "))

stack.push(s);

while(!stack.empty())

System.out.print(stack.pop() + " ");

}

}

<spoiler text="Output:">

fleas has dog My

</spoiler> Если вы хотите использовать класс Stack в своем коде, вам придется либо полностью указать пакет, либо изменить имя класса при создании объекта; в противном случае, скорее всего, возникнет конфликт с классом Stack из пакета java.util. Пример использования имен пакетов при импортировании java.util.* в предыдущем примере:

//: holding/StackCollision.java

import net.mindview.util.*;

public class StackCollision {

public static void main(String[] args) {

net.mindview.util.Stack<String> stack =

new net.mindview.util.Stack<String>();

for(String s : "My dog has fleas".split(" "))

stack.push(s);

while(!stack.empty())

System.out.print(stack.pop() + " ");

System.out.println();

java.util.Stack<String> stack2 =

new java.util.Stack<String>();

for(String s : "My dog has fleas".split(" "))

stack2.push(s);

while(!stack2.empty())

System.out.print(stack2.pop() + " ");

}

}

<spoiler text="Output:"> fleas has dog My fleas has dog My </spoiler> В java.util нет общего интерфейса Stack — вероятно, из-за того, что имя было задействовано в исходной, неудачно спроектированной версии java.util.Stack для Java 1.0. Хотя класс java.util.Stack существует,LinkedList обеспечивает более качественную реализацию стека, и решение net.mindview.util.Stack является предпочтительным.