数据结构API

interface接口(申明后直接调用方法)-implement实现(不关心)

1. 集合类基本接口

1
2
3

Collection{
    add(e);
    iterator迭代器();}

1.1 迭代器

iterator{
    next();
    hasNext();
    remove();}

next最后会抛出异常，需要先hasNext;

查找一个元素唯一个方法是next；

1.2删除 remove前必须先next，remove删除上次next返回的元素;

1.3 Collection 泛型实用方法,所有都能用:

import java.util.Collection<E>;

Iterator<E> iterator();//返回一个用于访问集合每个元素的迭代器    

int size();

boolean isEmpty();

boolean contains(Object obj);

boolean containsAll(Collection<?> c);

boolean equals(Object other);

boolean add(Object obj);//有返回值

boolean addAll(Collection<? extends> from);

boolean remove(Object obj);

boolean removeAll(Collection<?> c);

void clear();

boolean retainAll(Collection<?> other);//保留，既删除所有与other集合不一样的元素
    
Object[] toArray();

import java.util.Iterator<E>;

boolean hasNext();

E next();//到达尾部报错

void remove();//删除上次访问对象，紧跟next，如果期间集合发生变化报错

2 具体集合

map结尾的类以外都实现了Collection接口，map结尾的类实现map接口

2.1 链表LinkList

数组列表，链表共有

import java,util.List<E>;

ListIterator<E> listOterator();//列表迭代器，用来迭代

ListIterator<E> listOterator(int index);

void add(int i,E element);//在给定位置添加，无返回值，默认成功

Void addAll(int i,Collection<? extends E> elements);

E remove(int i);//删除该位置元素并返回

E get(int i);//get和set随机访问每一个元素只适用于数组列表，链表只能用迭代器提供的

E set(int i,E element);

int indexOf(Object obj);//如果没有返回-1

int lastIndexOf(Object obj);//返回列表中最后一次出现的元素，没有返回-1

import java.util.ListIterator;

void add(E newElement);//当前位置

void set(E newElement);//修改next上次访问位置，如果列表在其间被修改了，会报错

boolean hasPrevious();//反向的hasNext

E previous();//头，抛出异常

int nextIndex();//下次调用next返回索引

int prevIndex();

链表专属独有

import java.util.LinkedList<E>;

LinkedList();//构造空链表

LinkedList(Collection<? extends E> elements);

void addFirst(E element);

void addLast(E element);//在头或尾添加

E getFirst();

E getLast();//返回头或尾元素

E removeFirst();

E removeLast();

2.2 数组列表 ArryList 类实现了List接口

List接口（包含的迭代器）描述有顺序的集合，位置重要，两种协议：1get和set随机访问每一个元素只适用于数组列表，2链表只能用迭代器提供的。

Victor同步，多线程同时访问安全；ArryList不同步，多个同时访问不安全。

2.3 散列集 HashSet

无序

HashTable 散列表用链表数组实现，每个列表桶。

散列表实现的数据类型如HashSet

import java.HashSet<E>;

HashSet();

HashSet(Collection<? extends E> elements);

HashSet(int initialCapacity);//构造指定桶的空散列集

HashSet(int initialCapacity,float loadFactor);//填装因子，大于时再散列

1
2
3

import java.lang.Object;

int hashCode();//返回哈希码

2.4 树集TreeSet，排序集

有排序的集合（sorted collection）

import java.util.TreeSet<E>;

TreeSet();

TreeSet(Collection<? extends E> elements);

和比较紧密相关，因为是排序集合

2.5 排序集的对象比较

1
2
3

import java.lang.Comparable<T>;

int comparable(T other);//将这个对象this与other比较，this在other之前，返回负值，之后返回正值，相同为0

1
2
3

import java.util.Comparator<T>;
    
int comparable(T a,T b);//a与b比较

import java.util.SortSet<E>;

Comparator<? super E> comparator();//返回对元素排序的比较器？

E first();

E last();//返回排序集合的最小或最大

