25 января 2008

java.util LinkedList

Решил познакомится поближе с возможностями данного класса.
LinkedList - это реализация интерфейса List, которая реализует все операции списка и позволяет добавлять любые элементы (включая null).  Кроме реализации интерфейса List , LinkedList реализует методы получения, удаления и вставки в начало и конец списка. Такие операции позволяют использовать рассматриваемый класс как стек, очередь и двухсторонняя очередь.
Единственный негативный момент в том, что LinkedList является не синхронизированной. Тоесть при доступе к одному объекту LinkedList из нескольких потоков, необходимо, внешними средствами синхронизовать этот объект. Например создать объект, который будет инкапсулировать наш объект и отвечает за синхронизацию синхронизацию:
List list = Collections.synchronizedList(new LinkedList(...));

Так теперь перейдём к примерам.
1. Создание стека с помощью LinkedList :

import java.util.LinkedList;
public class MainClass {
  public static void main(String[] args) {
    StackL stack = new StackL();
    stack.push("First In");
    stack.push("Second In");
    System.out.println(stack.pop());
    System.out.println(stack.pop());
  }
}
class StackL {
  private LinkedList list = new LinkedList();
  public void push(Object v) {
    list.addFirst(v);
  }   public Object pop() {
    return list.removeFirst();
  }
}

Как известно стек работает по принципу FILO (first in last out), так что результат работы нашего примера:
>Second In
>First In


2. Создание очереди с помощью LinkedList:

import java.util.LinkedList ;
public class Queue {
  private LinkedList list = new LinkedList();
  public void put(Object v) {
   list.addFirst(v);
  }
  public Object get() {
    return list.removeLast();
  }
  public boolean isEmpty() {
    return list.isEmpty();
  }
  public static void main(String[] args) {
    Queue queue = new Queue();
    for(int i = 0; i < 10; i++)
      queue.put(Integer.toString(i));
    while(!queue.isEmpty())
      System.out.println(queue.get());
  }
}

В данном примере реализован принцип очереди: FIFO (first in first out).

Как вы заметили в этих примерах были ограничены возможности класса LinkedList, потому что он (LinkedList) имеет в своём арсенале методы реализующие и стек и очередь и двухсторонню очередь.

5 комментариев:

anatolich комментирует...

1. Не FILO, а LIFO.
2. То что методы в LinkedList и ArrayList не synchronized это не недостаток, а вполне грамотное решение. Которое позволяеть использовать синхронизацию только там где это уместно дабы избегать performance leaks.

То что пишешь в блог хорошо, только вот улучше качество статей.

Rumoku комментирует...

FILO и LIFO это одно и тоже, причём термин FILO употребляется чаще.

walrus комментирует...

А зачем делать самодельную очередь если есть стандартная?

Анонимный комментирует...

не соглашусь.
используются по большинству аббревиатуры FIFO и LIFO и не как по другому. смотрите как звучит красиво 8)

Antony комментирует...

Добрый день,

Так же следует учесть, что:
Collections.synchronizedList - это условная потокобезопасность, где синхронизированы методны, но не их набор.
И в данном случае вы сможете напороться на ConcurentModificationException. Происходит это, к примеру, когда один поток бежит по списку с его итератором. А другой в этот момент меняет этот список.
В этом случае может помочь полная блокировка списка с использованием sybcronized(list) {....}, что не очень хорошо само по себе или то, что предоставляет нам java.util.concurrent.*