в 17:44, 31 мая 2010

2010-05-31T17:44:27Z

Новая страница

== A basic priority linked list: maintaining an individual LinkedList for each priority level. ==



<source lang="java">
/*
* JBoss, Home of Professional Open Source
* Copyright 2005, JBoss Inc., and individual contributors as indicated
* by the @authors tag. See the copyright.txt in the distribution for a
* full listing of individual contributors.
*
* This is free software; you can redistribute it and/or modify it
* under the terms of the GNU Lesser General Public License as
* published by the Free Software Foundation; either version 2.1 of
* the License, or (at your option) any later version.
*
* This software is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this software; if not, write to the Free
* Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
* 02110-1301 USA, or see the FSF site: http://www.fsf.org.
*/
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.NoSuchElementException;
/**
* A basic priority linked list
*
* It implements this by maintaining an individual LinkedList for each priority
* level.
*
* @author
* @version <tt>$Revision: 1174 $</tt>
*
* $Id: BasicPrioritizedDeque.java 1174 2006-08-02 14:14:32Z timfox $
*/
public class BasicPriorityLinkedList {
protected LinkedList[] linkedLists;
protected int priorities;
protected int size;
public BasicPriorityLinkedList(int priorities) {
this.priorities = priorities;
initDeques();
}
public void addFirst(Object obj, int priority) {
linkedLists[priority].addFirst(obj);
size++;
}
public void addLast(Object obj, int priority) {
linkedLists[priority].addLast(obj);
size++;
}
public Object removeFirst() {
Object obj = null;
// Initially we are just using a simple prioritization algorithm:
// Highest priority refs always get returned first.
// This could cause starvation of lower priority refs.
// TODO - A better prioritization algorithm
for (int i = priorities - 1; i >= 0; i--) {
LinkedList ll = linkedLists[i];
if (!ll.isEmpty()) {
obj = ll.removeFirst();
break;
}
}
if (obj != null) {
size--;
}
return obj;
}
public Object removeLast() {
Object obj = null;
// Initially we are just using a simple prioritization algorithm:
// Lowest priority refs always get returned first.
// TODO - A better prioritization algorithm
for (int i = 0; i < priorities; i++) {
LinkedList ll = linkedLists[i];
if (!ll.isEmpty()) {
obj = ll.removeLast();
}
if (obj != null) {
break;
}
}
if (obj != null) {
size--;
}
return obj;
}
public Object peekFirst() {
Object obj = null;
// Initially we are just using a simple prioritization algorithm:
// Highest priority refs always get returned first.
// This could cause starvation of lower priority refs.
// TODO - A better prioritization algorithm
for (int i = priorities - 1; i >= 0; i--) {
LinkedList ll = linkedLists[i];
if (!ll.isEmpty()) {
obj = ll.getFirst();
}
if (obj != null) {
break;
}
}
return obj;
}
public List getAll() {
List all = new ArrayList();
for (int i = priorities - 1; i >= 0; i--) {
LinkedList deque = linkedLists[i];
all.addAll(deque);
}
return all;
}
public void clear() {
initDeques();
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public ListIterator iterator() {
return new PriorityLinkedListIterator(linkedLists);
}
protected void initDeques() {
linkedLists = new LinkedList[priorities];
for (int i = 0; i < priorities; i++) {
linkedLists[i] = new LinkedList();
}
size = 0;
}
class PriorityLinkedListIterator implements ListIterator {
private LinkedList[] lists;
private int index;
private ListIterator currentIter;
PriorityLinkedListIterator(LinkedList[] lists) {
this.lists = lists;
index = lists.length - 1;
currentIter = lists[index].listIterator();
}
public void add(Object arg0) {
throw new UnsupportedOperationException();
}
public boolean hasNext() {
if (currentIter.hasNext()) {
return true;
}
while (index >= 0) {
if (index == 0 || currentIter.hasNext()) {
break;
}
index--;
currentIter = lists[index].listIterator();
}
return currentIter.hasNext();
}
public boolean hasPrevious() {
throw new UnsupportedOperationException();
}
public Object next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
return currentIter.next();
}
public int nextIndex() {
throw new UnsupportedOperationException();
}
public Object previous() {
throw new UnsupportedOperationException();
}
public int previousIndex() {
throw new UnsupportedOperationException();
}
public void remove() {
currentIter.remove();
size--;
}
public void set(Object obj) {
throw new UnsupportedOperationException();
}
}
}</source>



