Java/Collections Data Structure/Link List
Версия от 18:01, 31 мая 2010; (обсуждение)
Содержание
- 1 A class for you to extend when you want object to maintain a doubly linked list
- 2 Add elements at beginning and end of LinkedList Java example
- 3 Add or insert an element to ArrayList using Java ListIterator Example
- 4 A List helper class that attempts to avoid unneccessary List creation.
- 5 A simple Doubly Linked list class, designed to avoid O(n) behaviour on insert and delete.
- 6 Check if a particular element exists in LinkedList Java example
- 7 Checking what item is first in line without removing it: element
- 8 Convert a LinkedList to ArrayList
- 9 Convert Collection to ArrayList
- 10 Convert LinkedList to Array with full length array
- 11 Convert LinkedList to Array with zero length array
- 12 Create a list with an ordered list of strings
- 13 Create an object array from elements of LinkedList Java example
- 14 Double LinkedList
- 15 Doubly Linked list
- 16 Finding an Element in a Sorted List
- 17 Get elements from LinkedList Java example
- 18 Get first and last elements from LinkedList Java example
- 19 Get SubList from LinkedList Java example
- 20 Implementing a Queue with LinkedList
- 21 Implementing a Stack
- 22 Iterate through elements of Java LinkedList using Iterator example
- 23 Iterate through elements of Java LinkedList using ListIterator example
- 24 Making a stack from a LinkedList
- 25 Remove all elements or clear LinkedList Java example
- 26 Remove first and last elements of LinkedList Java example
- 27 Remove range of elements from LinkedList Java example
- 28 Remove specified element from LinkedList Java example
- 29 Removing the first item from the queue: poll
- 30 Replace an Element of LinkedList Java example
- 31 Search elements of LinkedList Java example
- 32 Search for a non-existent element
- 33 Single linked list
- 34 To insert an object into a specific position into the list, specify the index in the add method
- 35 Updating LinkedList Items
- 36 Use addFirst method to add value to the first position in a linked list
- 37 Use an Iterator to cycle through a collection in the forward direction.
- 38 Use for each loop to go through elements in a linkedlist
- 39 Using a LinkedList in multi-thread
- 40 Wrap queue to synchronize the methods
A class for you to extend when you want object to maintain a doubly linked list
/**
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
/**
* Provides a base class for you to extend when you want object to maintain a
* doubly linked list to other objects without using a collection class.
*
* @author chirino
*/
public class LinkedNode {
protected LinkedNode next = this;
protected LinkedNode prev = this;
protected boolean tail = true;
public LinkedNode getHeadNode() {
if (isHeadNode()) {
return this;
}
if (isTailNode()) {
return next;
}
LinkedNode rc = prev;
while (!rc.isHeadNode()) {
rc = rc.prev;
}
return rc;
}
public LinkedNode getTailNode() {
if (isTailNode()) {
return this;
}
if (isHeadNode()) {
return prev;
}
LinkedNode rc = next;
while (!rc.isTailNode()) {
rc = rc.next;
}
return rc;
}
public LinkedNode getNext() {
return tail ? null : next;
}
public LinkedNode getPrevious() {
return prev.tail ? null : prev;
}
public boolean isHeadNode() {
return prev.isTailNode();
}
public boolean isTailNode() {
return tail;
}
/**
* @param rightHead the node to link after this node.
* @return this
*/
public LinkedNode linkAfter(LinkedNode rightHead) {
if (rightHead == this) {
throw new IllegalArgumentException("You cannot link to yourself");
}
if (!rightHead.isHeadNode()) {
throw new IllegalArgumentException("You only insert nodes that are the first in a list");
}
LinkedNode rightTail = rightHead.prev;
if (tail) {
tail = false;
} else {
rightTail.tail = false;
}
rightHead.prev = this; // link the head of the right side.
rightTail.next = next; // link the tail of the right side
next.prev = rightTail; // link the head of the left side
next = rightHead; // link the tail of the left side.
return this;
}
/**
* @param leftHead the node to link after this node.
* @return
* @return this
*/
public LinkedNode linkBefore(LinkedNode leftHead) {
if (leftHead == this) {
throw new IllegalArgumentException("You cannot link to yourself");
}
if (!leftHead.isHeadNode()) {
throw new IllegalArgumentException("You only insert nodes that are the first in a list");
}
// The left side is no longer going to be a tail..
LinkedNode leftTail = leftHead.prev;
leftTail.tail = false;
leftTail.next = this; // link the tail of the left side.
leftHead.prev = prev; // link the head of the left side.
prev.next = leftHead; // link the tail of the right side.
prev = leftTail; // link the head of the right side.
return leftHead;
}
/**
* Removes this node out of the linked list it is chained in.
*/
public void unlink() {
// If we are allready unlinked...
if (prev == this) {
reset();
return;
}
if (tail) {
prev.tail = true;
}
// Update the peers links..
next.prev = prev;
prev.next = next;
// Update our links..
reset();
}
public void reset() {
next = this;
prev = this;
tail = true;
}
}
/////////////////////////////////////
/**
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package org.apache.activemq.util;
import junit.framework.TestCase;
/**
* @author chirino
*/
public class LinkedNodeTest extends TestCase {
static class IntLinkedNode extends LinkedNode {
public final int v;
public IntLinkedNode(int v) {
this.v = v;
};
@Override
public String toString() {
return "" + v;
}
}
IntLinkedNode i1 = new IntLinkedNode(1);
IntLinkedNode i2 = new IntLinkedNode(2);
IntLinkedNode i3 = new IntLinkedNode(3);
IntLinkedNode i4 = new IntLinkedNode(4);
IntLinkedNode i5 = new IntLinkedNode(5);
IntLinkedNode i6 = new IntLinkedNode(6);
public void testLinkAfter() {
i1.linkAfter(i2.linkAfter(i3));
// Order should be 1,2,3
assertTrue(i1.getNext() == i2);
assertTrue(i1.getNext().getNext() == i3);
assertNull(i1.getNext().getNext().getNext());
assertTrue(i3.getPrevious() == i2);
assertTrue(i3.getPrevious().getPrevious() == i1);
assertNull(i3.getPrevious().getPrevious().getPrevious());
assertTrue(i1.isHeadNode());
assertFalse(i1.isTailNode());
assertFalse(i2.isHeadNode());
assertFalse(i2.isTailNode());
assertTrue(i3.isTailNode());
assertFalse(i3.isHeadNode());
i1.linkAfter(i4.linkAfter(i5));
// Order should be 1,4,5,2,3
assertTrue(i1.getNext() == i4);
assertTrue(i1.getNext().getNext() == i5);
assertTrue(i1.getNext().getNext().getNext() == i2);
assertTrue(i1.getNext().getNext().getNext().getNext() == i3);
assertNull(i1.getNext().getNext().getNext().getNext().getNext());
assertTrue(i3.getPrevious() == i2);
assertTrue(i3.getPrevious().getPrevious() == i5);
assertTrue(i3.getPrevious().getPrevious().getPrevious() == i4);
assertTrue(i3.getPrevious().getPrevious().getPrevious().getPrevious() == i1);
assertNull(i3.getPrevious().getPrevious().getPrevious().getPrevious().getPrevious());
assertTrue(i1.isHeadNode());
assertFalse(i1.isTailNode());
assertFalse(i4.isHeadNode());
assertFalse(i4.isTailNode());
assertFalse(i5.isHeadNode());
assertFalse(i5.isTailNode());
assertFalse(i2.isHeadNode());
assertFalse(i2.isTailNode());
assertTrue(i3.isTailNode());
assertFalse(i3.isHeadNode());
}
public void testLinkBefore() {
i3.linkBefore(i2.linkBefore(i1));
assertTrue(i1.getNext() == i2);
assertTrue(i1.getNext().getNext() == i3);
assertNull(i1.getNext().getNext().getNext());
assertTrue(i3.getPrevious() == i2);
assertTrue(i3.getPrevious().getPrevious() == i1);
assertNull(i3.getPrevious().getPrevious().getPrevious());
assertTrue(i1.isHeadNode());
assertFalse(i1.isTailNode());
assertFalse(i2.isHeadNode());
assertFalse(i2.isTailNode());
assertTrue(i3.isTailNode());
assertFalse(i3.isHeadNode());
i2.linkBefore(i5.linkBefore(i4));
// Order should be 1,4,5,2,3
assertTrue(i1.getNext() == i4);
assertTrue(i1.getNext().getNext() == i5);
assertTrue(i1.getNext().getNext().getNext() == i2);
assertTrue(i1.getNext().getNext().getNext().getNext() == i3);
assertNull(i1.getNext().getNext().getNext().getNext().getNext());
assertTrue(i3.getPrevious() == i2);
assertTrue(i3.getPrevious().getPrevious() == i5);
assertTrue(i3.getPrevious().getPrevious().getPrevious() == i4);
assertTrue(i3.getPrevious().getPrevious().getPrevious().getPrevious() == i1);
assertNull(i3.getPrevious().getPrevious().getPrevious().getPrevious().getPrevious());
assertTrue(i1.isHeadNode());
assertFalse(i1.isTailNode());
assertFalse(i4.isHeadNode());
assertFalse(i4.isTailNode());
assertFalse(i5.isHeadNode());
assertFalse(i5.isTailNode());
assertFalse(i2.isHeadNode());
assertFalse(i2.isTailNode());
assertTrue(i3.isTailNode());
assertFalse(i3.isHeadNode());
}
public void testUnlink() {
i1.linkAfter(i2.linkAfter(i3));
i3.linkAfter(i4);
i1.linkBefore(i5);
i1.linkAfter(i6);
// Order should be 5,1,6,2,3,4
i4.unlink();
i5.unlink();
i6.unlink();
// Order should be 1,2,3
assertTrue(i1.getNext() == i2);
assertTrue(i1.getNext().getNext() == i3);
assertNull(i1.getNext().getNext().getNext());
assertTrue(i3.getPrevious() == i2);
assertTrue(i3.getPrevious().getPrevious() == i1);
assertNull(i3.getPrevious().getPrevious().getPrevious());
assertTrue(i1.isHeadNode());
assertFalse(i1.isTailNode());
assertFalse(i2.isHeadNode());
assertFalse(i2.isTailNode());
assertTrue(i3.isTailNode());
assertFalse(i3.isHeadNode());
}
}
Add elements at beginning and end of LinkedList Java example
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]
*/
Add or insert an element to ArrayList using Java ListIterator Example
import java.util.ArrayList;
import java.util.ListIterator;
public class Main {
public static void main(String[] args) {
ArrayList<String> aList = new ArrayList<String>();
aList.add("1");
aList.add("2");
aList.add("3");
aList.add("4");
aList.add("5");
ListIterator<String> listIterator = aList.listIterator();
listIterator.next();
listIterator.add("Added Element");
for (String str: aList){
System.out.println(str);
}
}
}
A List helper class that attempts to avoid unneccessary List creation.
//
// Copyright 2004-2005 Mort Bay Consulting Pty. Ltd.
// ------------------------------------------------------------------------
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
// http://www.apache.org/licenses/LICENSE-2.0
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
import java.io.Serializable;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
/* ------------------------------------------------------------ */
/** Lazy List creation.
* A List helper class that attempts to avoid unneccessary List
* creation. If a method needs to create a List to return, but it is
* expected that this will either be empty or frequently contain a
* single item, then using LazyList will avoid additional object
* creations by using Collections.EMPTY_LIST or
* Collections.singletonList where possible.
*
* <p><h4>Usage</h4>
* <pre>
* Object lazylist =null;
* while(loopCondition)
* {
* Object item = getItem();
* if (item.isToBeAdded())
* lazylist = LazyList.add(lazylist,item);
* }
* return LazyList.getList(lazylist);
* </pre>
*
* An ArrayList of default size is used as the initial LazyList.
*
* @see java.util.List
* @author Greg Wilkins (gregw)
*/
public class LazyList
implements Cloneable, Serializable
{
private static final String[] __EMTPY_STRING_ARRAY = new String[0];
/* ------------------------------------------------------------ */
private LazyList()
{}
/* ------------------------------------------------------------ */
/** Add an item to a LazyList
* @param list The list to add to or null if none yet created.
* @param item The item to add.
* @return The lazylist created or added to.
*/
public static Object add(Object list, Object item)
{
if (list==null)
{
if (item instanceof List || item==null)
{
List l = new ArrayList();
l.add(item);
return l;
}
return item;
}
if (list instanceof List)
{
((List)list).add(item);
return list;
}
List l=new ArrayList();
l.add(list);
l.add(item);
return l;
}
/* ------------------------------------------------------------ */
/** Add an item to a LazyList
* @param list The list to add to or null if none yet created.
* @param index The index to add the item at.
* @param item The item to add.
* @return The lazylist created or added to.
*/
public static Object add(Object list, int index, Object item)
{
if (list==null)
{
if (index>0 || item instanceof List || item==null)
{
List l = new ArrayList();
l.add(index,item);
return l;
}
return item;
}
if (list instanceof List)
{
((List)list).add(index,item);
return list;
}
List l=new ArrayList();
l.add(list);
l.add(index,item);
return l;
}
/* ------------------------------------------------------------ */
/** Add the contents of a Collection to a LazyList
* @param list The list to add to or null if none yet created.
* @param collection The Collection whose contents should be added.
* @return The lazylist created or added to.
*/
public static Object addCollection(Object list, Collection collection)
{
Iterator i=collection.iterator();
while(i.hasNext())
list=LazyList.add(list,i.next());
return list;
}
/* ------------------------------------------------------------ */
/** Add the contents of an array to a LazyList
* @param list The list to add to or null if none yet created.
* @param collection The Collection whose contents should be added.
* @return The lazylist created or added to.
*/
public static Object addArray(Object list, Object[] array)
{
for(int i=0;array!=null && i<array.length;i++)
list=LazyList.add(list,array[i]);
return list;
}
/* ------------------------------------------------------------ */
/** Ensure the capcity of the underlying list.
*
*/
public static Object ensureSize(Object list, int initialSize)
{
if (list==null)
return new ArrayList(initialSize);
if (list instanceof ArrayList)
{
ArrayList ol=(ArrayList)list;
if (ol.size()>initialSize)
return ol;
ArrayList nl = new ArrayList(initialSize);
nl.addAll(ol);
return nl;
}
List l= new ArrayList(initialSize);
l.add(list);
return l;
}
/* ------------------------------------------------------------ */
public static Object remove(Object list, Object o)
{
if (list==null)
return null;
if (list instanceof List)
{
List l = (List)list;
l.remove(o);
if (l.size()==0)
return null;
return list;
}
if (list.equals(o))
return null;
return list;
}
/* ------------------------------------------------------------ */
public static Object remove(Object list, int i)
{
if (list==null)
return null;
if (list instanceof List)
{
List l = (List)list;
l.remove(i);
if (l.size()==0)
return null;
return list;
}
if (i==0)
return null;
return list;
}
/* ------------------------------------------------------------ */
/** Get the real List from a LazyList.
*
* @param list A LazyList returned from LazyList.add(Object)
* @return The List of added items, which may be an EMPTY_LIST
* or a SingletonList.
*/
public static List getList(Object list)
{
return getList(list,false);
}
/* ------------------------------------------------------------ */
/** Get the real List from a LazyList.
*
* @param list A LazyList returned from LazyList.add(Object) or null
* @param nullForEmpty If true, null is returned instead of an
* empty list.
* @return The List of added items, which may be null, an EMPTY_LIST
* or a SingletonList.
*/
public static List getList(Object list, boolean nullForEmpty)
{
if (list==null)
return nullForEmpty?null:Collections.EMPTY_LIST;
if (list instanceof List)
return (List)list;
List l = new ArrayList(1);
l.add(list);
return l;
}
/* ------------------------------------------------------------ */
public static String[] toStringArray(Object list)
{
if (list==null)
return __EMTPY_STRING_ARRAY;
if (list instanceof List)
{
List l = (List)list;
String[] a = new String[l.size()];
for (int i=l.size();i-->0;)
{
Object o=l.get(i);
if (o!=null)
a[i]=o.toString();
}
return a;
}
return new String[] {list.toString()};
}
/* ------------------------------------------------------------ */
public static Object toArray(Object list,Class aClass)
{
if (list==null)
return (Object[])Array.newInstance(aClass,0);
if (list instanceof List)
{
List l = (List)list;
if (aClass.isPrimitive())
{
Object a = Array.newInstance(aClass,l.size());
for (int i=0;i<l.size();i++)
Array.set(a,i,l.get(i));
return a;
}
return l.toArray((Object[])Array.newInstance(aClass,l.size()));
}
Object a = Array.newInstance(aClass,1);
Array.set(a,0,list);
return a;
}
/* ------------------------------------------------------------ */
/** The size of a lazy List
* @param list A LazyList returned from LazyList.add(Object) or null
* @return the size of the list.
*/
public static int size(Object list)
{
if (list==null)
return 0;
if (list instanceof List)
return ((List)list).size();
return 1;
}
/* ------------------------------------------------------------ */
/** Get item from the list
* @param list A LazyList returned from LazyList.add(Object) or null
* @param i int index
* @return the item from the list.
*/
public static Object get(Object list, int i)
{
if (list==null)
throw new IndexOutOfBoundsException();
if (list instanceof List)
return ((List)list).get(i);
if (i==0)
return list;
throw new IndexOutOfBoundsException();
}
/* ------------------------------------------------------------ */
public static boolean contains(Object list,Object item)
{
if (list==null)
return false;
if (list instanceof List)
return ((List)list).contains(item);
return list.equals(item);
}
/* ------------------------------------------------------------ */
public static Object clone(Object list)
{
if (list==null)
return null;
if (list instanceof List)
return new ArrayList((List)list);
return list;
}
/* ------------------------------------------------------------ */
public static String toString(Object list)
{
if (list==null)
return "[]";
if (list instanceof List)
return ((List)list).toString();
return "["+list+"]";
}
/* ------------------------------------------------------------ */
public static Iterator iterator(Object list)
{
if (list==null)
return Collections.EMPTY_LIST.iterator();
if (list instanceof List)
return ((List)list).iterator();
return getList(list).iterator();
}
/* ------------------------------------------------------------ */
public static ListIterator listIterator(Object list)
{
if (list==null)
return Collections.EMPTY_LIST.listIterator();
if (list instanceof List)
return ((List)list).listIterator();
return getList(list).listIterator();
}
/* ------------------------------------------------------------ */
/**
* @param array Any array of object
* @return A new <i>modifiable</i> list initialised with the elements from <code>array</code>.
*/
public static List array2List(Object[] array)
{
if (array==null || array.length==0)
return new ArrayList();
return new ArrayList(Arrays.asList(array));
}
/* ------------------------------------------------------------ */
/** Add element to an array
* @param array The array to add to (or null)
* @param item The item to add
* @param type The type of the array (in case of null array)
* @return new array with contents of array plus item
*/
public static Object[] addToArray(Object[] array, Object item, Class type)
{
if (array==null)
{
if (type==null && item!=null)
type= item.getClass();
Object[] na = (Object[])Array.newInstance(type, 1);
na[0]=item;
return na;
}
else
{
Class c = array.getClass().getComponentType();
Object[] na = (Object[])Array.newInstance(c, Array.getLength(array)+1);
System.arraycopy(array, 0, na, 0, array.length);
na[array.length]=item;
return na;
}
}
/* ------------------------------------------------------------ */
public static Object[] removeFromArray(Object[] array, Object item)
{
if (item==null || array==null)
return array;
for (int i=array.length;i-->0;)
{
if (item.equals(array[i]))
{
Class c = array==null?item.getClass():array.getClass().getComponentType();
Object[] na = (Object[])Array.newInstance(c, Array.getLength(array)-1);
if (i>0)
System.arraycopy(array, 0, na, 0, i);
if (i+1<array.length)
System.arraycopy(array, i+1, na, i, array.length-(i+1));
return na;
}
}
return array;
}
}
A simple Doubly Linked list class, designed to avoid O(n) behaviour on insert and delete.
/*
Licensed to the Apache Software Foundation (ASF) under one or more
contributor license agreements. See the NOTICE file distributed with
this work for additional information regarding copyright ownership.
The ASF licenses this file to You under the Apache License, Version 2.0
(the "License"); you may not use this file except in compliance with
the License. You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
*/
/**
* A simple Doubly Linked list class, designed to avoid
* O(n) behaviour on insert and delete.
*
* @author
* @version $Id: DoublyLinkedList.java 475685 2006-11-16 11:16:05Z cam $
*/
public class DoublyLinkedList {
/**
* Basic doubly linked list node interface.
*/
public static class Node {
private Node next = null;
private Node prev = null;
public final Node getNext() { return next; }
public final Node getPrev() { return prev; }
protected final void setNext(Node newNext) { next = newNext; }
protected final void setPrev(Node newPrev) { prev = newPrev; }
/**
* Unlink this node from it"s current list...
*/
protected final void unlink() {
if (getNext() != null)
getNext().setPrev(getPrev());
if (getPrev() != null)
getPrev().setNext(getNext());
setNext(null);
setPrev(null);
}
/**
* Link this node in, infront of nde (unlinks it"s self
* before hand if needed).
* @param nde the node to link in before.
*/
protected final void insertBefore(Node nde) {
// Already here...
if (this == nde) return;
if (getPrev() != null)
unlink();
// Actually insert this node...
if (nde == null) {
// empty lst...
setNext(this);
setPrev(this);
} else {
setNext(nde);
setPrev(nde.getPrev());
nde.setPrev(this);
if (getPrev() != null)
getPrev().setNext(this);
}
}
}
private Node head = null;
private int size = 0;
public DoublyLinkedList() {}
/**
* Returns the number of elements currently in the list.
*/
public synchronized int getSize() { return size; }
/**
* Removes all elements from the list.
*/
public synchronized void empty() {
while(size > 0) pop();
}
/**
* Get the current head element
* @return The current "first" element in list.
*/
public Node getHead() { return head; }
/**
* Get the current tail element
* @return The current "last" element in list.
*/
public Node getTail() { return head.getPrev(); }
/**
* Moves <tt>nde</tt> to the head of the list (equivilent to
* remove(nde); add(nde); but faster.
*/
public void touch(Node nde) {
if (nde == null) return;
nde.insertBefore(head);
head = nde;
}
public void add(int index, Node nde) {
if (nde == null) return;
if (index == 0) {
// This makes it the first element in the list.
nde.insertBefore(head);
head = nde;
} else if (index == size) {
// Because the list is circular this
// makes it the last element in the list.
nde.insertBefore(head);
} else {
Node after = head;
while (index != 0) {
after = after.getNext();
index--;
}
nde.insertBefore(after);
}
size++;
}
/**
* Adds <tt>nde</tt> to the head of the list.
* In perl this is called an "unpop". <tt>nde</tt> should
* not currently be part of any list.
* @param nde the node to add to the list.
*/
public void add(Node nde) {
if (nde == null) return;
nde.insertBefore(head);
head = nde;
size++;
}
/**
* Removes nde from the list it is part of (should be this
* one, otherwise results are undefined). If nde is the
* current head element, then the next element becomes head,
* if there are no more elements the list becomes empty.
* @param nde node to remove.
*/
public void remove(Node nde) {
if (nde == null) return;
if (nde == head) {
if (head.getNext() == head)
head = null; // Last node...
else
head = head.getNext();
}
nde.unlink();
size--;
}
/**
* Removes "head" from list and returns it. Returns null if list is empty.
* @return current head element, next element becomes head.
*/
public Node pop() {
if (head == null) return null;
Node nde = head;
remove(nde);
return nde;
}
/**
* Removes "tail" from list and returns it. Returns null if list is empty.
* @return current tail element.
*/
public Node unpush() {
if (head == null) return null;
Node nde = getTail();
remove(nde);
return nde;
}
/**
* Adds <tt>nde</tt> to tail of list
*/
public void push(Node nde) {
nde.insertBefore(head);
if (head == null) head = nde;
size++;
}
/**
* Adds <tt>nde</tt> to head of list
*/
public void unpop(Node nde) {
nde.insertBefore(head);
head = nde;
size++;
}
}
Check if a particular element exists in LinkedList Java example
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");
}
}
}
Checking what item is first in line without removing it: element
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
Queue<String> queue = new LinkedList<String>();
queue.add("A");
queue.add("B");
queue.offer("C");
queue.offer("D");
System.out.println("remove: " + queue.remove());
System.out.println("element: " + queue.element());
System.out.println("poll: " + queue.poll());
System.out.println("peek: " + queue.peek());
}
}
/*
remove: A
element: B
poll: B
peek: C
*/
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 a list with an ordered list of strings
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
public class Main {
public static void main(String[] argv) {
List<String> sortedList = new LinkedList<String>();
sortedList.addAll(Arrays.asList(new String[] { "a", "b", "c", "d" }));
int index = Collections.binarySearch(sortedList, "c");
System.out.println(index);
index = Collections.binarySearch(sortedList, "e");
System.out.println(index);
}
}
Create an object array from elements of LinkedList Java example
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);
}
}
}
Double LinkedList
/*
* The contents of this file are subject to the terms
* of the Common Development and Distribution License
* (the "License"). You may not use this file except
* in compliance with the License.
*
* You can obtain a copy of the license at
* glassfish/bootstrap/legal/CDDLv1.0.txt or
* https://glassfish.dev.java.net/public/CDDLv1.0.html.
* See the License for the specific language governing
* permissions and limitations under the License.
*
* When distributing Covered Code, include this CDDL
* HEADER in each file and include the License file at
* glassfish/bootstrap/legal/CDDLv1.0.txt. If applicable,
* add the following below this CDDL HEADER, with the
* fields enclosed by brackets "[]" replaced with your
* own identifying information: Portions Copyright [yyyy]
* [name of copyright owner]
*/
/*
* ConnectionImpl.java
*
* Create on March 3, 2000
*/
/**
* This class defines a thread-safe double linked-list. The list is usable by
* any class that implements the com.forte.util.Linkable interface. This class
* allows a linkable object it be inserted or removed from anywhere in the
* list.
*
* RESTRICTION: An object can only be a member of 1 list at a time.
*/
public class DoubleLinkedList {
// Instance variables.
/**
* Head of linked list.
*/
public Linkable head;
/**
* Tail of linked list.
*/
public Linkable tail;
/**
* Size of linked list.
*/
public int size;
/**
* Default constructor.
*/
public DoubleLinkedList() {
this.head = null;
this.size = 0;
this.tail = null;
}
// Public Methods.
/**
* Return the object at the head of a linked list.
*/
public synchronized Linkable getHead() {
return this.head;
}
/**
* Return the object at the tail of a linked list.
*/
public synchronized Linkable getTail() {
return this.tail;
}
/**
* Return size of the linked list.
*/
public synchronized int getSize() {
return this.size;
}
/**
* Insert an object at the head of a linked list.
*/
public synchronized void insertAtHead(Linkable node) {
if (node instanceof Linkable) {
if (this.head == null) {
node.setNext(null); // Fixup node nextlink.
node.setPrevious(null); // Fixup node backlink.
this.head = node; // Insert node at head of list.
} else {
Linkable oldHead = this.head; // Fixup current head node.
oldHead.setPrevious(node); // Set backlink to new node.
node.setNext(oldHead); // Fixup new node nextlink.
node.setPrevious(null); // Fixup new node backlink.
this.head = node; // Insert node at head of list.
}
if (this.tail == null) // If list was empty,
{
this.tail = node; // Insert node at tail of list.
}
this.size++;
}
}
/**
* Insert an object at the tail of a linked list.
*/
public synchronized void insertAtTail(Linkable node) {
if (node instanceof Linkable) {
if (this.tail == null) {
node.setNext(null); // Fixup node nextlink.
node.setPrevious(null); // Fixup node backlink.
this.tail = node; // Insert node at end of list.
} else {
Linkable oldTail = this.tail; // Fixup current tail node.
oldTail.setNext(node); // Set backlink to new node.
node.setNext(null); // Fixup new node backlink.
node.setPrevious(oldTail); // Fixup new node nextlink.
this.tail = node; // Insert node at end of list.
}
if (this.head == null) // If list was empty,
{
this.head = node; // Insert node at head of list.
}
this.size++;
}
}
/**
* Remove and return an object from the head of a linked list.
*/
public synchronized Linkable removeFromHead() {
Linkable node = this.head;
if (node instanceof Linkable) {
this.head = node.getNext(); // Set head to next node.
if (this.head == null) // If we emptied the list,
{
this.tail = null; // Fixup the tail pointer.
} else {
this.head.setPrevious(null);// Clear head node backlink.
}
node.setNext(null); // Clear removed node nextlink.
node.setPrevious(null); // Clear romoved node backlink.
this.size--;
}
return node;
}
/**
* Remove and return an object from the tail of a linked list.
*/
public synchronized Linkable removeFromTail() {
Linkable node = this.tail;
if (node instanceof Linkable) {
this.tail = node.getPrevious(); // Set tail to previous node.
if (this.tail == null) // If we emptied the list,
{
this.head = null; // Fixup the head pointer.
} else {
this.tail.setNext(null); // Clear tail node nextlink.
}
node.setNext(null); // Clear removed node nextlink.
node.setPrevious(null); // Clear removed node backlink.
this.size--;
}
return node;
}
/**
* Remove the specified object from anywhere in the linked list. This method
* is usually used by the object to remove itself from the list.
*/
public synchronized void removeFromList(Linkable node) {
if ((this.size <= 0) || ((this.head == null) && (this.tail == null))) {
return;
}
if (node instanceof Linkable) {
Linkable p = node.getPrevious(); // Reference to previous node.
Linkable n = node.getNext(); // Reference to next node.
if (p == null) // Is this the first (or only) node in the list?
{
this.head = n; // Yes, set the head of the list to point to the next.
} else {
p.setNext(n); // No, set the previous node to point to the next.
}
if (n == null) // Is this the last (or only) node in the list?
{
this.tail = p; // Yes, set the tail to point to the previous.
} else {
n.setPrevious(p); // No, set the next node to point to the previous.
}
node.setNext(null);
node.setPrevious(null);
this.size--;
}
}
/**
* Insert an object anywhere into the linked list.
* @param afternode the new node will be inserted after this node
* @param newnode the new node to be inserted
*/
public synchronized void insertIntoList(Linkable afternode,
Linkable newnode) {
if ((newnode instanceof Linkable) && (afternode instanceof Linkable)) {
if (this.tail == afternode) // If inserting at the tail,
{
this.insertAtTail(newnode); // Use insertAtTail method.
} else {
Linkable nextnode = afternode.getNext();
newnode.setNext(nextnode); // Point to next node.
newnode.setPrevious(afternode); // Point to previous node.
afternode.setNext(newnode); // Fixup backlink in afternode.
nextnode.setPrevious(newnode); // Fixup nextlink in next node.
}
this.size++;
}
}
/**
* Return a string representation of this DoubleLinkedList object. <p>
* @return String representation of this object.
*/
public synchronized String toString() {
/* boolean dif = ThreadContext.lgr().test
( // Check for trace flag sp:1:1
TraceLogger.CONFIGURATION,
TraceLogger.SVC_SP,
SPLogFlags.CFG_DIFFABLE_EXCEPTS,
1
);
String buf = "DoubleLinkedList@\n";
if(!dif)
{
buf = buf + " head = " + this.head + "\n";
buf = buf + " tail = " + this.tail + "\n";
}
buf = buf + " size = " + this.size + "\n";
return buf;
*/
return null;
}
}
/*
* The contents of this file are subject to the terms
* of the Common Development and Distribution License
* (the "License"). You may not use this file except
* in compliance with the License.
*
* You can obtain a copy of the license at
* glassfish/bootstrap/legal/CDDLv1.0.txt or
* https://glassfish.dev.java.net/public/CDDLv1.0.html.
* See the License for the specific language governing
* permissions and limitations under the License.
*
* When distributing Covered Code, include this CDDL
* HEADER in each file and include the License file at
* glassfish/bootstrap/legal/CDDLv1.0.txt. If applicable,
* add the following below this CDDL HEADER, with the
* fields enclosed by brackets "[]" replaced with your
* own identifying information: Portions Copyright [yyyy]
* [name of copyright owner]
*/
/*
* ConnectionImpl.java
*
* Create on March 3, 2000
*/
/**
* This file defines a linkable interface. Any object that needs to be a member
* of com.forte.util.DoubleLinkedList should implement this interface.
*/
interface Linkable {
public Linkable getNext();
public Linkable getPrevious();
public void setNext(Linkable node);
public void setPrevious(Linkable node);
}
Doubly Linked list
/*****************************************************************************
* Copyright (C) The Apache Software Foundation. All rights reserved. *
* ------------------------------------------------------------------------- *
* This software is published under the terms of the Apache Software License *
* version 1.1, a copy of which has been included with this distribution in *
* the LICENSE file. *
*****************************************************************************/
/**
* A simple Doubly Linked list class, designed to avoid
* O(n) behaviour on insert and delete.
*/
public class DoublyLinkedList {
/**
* Basic doubly linked list node interface.
*/
public static class Node {
private Node next = null;
private Node prev = null;
public final Node getNext() { return next; }
public final Node getPrev() { return prev; }
protected final void setNext(Node newNext) { next = newNext; }
protected final void setPrev(Node newPrev) { prev = newPrev; }
/**
* Unlink this node from it"s current list...
*/
protected final void unlink() {
if (getNext() != null)
getNext().setPrev(getPrev());
if (getPrev() != null)
getPrev().setNext(getNext());
setNext(null);
setPrev(null);
}
/**
* Link this node in, infront of nde (unlinks it"s self
* before hand if needed).
* @param nde the node to link in before.
*/
protected final void insertBefore(Node nde) {
// Already here...
if (this == nde) return;
if (getPrev() != null)
unlink();
// Actually insert this node...
if (nde == null) {
// empty lst...
setNext(this);
setPrev(this);
} else {
setNext(nde);
setPrev(nde.getPrev());
nde.setPrev(this);
if (getPrev() != null)
getPrev().setNext(this);
}
}
}
private Node head = null;
private int size = 0;
public DoublyLinkedList() {}
/**
* Returns the number of elements currently in the list.
*/
public synchronized int getSize() { return size; }
/**
* Removes all elements from the list.
*/
public synchronized void empty() {
while(size > 0) pop();
}
/**
* Get the current head element
* @return The current "first" element in list.
*/
public Node getHead() { return head; }
/**
* Get the current tail element
* @return The current "last" element in list.
*/
public Node getTail() { return head.getPrev(); }
/**
* Moves <tt>nde</tt> to the head of the list (equivilent to
* remove(nde); add(nde); but faster.
*/
public void touch(Node nde) {
if (nde == null) return;
nde.insertBefore(head);
head = nde;
}
/**
* Adds <tt>nde</tt> to the head of the list.
* In perl this is called an "unpop". <tt>nde</tt> should
* not currently be part of any list.
* @param nde the node to add to the list.
*/
public void add(Node nde) {
if (nde == null) return;
nde.insertBefore(head);
head = nde;
size++;
}
/**
* Removes nde from the list it is part of (should be this
* one, otherwise results are undefined). If nde is the
* current head element, then the next element becomes head,
* if there are no more elements the list becomes empty.
* @param nde node to remove.
*/
public void remove(Node nde) {
if (nde == null) return;
if (nde == head) {
if (head.getNext() == head)
head = null; // Last node...
else
head = head.getNext();
}
nde.unlink();
size--;
}
/**
* Removes "head" from list and returns it. Returns null if list is empty.
* @returns current head element, next element becomes head.
*/
public Node pop() {
if (head == null) return null;
Node nde = head;
remove(nde);
return nde;
}
/**
* Removes "tail" from list and returns it. Returns null if list is empty.
* @returns current tail element.
*/
public Node unpush() {
if (head == null) return null;
Node nde = getTail();
remove(nde);
return nde;
}
/**
* Adds <tt>nde</tt> to tail of list
*/
public void push(Node nde) {
nde.insertBefore(head);
if (head == null) head = nde;
size++;
}
/**
* Adds <tt>nde</tt> to head of list
*/
public void unpop(Node nde) {
nde.insertBefore(head);
head = nde;
size++;
}
}
Finding an Element in a Sorted List
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
public class Main {
public static void main(String[] argv) {
List<String> sortedList = new LinkedList<String>();
sortedList.addAll(Arrays.asList(new String[] { "a", "b", "c", "d" }));
int index = Collections.binarySearch(sortedList, "c");
System.out.println(index);
index = Collections.binarySearch(sortedList, "e");
System.out.println(index);
}
}
/*
2
-5
*/
Get elements from LinkedList Java example
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 Java example
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 Java example
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);
}
}
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);
}
}
Iterate through elements of Java LinkedList using Iterator example
import java.util.Iterator;
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");
Iterator itr = lList.iterator();
while (itr.hasNext()) {
System.out.println(itr.next());
}
}
}
Iterate through elements of Java LinkedList using ListIterator example
import java.util.ListIterator;
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");
ListIterator itr = lList.listIterator();
System.out.println("forward direction");
while (itr.hasNext()){
System.out.println(itr.next());
}
System.out.println("reverse direction");
while (itr.hasPrevious()){
System.out.println(itr.previous());
}
}
}
Making a stack from a LinkedList
// : c11:StackL.java
// Making a stack from a LinkedList.
// From "Thinking in Java, 3rd ed." (c) Bruce Eckel 2002
// www.BruceEckel.ru. See copyright notice in CopyRight.txt.
import java.util.LinkedList;
public 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();
}
public static void main(String[] args) {
StackL stack = new StackL();
for (int i = 0; i < 10; i++)
stack.push(new Integer(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());
}
} ///:~
Remove all elements or clear LinkedList Java example
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 Java example
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 Java example
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 Java example
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 the first item from the queue: poll
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
Queue<String> queue = new LinkedList<String>();
queue.add("A");
queue.add("B");
queue.offer("C");
queue.offer("D");
System.out.println("remove: " + queue.remove());
System.out.println("element: " + queue.element());
System.out.println("poll: " + queue.poll());
System.out.println("peek: " + queue.peek());
}
}
/*
remove: A
element: B
poll: B
peek: C
*/
Replace an Element of LinkedList Java example
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);
}
}
Search elements of LinkedList Java example
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"));
}
}
Search for a non-existent element
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
public class Main {
public static void main(String[] argv) {
List<String> sortedList = new LinkedList<String>();
sortedList.addAll(Arrays.asList(new String[] { "a", "b", "c", "d" }));
int index = Collections.binarySearch(sortedList, "c");
System.out.println(index);
index = Collections.binarySearch(sortedList, "e");
System.out.println(index);
}
}
/*
2
-5
*/
Single linked list
/**
* Copyright (c) 2005 Elie Levy <elie.levy@zilonis.org>
* All rights reserved
*
* This License governs use of the accompanying Software, and your use of the
* Software constitutes acceptance of this license.
*
* You may use this Software for any non-commercial purpose, subject to the
* restrictions in this license. Some purposes which can be non-commercial are
* teaching, academic research, and personal experimentation. You may also
* distribute this Software with books or other teaching materials, or publish
* the Software on websites, that are intended to teach the use of the
* Software.
*
*
* You may not use or distribute this Software or any derivative works in any
* form for commercial purposes. Examples of commercial purposes would be
* running business operations, licensing, leasing, or selling the Software, or
* distributing the Software for use with commercial products.
*
* You may modify this Software and distribute the modified Software for
* non-commercial purposes, however, you may not grant rights to the Software
* or derivative works that are broader than those provided by this License.
* For example, you may not distribute modifications of the Software under
* terms that would permit commercial use, or under terms that purport to
* require the Software or derivative works to be sublicensed to others.
*
* You may use any information in intangible form that you remember after
* accessing the Software. However, this right does not grant you a license to
* any of the copyrights or patents for anything you might create using such
* information.
*
* In return, we simply require that you agree:
*
* Not to remove any copyright or other notices from the Software.
*
*
* That if you distribute the Software in source or object form, you will
* include a verbatim copy of this license.
*
*
* That if you distribute derivative works of the Software in source code form
* you do so only under a license that includes all of the provisions of this
* License, and if you distribute derivative works of the Software solely in
* object form you do so only under a license that complies with this License.
*
*
* That if you have modified the Software or created derivative works, and
* distribute such modifications or derivative works, you will cause the
* modified files to carry prominent notices so that recipients know that they
* are not receiving the original Software. Such notices must state: (i) that
* you have changed the Software; and (ii) the date of any changes.
*
*
* THAT THE SOFTWARE COMES "AS IS", WITH NO WARRANTIES. THIS MEANS NO EXPRESS,
* IMPLIED OR STATUTORY WARRANTY, INCLUDING WITHOUT LIMITATION, WARRANTIES OF
* MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE OR ANY WARRANTY OF TITLE
* OR NON-INFRINGEMENT. ALSO, YOU MUST PASS THIS DISCLAIMER ON WHENEVER YOU
* DISTRIBUTE THE SOFTWARE OR DERIVATIVE WORKS.
*
*
* THAT NEITHER ZILONIS NOR THE AUTHOR WILL BE LIABLE FOR ANY DAMAGES RELATED
* TO THE SOFTWARE OR THIS LICENSE, INCLUDING DIRECT, INDIRECT, SPECIAL,
* CONSEQUENTIAL OR INCIDENTAL DAMAGES, TO THE MAXIMUM EXTENT THE LAW PERMITS,
* NO MATTER WHAT LEGAL THEORY IT IS BASED ON. ALSO, YOU MUST PASS THIS
* LIMITATION OF LIABILITY ON WHENEVER YOU DISTRIBUTE THE SOFTWARE OR
* DERIVATIVE WORKS.
*
*
* That if you sue anyone over patents that you think may apply to the Software
* or anyone"s use of the Software, your license to the Software ends
* automatically.
*
*
* That your rights under the License end automatically if you breach it in any
* way.
*
*
* Elie Levy reserves all rights not expressly granted to you in this
* license.
*
*/
import java.util.Iterator;
/**
* A very lite single linked list
*/
public class LiteList<Element> implements Iterable<Element> {
private Node first;
public void add(Element element) {
first = new Node(element,first);
}
public Iterator<Element> iterator() {
return new LiteIterator();
}
private class LiteIterator implements Iterator<Element> {
Node current;
public LiteIterator() {
current = first;
}
public boolean hasNext() {
return (current!=null);
}
public Element next() {
Element result = current.getElement();
current = current.getNext();
return result;
}
public void remove() {
}
}
private class Node {
private Element element;
private Node next;
public Node(Element element, Node next) {
this.element = element;
this.next = next;
}
public Element getElement() {
return element;
}
public Node getNext() {
return next;
}
}
}
To insert an object into a specific position into the list, specify the index in the add method
import java.util.LinkedList;
public class MainClass {
public static void main(String[] a) {
LinkedList<String> officers = new LinkedList<String>();
officers.add("B");
officers.add("B");
officers.add("H");
officers.add("P");
officers.add("M");
officers.add(2, "T");
for (String s : officers)
System.out.println(s);
}
}
Updating LinkedList Items
import java.util.LinkedList;
public class MainClass {
public static void main(String[] a) {
LinkedList<String> officers = new LinkedList<String>();
officers.add("B");
officers.add("B");
officers.add("T");
officers.add("H");
officers.add("P");
officers.add("McIntyre");
System.out.println(officers);
officers.set(2, "Murdock");
System.out.println("\nTuttle is replaced:");
System.out.println(officers);
}
}
Use addFirst method to add value to the first position in a linked list
import java.util.LinkedList;
public class MainClass {
public static void main(String[] a) {
LinkedList<String> officers = new LinkedList<String>();
officers.addFirst("B");
officers.addFirst("B");
officers.addFirst("H");
officers.addFirst("P");
officers.addFirst("M");
for (String s : officers)
System.out.println(s);
}
}
Use an Iterator to cycle through a collection in the forward direction.
// Use a ListIterator to cycle through a collection in the reverse direction.
import java.util.Iterator;
import java.util.LinkedList;
import java.util.ListIterator;
class Employee {
String name;
String number;
Employee(String n, String num) {
name = n;
number = num;
}
}
public class Main {
public static void main(String args[]) {
LinkedList<Employee> phonelist = new LinkedList<Employee>();
phonelist.add(new Employee("A", "1"));
phonelist.add(new Employee("B", "2"));
phonelist.add(new Employee("C", "3"));
Iterator<Employee> itr = phonelist.iterator();
Employee pe;
while (itr.hasNext()) {
pe = itr.next();
System.out.println(pe.name + ": " + pe.number);
}
ListIterator<Employee> litr = phonelist.listIterator(phonelist.size());
while (litr.hasPrevious()) {
pe = litr.previous();
System.out.println(pe.name + ": " + pe.number);
}
}
}
Use for each loop to go through elements in a linkedlist
import java.util.LinkedList;
public class MainClass {
public static void main(String[] a) {
LinkedList<String> officers = new LinkedList<String>();
officers.add("B");
officers.add("B");
officers.add("H");
officers.add("P");
officers.add("M");
for (String s : officers)
System.out.println(s);
}
}
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);
}
}
