Java Tutorial/Collections/LinkedList

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

/*
 * 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();
    }
  }
}

Add elements at beginning and end of LinkedList

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]
*/

Adding Elements: add a single element

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

public boolean add(Object element)
public boolean add(int index, Object element)

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

Add object to LinkedList

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");
  }
}

Check if a particular element exists in LinkedList

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");
    }
  }
}

Convert a LinkedList to ArrayList

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
*/

Convert Collection to ArrayList

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);
    }
  }
}

Convert LinkedList to Array with full length array

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
*/

Convert LinkedList to Array with zero length array

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
*/

Create an object array from elements of LinkedList

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);
    }
  }
}

Get elements from LinkedList

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);
    }
  }
}

Get first and last elements from LinkedList

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());
  }
}

Get SubList from LinkedList

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);
  }
}

Helper method for creating list

/**
 * 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>();
  }
}

Implementing a Queue with LinkedList

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();
  }
}

Implementing a Stack

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);
  }
}

LinkedList: add, addFirst, addLast, remove

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);
  }
}

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

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();
  }
}

0
1
2
3
4
5
6
7
8
9

Making a stack from a LinkedList

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();
  }
}

9
9
9
8
7

Remove all elements or clear LinkedList

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);
  }
}

Remove first and last elements of LinkedList

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);
  }
}

Remove range of elements from LinkedList

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);
  }
}

Remove specified element from LinkedList

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);
  }
}

Removing Elements

public Object removeFirst()
public Object removeLast()

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

Replace an Element of LinkedList

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);
  }
}

Retrieving the Ends from a LinkedList

public Object getFirst()
public Object getLast()

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

Search elements of LinkedList

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"));
  }
}

Using a LinkedList in multi-thread

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();
  }
}

Wrap queue to synchronize the methods

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);
  }
}