Java/Collections Data Structure/Custom List
Содержание
A growable array of int values, suitable for use with multiple threads
<source lang="java">
/*
* 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 }
}
</source>
Another Link list
<source lang="java">
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(); }
}
</source>
Doubly-linked list with data structure
<source lang="java">
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 + " "); }
}
</source>
Frist last list
<source lang="java">
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(); }
}
</source>
List with first and last references
<source lang="java">
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 + " "); } }
}
</source>
Redundancy Checker
<source lang="java">
/*
* 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; }
}
</source>
Sorted list
<source lang="java">
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 + " "); } }
}
</source>