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