如何用链表实现Collection

Question

不明白，Java中有完整的Collection的实现类，为什么还要自己实现呢？

Answer 1

补充一下,除了数组和循环外,主要使用序列化Serializeable

Answer 2

import java.util.*;
import java.io.*;
public class Collections {
    private Collections() {}
    private static final int BINARYSEARCH_THRESHOLD   = 5000;
    private static final int REVERSE_THRESHOLD        =   18;
    private static final int SHUFFLE_THRESHOLD        =    5;
    private static final int FILL_THRESHOLD           =   25;
    private static final int ROTATE_THRESHOLD         =  100;
    private static final int COPY_THRESHOLD           =   10;
    private static final int REPLACEALL_THRESHOLD     =   11;
    private static final int INDEXOFSUBLIST_THRESHOLD =   35;
    public static void sort(List list) {
Object a[] = list.toArray();
Arrays.sort(a);
ListIterator i = list.listIterator();
for (int j=0; j<a.length; j++) {
    i.next();
    i.set(a[j]);
}
    }
    public static void sort(List list, Comparator c) {
Object a[] = list.toArray();
Arrays.sort(a, c);
ListIterator i = list.listIterator();
for (int j=0; j<a.length; j++) {
    i.next();
    i.set(a[j]);
}
    }
    public static int binarySearch(List list, Object key) {
        if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
            return indexedBinarySearch(list, key);
        else
            return iteratorBinarySearch(list, key);
    }    private static int indexedBinarySearch(List list, Object key) {
int low = 0;
int high = list.size()-1; while (low <= high) {
    int mid = (low + high) >> 1;
    Object midVal = list.get(mid);
    int cmp = ((Comparable)midVal).compareTo(key);     if (cmp < 0)
low = mid + 1;
    else if (cmp > 0)
high = mid - 1;
    else
return mid; // key found
}
return -(low + 1);  // key not found
    }    private static int iteratorBinarySearch(List list, Object key) {
int low = 0;
int high = list.size()-1;
        ListIterator i = list.listIterator();        while (low <= high) {
            int mid = (low + high) >> 1;
            Object midVal = get(i, mid);
            int cmp = ((Comparable)midVal).compareTo(key);            if (cmp < 0)
                low = mid + 1;
            else if (cmp > 0)
                high = mid - 1;
            else
                return mid;
        }
        return -(low + 1);
    }
    private static Object get(ListIterator i, int index) {
        Object obj = null;
        int pos = i.nextIndex();
        if (pos <= index) {
            do {
                obj = i.next();
            } while (pos++ < index);
        } else {
            do {
                obj = i.previous();
            } while (--pos > index);
        }
        return obj;
    }
    public static int binarySearch(List list, Object key, Comparator c) {
        if (c==null)
            return binarySearch(list, key);        if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
            return indexedBinarySearch(list, key, c);
        else
            return iteratorBinarySearch(list, key, c);
    }    private static int indexedBinarySearch(List l, Object key, Comparator c) {
int low = 0;
int high = l.size()-1; while (low <= high) {
    int mid = (low + high) >> 1;
    Object midVal = l.get(mid);
    int cmp = c.compare(midVal, key);     if (cmp < 0)
low = mid + 1;
    else if (cmp > 0)
high = mid - 1;
    else
return mid;
}
return -(low + 1);
    }    private static int iteratorBinarySearch(List l, Object key, Comparator c) {
int low = 0;
int high = l.size()-1;
        ListIterator i = l.listIterator();        while (low <= high) {
            int mid = (low + high) >> 1;
            Object midVal = get(i, mid);
            int cmp = c.compare(midVal, key);            if (cmp < 0)
                low = mid + 1;
            else if (cmp > 0)
                high = mid - 1;
            else
                return mid;
        }
        return -(low + 1);
    }

Answer 3

public static void reverse(List list) {
        int size = list.size();
        if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) {
            for (int i=0, mid=size>>1, j=size-1; i<mid; i++, j--)
                swap(list, i, j);
        } else {
            ListIterator fwd = list.listIterator();
            ListIterator rev = list.listIterator(size);
            for (int i=0, mid=list.size()>>1; i<mid; i++) {
                Object tmp = fwd.next();
                fwd.set(rev.previous());
                rev.set(tmp);
            }
        }
    }    public static void shuffle(List list) {
        shuffle(list, r);
    }
    private static Random r = new Random();    public static void shuffle(List list, Random rnd) {
        int size = list.size();
        if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
            for (int i=size; i>1; i--)
                swap(list, i-1, rnd.nextInt(i));
        } else {
            Object arr[] = list.toArray();
            for (int i=size; i>1; i--)
                swap(arr, i-1, rnd.nextInt(i));
            ListIterator it = list.listIterator();
            for (int i=0; i<arr.length; i++) {
                it.next();
                it.set(arr[i]);
            }
        }
    }
public static void swap(List list, int i, int j) {
        list.set(i, list.set(j, list.get(i)));
    }
    private static void swap(Object[] arr, int i, int j) {
        Object tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    public static void fill(List list, Object obj) {
        int size = list.size();
        if (size < FILL_THRESHOLD || list instanceof RandomAccess) {
            for (int i=0; i<size; i++)
                list.set(i, obj);
        } else {
            ListIterator itr = list.listIterator();
            for (int i=0; i<size; i++) {
                itr.next();
                itr.set(obj);
            }
        }
    }
    public static void copy(List dest, List src) {
        int srcSize = src.size();
        if (srcSize > dest.size())
            throw new IndexOutOfBoundsException("Source does not fit in dest");        if (srcSize < COPY_THRESHOLD ||
            (src instanceof RandomAccess && dest instanceof RandomAccess)) {
            for (int i=0; i<srcSize; i++)
                dest.set(i, src.get(i));
        } else {
            ListIterator di=dest.listIterator(), si=src.listIterator();
            for (int i=0; i<srcSize; i++) {
                di.next();
                di.set(si.next());
            }
        }
    }
    public static Object min(Collection coll) {
Iterator i = coll.iterator();
Comparable candidate = (Comparable)(i.next());        while(i.hasNext()) {
    Comparable next = (Comparable)(i.next());
    if (next.compareTo(candidate) < 0)
candidate = next;
}
return candidate;
    }

Answer 4

用java实现链表，一般是用两个数组，一个记录值，另一个记录位置。不过LinkedList已经很好用了，你为什么要自己作？如果一定要自己实现在，可以在网上打《数据结构（java版）》这本书，里面有非常详细的介绍。

Answer 5

请问《数据结构（java版）》哪里有下载？