== Add elements at beginning and end of LinkedList ==



<source lang="java">
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<String> lList = new LinkedList<String>();
lList.add("1");
lList.add("2");
lList.add("3");
lList.add("4");
lList.add("5");
System.out.println(lList);
lList.addFirst("0");
System.out.println(lList);
lList.addLast("6");
System.out.println(lList);
}
}
/*
[1, 2, 3, 4, 5]
[0, 1, 2, 3, 4, 5]
[0, 1, 2, 3, 4, 5, 6]
*/</source>



== Adding Elements: add a single element ==

Adding the element to the end of the list unless an index is specified.



<source lang="java">
public boolean add(Object element)
public boolean add(int index, Object element)</source>



<pre class=codeResult>[X, A, B, C, D, Z]</pre>

== Add object to LinkedList ==



<source lang="java">
import java.util.LinkedList;
class Address {
private String name;
private String street;
private String city;
private String state;
private String code;
Address(String n, String s, String c, String st, String cd) {
name = n;
street = s;
city = c;
state = st;
code = cd;
}
public String toString() {
return name + " " + street + " " + city + " " + state + " " + code;
}
}
class MailList {
public static void main(String args[]) {
LinkedList<Address> ml = new LinkedList<Address>();
ml.add(new Address("A", "11 Ave", "U", "IL", "11111"));
ml.add(new Address("R", "11 Lane", "M", "IL", "22222"));
ml.add(new Address("T", "8 St", "C", "IL", "33333"));
for (Address element : ml)
System.out.println(element + "\n");
}
}</source>



== Check if a particular element exists in LinkedList ==



<source lang="java">
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<String> lList = new LinkedList<String>();
lList.add("1");
lList.add("2");
lList.add("3");
lList.add("4");
lList.add("5");
if (lList.contains("4")) {
System.out.println("LinkedList contains 4");
} else {
System.out.println("LinkedList does not contain 4");
}
}
}</source>



== Convert a LinkedList to ArrayList ==



<source lang="java">
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class Main {
public static void main(String[] args) {
LinkedList<String> myQueue = new LinkedList<String>();
myQueue.add("A");
myQueue.add("B");
myQueue.add("C");
myQueue.add("D");
List<String> myList = new ArrayList<String>(myQueue);
for (Object theFruit : myList)
System.out.println(theFruit);
}
}
/*
A
B
C
D
*/</source>



== Convert Collection to ArrayList ==



<source lang="java">
import java.util.ArrayList;
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<String> linkedList = new LinkedList<String>();
linkedList.push("A");
linkedList.push("B");
linkedList.push("C");
linkedList.push("D");
ArrayList<String> arrayList = new ArrayList<String>(linkedList);
for (String s : arrayList) {
System.out.println("s = " + s);
}
}
}</source>



== Convert LinkedList to Array with full length array ==



<source lang="java">
import java.util.LinkedList;
import java.util.List;
public class Main {
public static void main(String[] args) {
List<String> theList = new LinkedList<String>();
theList.add("A");
theList.add("B");
theList.add("C");
theList.add("D");
String[] my = theList.toArray(new String[theList.size()]);
for (int i = 0; i < my.length; i++) {
System.out.println(my[i]);
}
}
}

/*
A
B
C
D
*/</source>



== Convert LinkedList to Array with zero length array ==



<source lang="java">
import java.util.LinkedList;
import java.util.List;
public class Main {
public static void main(String[] args) {
List<String> theList = new LinkedList<String>();
theList.add("A");
theList.add("B");
theList.add("C");
theList.add("D");
String[] my = theList.toArray(new String[0]);
for (int i = 0; i < my.length; i++) {
System.out.println(my[i]);
}
}
}
/*
A
B
C
D
*/</source>



== Create an object array from elements of LinkedList ==



<source lang="java">
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<String> lList = new LinkedList<String>();
lList.add("1");
lList.add("2");
lList.add("3");
lList.add("4");
lList.add("5");
Object[] objArray = lList.toArray();
for (Object obj: objArray) {
System.out.println(obj);
}
}
}</source>



== Get elements from LinkedList ==



<source lang="java">
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<String> lList = new LinkedList<String>();
lList.add("1");
lList.add("2");
lList.add("3");
lList.add("4");
lList.add("5");
for (String str: lList) {
System.out.println(str);
}
}
}</source>



== Get first and last elements from LinkedList ==



