Java Tutorial/Collections/LinkedList

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 $Revision: 1174 $
* 
* $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>

[X, A, B, C, D, Z]

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

1. public LinkedList(): creating an empty list
2. public LinkedList(Collection col): copy constructor

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>

0
1
2
3
4
5
6
7
8
9

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>

9
9
9
8
7

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>

[X, A, B, C, D, Z]
X
Z
[A, B, C, D]

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>

[X, A, B, C, D, Z]
X
Z

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>