import java.util.NavigableSet<E>;

E higher(E value);//返回大于value的最小元素或最大，没有返回null

E lower(E value);

E ceiling(E value);

E floor(E value);//返回最大或最小，没有则null

E pollFirst();

E pollLast();//删除并返回这个排序集的最大或最小，空null

Iterator<E> descendingIterator();//返回一个按递减顺序遍历集中元素的迭代器

import java.util.TreeSet<E>;

TreeSet();

TreeSet(Collection<? super E> c);//构造树，用指定比较器对其中元素排序

TreeSet(Collection<? extends E> elements);//构造树，所有元素添加，与给定集相同元素的比较器

2.6 队列Queue与双端队列Deque

import java.util.Queue<E>;

boolean add(E element);

boolean offer(E element);//如果队列没满，添加队尾返回true；满了add抛出异常，offer false

E remove();

E poll();//队列不空，返回第一个并删除；空，remove报错，第二个null

E element();

E peek();//队列不空，返回头；空，element抛出异常，peek null

import java.util.Deque;

void addFirst(E element);

void addLast(E element);

boolean offerFirst(E element);

boolean offerLast(E element);//如果满，add抛出异常，offer false

E removeFist();

E removeLast();

E pollFirst();

E pollLast();//不空，删除并返回，空remove报错，poll null

E getFirst();

E getLast();

E peekFirst();

E peekLast();//返回头，空，get报错，peek null

import java.util.ArrayDeque;

ArrayDeque();

ArrayDeque(int initialCapacity);//初始化16或给定容量双端队列

2.7 优先级队列PriorityQueue (最小)堆heap

import java.util.PriorityQueue;

PriorityQueue();

PriorityQueue(int initialCapacity);//构造一个用于存放Comparable对象的优先级队列

PriorityQueue(int initialCapacity,Comparator<? super E> c);//构造一个优先级队列，指定比较器排序

2.8映射表Map<K,V> 泛型

import java.util.Map<K,V>;

V get(Object Key);//返回key对应value，没有null

V put(K key,V value);插入，如果存在，取代，返回旧值；键可以为null值不能为null

void putAll(Map<? extends K, ? extends V> entries);

boolean containsKey(Object key);

boolean containsValue(Object value);

set<Map.Entry<K,V> entrySet();//返回Map.Entry的集视图，也就是映射表的KV对;可以从这儿删除元素，映射表也同步删除，不能添加

Set<K> KeySet();//映射表所有键的集视图，可删除不能添加

Collection<V> values();//映射表所有值的集视图，可删除不能添加

import java.util.Map.Entry<K,V>;

K getKey();

V getValue();

V setValue(V newValue);//设置新值，返回旧值

import java.util.HashMap<K,V>;

HashMap();

HashMap(int initialCapacity);

HashMap(int initialCapacity,float loadFactor)//填装因子

import java.util.TreeMap<K,V>;

TreeMap(Comparator<? super K> c);//构造树映射表，指定比较器排序

TreeMap(Map<? extends K, extends V> entires);//映射表全部添加到树映射表

TreeMap(SortedMap<? extends K, extends V> entires);//排序映射表添加到树映射表，用相同的比较器

import java.util.SortedMap<K,V>;

Comparator<? super K> comparator);//返回对K排序的比较器，compareto null

K firstKey();

K lastKey();

2.9 HashTable Vector enum Stack

hashTable 与hashMap区别不大，不同是HashTable线程安全，同步访问；

vector与ArrayList同理；

import java.util.Enumeration<E>;

boolean hasMoreElement();有更多true

E nextElement();hasmore false 会报错

import java.util.Hashtable<K,V>;

Enumeration<K> Keys();//遍历 枚举

Enumeration<V> elements();

1
2
3

import java.util.Vector<V>;

Enumeration<E> elements();

import java.util.Stack<E>;

E push(E item);

E pop();

E peek();//空会报错

位？

集合框架framework 展示Collection||Map两个接口的混用

2022/3/15

1. 集合类 基本接口