<source lang="java">
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<String> lList = new LinkedList<String>();
lList.add("1");
lList.add("2");
lList.add("3");
lList.add("4");
lList.add("5");
System.out.println("First element of LinkedList is : " + lList.getFirst());
System.out.println("Last element of LinkedList is : " + lList.getLast());
}
}</source>



== Get SubList from LinkedList ==



<source lang="java">
import java.util.LinkedList;
import java.util.List;
public class Main {
public static void main(String[] args) {
LinkedList<String> lList = new LinkedList<String>();
lList.add("1");
lList.add("2");
lList.add("3");
lList.add("4");
lList.add("5");
System.out.println(lList);
List lst = lList.subList(1, 4);
System.out.println(lst);
lst.remove(2);
System.out.println(lst);
System.out.println(lList);
}
}</source>



== Helper method for creating list ==



<source lang="java">
/**
* Copyright (C) 2007 Google Inc.
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
*/

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
/**
* Helper methods related to {@link List}s.
*
* @author maxr@google.ru (Max Ross)
*/
public class Lists {
private Lists() { }
/**
* Construct a new {@link ArrayList}, taking advantage of type inference to
* avoid specifying the type on the rhs.
*/
public static <E> ArrayList<E> newArrayList() {
return new ArrayList<E>();
}
/**
* Construct a new {@link ArrayList} with the specified capacity, taking advantage of type inference to
* avoid specifying the type on the rhs.
*/
public static <E> ArrayList<E> newArrayListWithCapacity(int initialCapacity) {
return new ArrayList<E>(initialCapacity);
}
/**
* Construct a new {@link ArrayList} with the provided elements, taking advantage of type inference to
* avoid specifying the type on the rhs.
*/
public static <E> ArrayList<E> newArrayList(E... elements) {
ArrayList<E> set = newArrayList();
Collections.addAll(set, elements);
return set;
}
/**
* Construct a new {@link ArrayList} with the contents of the provided {@link Iterable}, taking advantage of type inference to
* avoid specifying the type on the rhs.
*/
public static <E> ArrayList<E> newArrayList(Iterable<? extends E> elements) {
ArrayList<E> list = newArrayList();
for(E e : elements) {
list.add(e);
}
return list;
}
/**
* Construct a new {@link LinkedList}, taking advantage of type inference to
* avoid specifying the type on the rhs.
*/
public static <E> LinkedList<E> newLinkedList() {
return new LinkedList<E>();
}
}</source>



== Implementing a Queue with LinkedList ==



<source lang="java">
import java.util.LinkedList;
public class Main {
public static void main(String[] argv) throws Exception {
LinkedList queue = new LinkedList();
Object object = "";
// Add to end of queue
queue.add(object);
// Get head of queue
Object o = queue.removeFirst();
}
}</source>



== Implementing a Stack ==



<source lang="java">
import java.util.Collections;
import java.util.LinkedList;
public class Main {
public static void main(String[] argv) throws Exception {
LinkedList stack = new LinkedList();
Object object = "";

stack.addFirst(object);
Object o = stack.getFirst();
stack = (LinkedList) Collections.synchronizedList(stack);
}
}</source>



== LinkedList: add, addFirst, addLast, remove ==



<source lang="java">
import java.util.LinkedList;
class LinkedListDemo {
public static void main(String args[]) {
LinkedList<String> ll = new LinkedList<String>();
ll.add("F");
ll.add("B");
ll.add("D");
ll.add("E");
ll.add("C");
ll.addLast("Z");
ll.addFirst("A");
ll.add(1, "A2");
System.out.println("Original contents of ll: " + ll);
ll.remove("F");
ll.remove(2);
System.out.println("Contents of ll after deletion: " + ll);
ll.removeFirst();
ll.removeLast();
System.out.println("ll after deleting first and last: " + ll);
String val = ll.get(2);
ll.set(2, val + " Changed");
System.out.println("ll after change: " + ll);
}
}</source>



== LinkedList Class ==

The LinkedList class is a doubly linked list, which internally maintains references to the previous and
next element at each node in the list.
Creating a LinkedList
<OL><LI>public LinkedList(): creating an empty list</LI><LI>public LinkedList(Collection col): copy constructor</LI></OL>

== Making a queue from a LinkedList ==



<source lang="java">
import java.util.LinkedList;
public class MainClass {
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());
}
}
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();
}
}</source>



<pre class=codeResult>0
1
2
3
4
5
6
7
8
9</pre>

== Making a stack from a LinkedList ==



