Java/Collections Data Structure/Custom List

A growable array of int values, suitable for use with multiple threads

/*
 * Copyright (c) 2004 David Flanagan.  All rights reserved.
 * This code is from the book Java Examples in a Nutshell, 3nd Edition.
 * It is provided AS-IS, WITHOUT ANY WARRANTY either expressed or implied.
 * You may study, use, and modify it for any non-commercial purpose,
 * including teaching and use in open-source projects.
 * You may distribute it non-commercially as long as you retain this notice.
 * For a commercial use license, or to purchase the book, 
 * please visit http://www.davidflanagan.ru/javaexamples3.
 */
/**
 * A growable array of int values, suitable for use with multiple threads.
 */
public class ThreadSafeIntList {
  protected int[] data; // This array holds the integers
  protected int size; // This is how many it current holds
  // Static final values are constants. This one is private.
  private static final int DEFAULT_CAPACITY = 8;
  // Create a ThreadSafeIntList with a default capacity
  public ThreadSafeIntList() {
    // We don"t have to set size to zero because newly created objects
    // automatically have their fields set to zero, false, and null.
    data = new int[DEFAULT_CAPACITY]; // Allocate the array
  }
  // This constructor returns a copy of an existing ThreadSafeIntList.
  // Note that it synchronizes its access to the original list.
  public ThreadSafeIntList(ThreadSafeIntList original) {
    synchronized (original) {
      this.data = (int[]) original.data.clone();
      this.size = original.size;
    }
  }
  // Return the number of ints stored in the list
  public synchronized int size() {
    return size;
  }
  // Return the int stored at the specified index
  public synchronized int get(int index) {
    if (index < 0 || index >= size) // Check that argument is legitimate
      throw new IndexOutOfBoundsException(String.valueOf(index));
    return data[index];
  }
  // Append a new value to the list, reallocating if necessary
  public synchronized void add(int value) {
    if (size == data.length)
      setCapacity(size * 2); // realloc if necessary
    data[size++] = value; // add value to list
  }
  // Remove all elements from the list
  public synchronized void clear() {
    size = 0;
  }
  // Copy the contents of the list into a new array and return that array
  public synchronized int[] toArray() {
    int[] copy = new int[size];
    System.arraycopy(data, 0, copy, 0, size);
    return copy;
  }
  // Reallocate the data array to enlarge or shrink it.
  // Not synchronized because it is always called from synchronized methods.
  protected void setCapacity(int n) {
    if (n == data.length)
      return; // Check size
    int[] newdata = new int[n]; // Allocate the new array
    System.arraycopy(data, 0, newdata, 0, size); // Copy data into it
    data = newdata; // Replace old array
  }
}

Another Link list

