Java中的常用数据结构（未完待续...）

冷不防 2023-02-24 08:21 2阅读 0赞

1.Java中常用的数据结构

ArrayList、LinkedList、HashMap、HashSet、TreeMap、ConcurrentHashMap

2.Collection、List、Iterable、Iterator

public interface Iterable<T> { 
    	Iterator<T> iterator();
    }
    
    public interface Iterator<E> { 
    	boolean hasNext();
    	E next();
    }
    
    public interface Collection<E> extends Iterable<E> { 
    	int size();
    	boolean isEmpty();
    	boolean constains(Object o);
    	Iterator<E> iterator();
    	boolean add(E e);
    	boolean remove(Object o);
    }   
    
    public interface List<E> extends Collection<E> { 
    	int size();
    	boolean isEmpty();
    	boolean constains(Object o);
    	Iterator<E> iterator();
    	boolean add(E e);
    	boolean remove(Object o);
    }

3.ArrayList  
内部使用Object\[\] elementData数组实现。主要方法有get、set、add、remove等。

public class ArrayList<E> extends AbstractList<E>
            implements List<E>, RandomAccess, Cloneable, java.io.Serializable { 
    	private static final int DEFAULT_CAPACITY = 10;
        private static final Object[] EMPTY_ELEMENTDATA = { };
    	private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = { };
    	transient Object[] elementData;
    	private int size;
    	
        public ArrayList(int initialCapacity) { 
            if (initialCapacity > 0) { 
                this.elementData = new Object[initialCapacity];
            } else if (initialCapacity == 0) { 
                this.elementData = EMPTY_ELEMENTDATA;
            } else { 
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
            }
        }
        public ArrayList() { 
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }
        public int size() { 
            return size;
        }
        public boolean isEmpty() { 
            return size == 0;
        }
        public boolean contains(Object o) { 
            return indexOf(o) >= 0;
        }
        public E get(int index) { 
            rangeCheck(index);
            return elementData(index);
        }
        public E set(int index, E element) { 
            rangeCheck(index);
            E oldValue = elementData(index);
            elementData[index] = element;
            return oldValue;
        }
        public boolean add(E e) { 
            ensureCapacityInternal(size + 1); 
            elementData[size++] = e;
            return true;
        }
        private void grow(int minCapacity) { 
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            elementData = Arrays.copyOf(elementData, newCapacity);
        } 
        public void add(int index, E element) { 
            rangeCheckForAdd(index);
    
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            System.arraycopy(elementData, index, elementData, index + 1,
                             size - index);
            elementData[index] = element;
            size++;
        }
        public E remove(int index) { 
            rangeCheck(index);
    
            modCount++;
            E oldValue = elementData(index);
    
            int numMoved = size - index - 1;
            if (numMoved > 0)
                System.arraycopy(elementData, index+1, elementData, index,
                                 numMoved);
            elementData[--size] = null; // clear to let GC do its work
    
            return oldValue;
        }
        public boolean remove(Object o) { 
            if (o == null) { 
                for (int index = 0; index < size; index++)
                    if (elementData[index] == null) { 
                        fastRemove(index);
                        return true;
                    }
            } else { 
                for (int index = 0; index < size; index++)
                    if (o.equals(elementData[index])) { 
                        fastRemove(index);
                        return true;
                    }
            }
            return false;
        }
        public void clear() { 
            modCount++;
            // clear to let GC do its work
            for (int i = 0; i < size; i++)
                elementData[i] = null;
            size = 0;
        }
    }

4.LinkedList  
LinkedList的节点有元素、前驱、后继三个属性，既可以从前向后遍历，也可以从后向前遍历。  
可以通过add、remove作为链表。  
可以通过addFirst、addLast、removeFirst、removeLast作为双端队列。  
可以通过push、pop当作栈。

public class LinkedList<E>
        extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable
    { 
    	transient int size = 0;
    	transient Node<E> first;
    	transient Node<E> last;
    	public LinkedList() { }
        public E getFirst() { 
            final Node<E> f = first;
            if (f == null)
                throw new NoSuchElementException();
            return f.item;
        }
        public E getLast() { 
            final Node<E> l = last;
            if (l == null)
                throw new NoSuchElementException();
            return l.item;
        }
        public E removeFirst() { 
            final Node<E> f = first;
            if (f == null)
                throw new NoSuchElementException();
            return unlinkFirst(f);
        }
        public E removeLast() { 
            final Node<E> l = last;
            if (l == null)
                throw new NoSuchElementException();
            return unlinkLast(l);
        }
        public void addFirst(E e) { 
            linkFirst(e);
        }
        public void addLast(E e) { 
            linkLast(e);
        }
        public boolean contains(Object o) { 
            return indexOf(o) != -1;
        }
        public int size() { 
            return size;
        }
        public boolean add(E e) { 
            linkLast(e);
            return true;
        }
        public boolean remove(Object o) { 
            if (o == null) { 
                for (Node<E> x = first; x != null; x = x.next) { 
                    if (x.item == null) { 
                        unlink(x);
                        return true;
                    }
                }
            } else { 
                for (Node<E> x = first; x != null; x = x.next) { 
                    if (o.equals(x.item)) { 
                        unlink(x);
                        return true;
                    }
                }
            }
            return false;
        }
        public E get(int index) { 
            checkElementIndex(index);
            return node(index).item;
        }
        public E set(int index, E element) { 
            checkElementIndex(index);
            Node<E> x = node(index);
            E oldVal = x.item;
            x.item = element;
            return oldVal;
        }
        public void add(int index, E element) { 
            checkPositionIndex(index);
    
            if (index == size)
                linkLast(element);
            else
                linkBefore(element, node(index));
        }
        public E remove(int index) { 
            checkElementIndex(index);
            return unlink(node(index));
        }
        public E peek() { 
            final Node<E> f = first;
            return (f == null) ? null : f.item;
        }
        public E element() { 
            return getFirst();
        }
        public E poll() { 
            final Node<E> f = first;
            return (f == null) ? null : unlinkFirst(f);
        }
       public E remove() { 
            return removeFirst();
        }
        public boolean offer(E e) { 
            return add(e);
        }
        public void push(E e) { 
            addFirst(e);
        }
        public E pop() { 
            return removeFirst();
        }
        private static class Node<E> { 
            E item;
            Node<E> next;
            Node<E> prev;
    
            Node(Node<E> prev, E element, Node<E> next) { 
                this.item = element;
                this.next = next;
                this.prev = prev;
            }
        }