<source lang="java">
import java.util.LinkedList;
public class MainClass {
public static void main(String[] args) {
StackL stack = new StackL();
for (int i = 0; i < 10; i++)
stack.push(i);
System.out.println(stack.top());
System.out.println(stack.top());
System.out.println(stack.pop());
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 top() {
return list.getFirst();
}
public Object pop() {
return list.removeFirst();
}
}</source>



<pre class=codeResult>9
9
9
8
7</pre>

== Remove all elements or clear LinkedList ==



<source lang="java">
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<String> lList = new LinkedList<String>();
lList.add("1");
lList.add("2");
lList.add("3");
lList.add("4");
lList.add("5");
System.out.println("LinkedList contains : " + lList);
lList.clear();
System.out.println("LinkedList now contains : " + lList);
}
}</source>



== Remove first and last elements of LinkedList ==



<source lang="java">
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<String> lList = new LinkedList<String>();
lList.add("1");
lList.add("2");
lList.add("3");
lList.add("4");
lList.add("5");
System.out.println(lList);
Object object = lList.removeFirst();
System.out.println(object + " has been removed");
System.out.println(lList);
object = lList.removeLast();
System.out.println(object + " has been removed");
System.out.println(lList);
}
}</source>



== Remove range of elements from LinkedList ==



<source lang="java">
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<String> lList = new LinkedList<String>();
lList.add("1");
lList.add("2");
lList.add("3");
lList.add("4");
lList.add("5");
System.out.println(lList);
lList.subList(2, 5).clear();
System.out.println(lList);
}
}</source>



== Remove specified element from LinkedList ==



<source lang="java">
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<String> lList = new LinkedList<String>();
lList.add("1");
lList.add("2");
lList.add("3");
lList.add("4");
lList.add("5");
System.out.println(lList);
System.out.println(lList.remove("2"));
System.out.println(lList);
Object obj = lList.remove(2);
System.out.println(obj + " has been removed from LinkedList");
System.out.println(lList);
}
}</source>



== Removing Elements ==



<source lang="java">
public Object removeFirst()
public Object removeLast()</source>



<pre class=codeResult>[X, A, B, C, D, Z]
X
Z
[A, B, C, D]</pre>

== Replace an Element of LinkedList ==



<source lang="java">
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<String> lList = new LinkedList<String>();
lList.add("1");
lList.add("2");
lList.add("3");
lList.add("4");
lList.add("5");
System.out.println(lList);
lList.set(3, "Replaced");
System.out.println(lList);
}
}</source>



== Retrieving the Ends from a LinkedList ==



<source lang="java">
public Object getFirst()
public Object getLast()</source>



<pre class=codeResult>[X, A, B, C, D, Z]
X
Z</pre>

== Search elements of LinkedList ==



<source lang="java">
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<String> lList = new LinkedList<String>();
lList.add("1");
lList.add("2");
lList.add("3");
lList.add("4");
lList.add("5");
lList.add("2");
System.out.println(lList.indexOf("2"));
System.out.println(lList.lastIndexOf("2"));
}
}</source>



== Using a LinkedList in multi-thread ==



<source lang="java">
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
class PrepareProduction implements Runnable {
private final List<String> queue;
PrepareProduction(List<String> q) {
queue = q;
}
public void run() {
queue.add("1");
queue.add("done");
}
}
class DoProduction implements Runnable {
private final List<String> queue;
DoProduction(List<String> q) {
queue = q;
}
public void run() {
String value = queue.remove(0);
while (!value.equals("*")) {
System.out.println(value);
value = queue.remove(0);
}
}
}
public class Main {
public static void main(String[] args) throws Exception {
List q = Collections.synchronizedList(new LinkedList<String>());
Thread p1 = new Thread(new PrepareProduction(q));
Thread c1 = new Thread(new DoProduction(q));
p1.start();
c1.start();
p1.join();
c1.join();
}
}</source>



== Wrap queue to synchronize the methods ==



<source lang="java">
import java.util.Collections;
import java.util.LinkedList;
public class Main {
public static void main(String[] argv) throws Exception {
LinkedList queue = new LinkedList();
Object object = "";
queue.add(object);
Object o = queue.removeFirst();
queue = (LinkedList) Collections.synchronizedList(queue);
}
}</source>

Java Tutorial/Collections/LinkedList - История изменений

Admin: 1 версия

в 17:44, 31 мая 2010

← Предыдущая	Версия 05:05, 1 июня 2010
(нет различий)