class Link {
  public int key;
  public double data; 
  public Link next;
  public Link(int id, double dd) {
    key = id;
    data = dd;
  }
  public void displayLink() {
    System.out.print("{" + key + ", " + data + "} ");
  }
}
public class AnotherLinkList {
  private Link first;
  public AnotherLinkList() {
    first = null;
  }
  public void insertFirst(int id, double dd) {
    Link newLink = new Link(id, dd);
    newLink.next = first;
    first = newLink; 
  }
  public Link find(int key) 
  {
    Link current = first; 
    while (current.key != key)
    {
      if (current.next == null)
        return null; // didn"t find it
      else
        // not end of list,
        current = current.next; // go to next link
    }
    return current; // found it
  }
  //   delete link with given key
  public Link delete(int key) {
    Link current = first;
    Link previous = first;
    while (current.key != key) {
      if (current.next == null)
        return null; // didn"t find it
      else {
        previous = current; // go to next link
        current = current.next;
      }
    } // found it
    if (current == first) // if first link,
      first = first.next; //    change first
    else
      // otherwise,
      previous.next = current.next; //    bypass it
    return current;
  }
  public void displayList() {
    System.out.print("List (first to last): ");
    Link current = first; 
    while (current != null) 
    {
      current.displayLink(); 
      current = current.next;
    }
    System.out.println("");
  }
  public static void main(String[] args) {
    AnotherLinkList theList = new AnotherLinkList();
    theList.insertFirst(12, 2.59);
    theList.insertFirst(24, 4.69);
    theList.insertFirst(36, 6.79);
    theList.insertFirst(48, 8.89);
    theList.displayList();
    Link f = theList.find(44);
    if (f != null)
      System.out.println("Found link with key " + f.key);
    else
      System.out.println("Can"t find link");
    Link d = theList.delete(66); 
    if (d != null)
      System.out.println("Deleted link with key " + d.key);
    else
      System.out.println("Can"t delete link");
    theList.displayList();
  }
}

Doubly-linked list with data structure

public class DoublyLinkedList {
  private Link first; 
  private Link last; 
  public DoublyLinkedList() {
    first = null; 
    last = null;
  }
  public boolean isEmpty(){
    return first == null;
  }
  public void insertFirst(long dd){
    Link newLink = new Link(dd); 
    if (isEmpty()) 
      last = newLink; 
    else
      first.previous = newLink; 
    newLink.next = first; 
    first = newLink; 
  }
  public void insertLast(long dd){
    Link newLink = new Link(dd); 
    if (isEmpty()) 
      first = newLink; 
    else {
      last.next = newLink; 
      newLink.previous = last; 
    }
    last = newLink; 
  }
  public Link deleteFirst(){ 
    Link temp = first;
    if (first.next == null) 
      last = null; 
    else
      first.next.previous = null;
    first = first.next; 
    return temp;
  }
  public Link deleteLast(){ 
    Link temp = last;
    if (first.next == null)
      first = null; 
    else
      last.previous.next = null;
    last = last.previous; 
    return temp;
  }
  public boolean insertAfter(long key, long dd) { 
    Link current = first; 
    while (current.dData != key){
      current = current.next;
      if (current == null)
        return false; // cannot find it
    }
    Link newLink = new Link(dd); // make new link
    if (current == last) // if last link,
    {
      newLink.next = null; 
      last = newLink; 
    } else // not last link,
    {
      newLink.next = current.next; 
      
      current.next.previous = newLink;
    }
    newLink.previous = current; 
    current.next = newLink; 
    return true; // found it, insert
  }
  public Link deleteKey(long key){
    Link current = first; 
    while (current.dData != key)
    {
      current = current.next;
      if (current == null)
        return null; // cannot find it
    }
    if (current == first) // found it; first item?
      first = current.next; 
    else
      current.previous.next = current.next;
    if (current == last) // last item?
      last = current.previous; 
    else
      // not last
      current.next.previous = current.previous;
    return current; // return value
  }
  public void displayForward() {
    System.out.print("List (first to last): ");
    Link current = first; // start at beginning
    while (current != null) // until end of list,
    {
      current.displayLink();
      current = current.next; // move to next link
    }
    System.out.println("");
  }
  public void displayBackward() {
    System.out.print("List : ");
    Link current = last;
    while (current != null){
      current.displayLink();
      current = current.previous;
    }
    System.out.println("");
  }
  public static void main(String[] args) {
    DoublyLinkedList theList = new DoublyLinkedList();
    theList.insertFirst(22);
    theList.insertFirst(44);
    theList.insertLast(33);
    theList.insertLast(55);
    theList.displayForward();
    theList.displayBackward();
    theList.deleteFirst();
    theList.deleteLast();
    theList.deleteKey(11);
    theList.displayForward();
    theList.insertAfter(22, 77); // insert 77 after 22
    theList.insertAfter(33, 88); // insert 88 after 33
    theList.displayForward();
  }
}
class Link {
  public long dData; // data item
  public Link next; // next link in list
  public Link previous; // previous link in list
  public Link(long d)
  {
    dData = d;
  }
  public void displayLink(){
    System.out.print(dData + " ");
  }
}

Frist last list

class Link {
  public long dData; 
  public Link next; 
  public Link(long d){
    dData = d;
  }
  public void displayLink(){
    System.out.print(dData + " ");
  }
}
public class FirstLastList1 {
  private Link first; 
  private Link last; 
  public FirstLastList1() {
    first = null;
    last = null;
  }
  public boolean isEmpty() {
    return first == null;
  }
  public void insertLast(long dd){
    Link newLink = new Link(dd); 
    if (isEmpty()) 
      first = newLink; 
    else
      last.next = newLink;
    last = newLink; 
  }
  public long deleteFirst(){
    long temp = first.dData;
    if (first.next == null) 
      last = null;
    first = first.next; 
    return temp;
  }
  public void displayList() {
    Link current = first;
    while (current != null){
      current.displayLink();
      current = current.next;
    }
    System.out.println("");
  }
}
class LinkQueue {
  private FirstLastList1 theList;
  public LinkQueue() {
    theList = new FirstLastList1();
  }
  public boolean isEmpty(){
    return theList.isEmpty();
  }
  public void insert(long j){
    theList.insertLast(j);
  }
  public long remove()
  {
    return theList.deleteFirst();
  }
  public void displayQueue() {
    System.out.print("Queue: ");
    theList.displayList();
  }
  public static void main(String[] args) {
    LinkQueue theQueue = new LinkQueue();
    theQueue.insert(20);
    theQueue.insert(40);
    theQueue.displayQueue();
    theQueue.insert(60);
    theQueue.insert(80);
    theQueue.displayQueue();
    theQueue.remove();
    theQueue.remove();
    theQueue.displayQueue();
  }
}

List with first and last references

public class FirstLastList {
  private Link first; // ref to first link
  private Link last; // ref to last link
  public FirstLastList() {
    first = null; 
    last = null;
  }
  public boolean isEmpty() {
    return first == null;
  }
  public void insertFirst(long dd) {
    Link newLink = new Link(dd); // make new link
    if (isEmpty()) 
      last = newLink; 
    newLink.next = first; 
    first = newLink; 
  }
  public void insertLast(long dd) {
    Link newLink = new Link(dd); 
    if (isEmpty()) 
      first = newLink; 
    else
      last.next = newLink; 
      last = newLink; 
  }
  public long deleteFirst(){ 
    long temp = first.dData;
    if (first.next == null) // if only one item
      last = null; 
    first = first.next; 
    return temp;
  }
  public void displayList() {
    System.out.print("List: ");
    Link current = first; 
    while (current != null)
    {
      current.displayLink(); 
      current = current.next;
    }
    System.out.println("");
  }
  public static void main(String[] args) { // make a new list
    FirstLastList theList = new FirstLastList();
    theList.insertFirst(22);
    theList.insertFirst(44);
    theList.insertLast(33);
    theList.insertLast(55);
    theList.displayList();
    theList.deleteFirst();
    theList.deleteFirst();
    theList.displayList();
  } 
  class Link {
    public long dData; 
  
    public Link next; 
  
    public Link(long d) {
      dData = d;
    }
  
    public void displayLink() {
      System.out.print(dData + " ");
    }
  }
}

Redundancy Checker

/*
 *        Code by David Beuze. No rights reserved :) - 2006
 *
 *        contact: smerpy@gmail.ru
 */
/*
 *        This code snippet takes a list of objects and checks for any redundancy in the list.
 *        In this example I"ve taken a list of Integer, but it can be generalized to any kind
 *        of object.
 */
/*Output:
 * 
 * Oh no! The value 1 is redundant.
 * 
 * */

import java.util.Arrays;
import java.util.List;
import java.util.ListIterator;
public class RedundancyChecker {
  public static void main(String[] a) {
    new RedundancyChecker();
  }
  public RedundancyChecker() {
    Integer[] array = new Integer[5]; // Create and
    // array of
    // Integer
    Integer i0 = new Integer(0);
    array[0] = i0;
    Integer i1 = new Integer(1); // <--------
    array[1] = i1; // |
    Integer i2 = new Integer(2); // |--- redundant
    // values
    array[2] = i2; // |
    Integer i3 = new Integer(1); // <--------
    array[3] = i3;
    Integer i4 = new Integer(4);
    array[4] = i4;
    // transform the array into a List
    List l = Arrays.asList(array);
    // Check the List
    checkForRedundancy(l);
  }
  public boolean checkForRedundancy(List l) {
    ListIterator li1 = l.listIterator(); // Make a
    // general
    // ListIterator
    // on the list
    while (li1.hasNext()) {
      // Store the value of the actual first checked
      // element of the List,
      // it needs to be stored because it calls the
      // .next(), which we can call only once per loop
      // in order to sweep the whole list.
      int check1 = ((Integer) li1.next()).intValue();
      // Make a second ListIterator that will start
      // with the element that is just after the
      // actual first checked one,
      // in order to avoid checking several times the
      // same elements.
      ListIterator li2 = l.listIterator(li1.nextIndex() + 1);
      while (li2.hasNext()) {
        // Store the following elements one by
        // one and check to see if they match
        // the actual one.
        int check2 = ((Integer) li2.next()).intValue();
        if (check1 == check2) {
          System.out.println("Oh no! The value " + check1 + " is redundant.");
          return true;
        }
      }
      // The .next() method has already been called at
      // the beginning of the loop.
    }
    return false;
  }
}

Sorted list

public class SortedList {
  private Link first; 
  public SortedList() {
    first = null;
  }
  public boolean isEmpty(){
    return (first == null);
  }
  public void insert(long key){
    Link newLink = new Link(key); 
    Link previous = null; 
    Link current = first;
    while (current != null && key > current.data) {
      previous = current;
      current = current.next;
    }
    if (previous == null)
      first = newLink; 
    else
      previous.next = newLink; 
    newLink.next = current; 
  }
  public Link remove() { 
    Link temp = first; 
    first = first.next;
    return temp; 
  }
  public void displayList() {
    System.out.print("List: ");
    Link current = first; 
    while (current != null){
      current.displayLink(); 
      current = current.next;
    }
    System.out.println("");
  }
  public static void main(String[] args) { 
    SortedList theSortedList = new SortedList();
    theSortedList.insert(20); 
    theSortedList.insert(40);
    theSortedList.displayList(); 
    theSortedList.insert(10); 
    theSortedList.insert(30);
    theSortedList.insert(50);
    theSortedList.displayList(); 
    theSortedList.remove(); 
    theSortedList.displayList(); 
  } 
  class Link {
    public long data; 
  
    public Link next; 
  
    public Link(long dd) {
      data = dd;
    }
  
    public void displayLink() {
      System.out.print(data + " ");
    }
  }
}