- 集合的分类
- 一、Iterator接口(迭代器)
- 迭代器需要注意的地方
- 二、Collection接口
- 遍历方式(五种)
- ArrayList类
- LinkedList
- Vector
- Set接口
- HashSet
- TreeSet
- 三.Map集合
- HashMap
- TreeMap
- 四.数据结构模拟实现
- 双向链表
- 节点
- 实现
- 单链表
- 节点
- 实现
- 循环链表的实现
- 节点
- 实现
集合的分类
-
Collection集合(单列集合的接口)
List接口集合(存取有序,集合可有重复值,有索引的) 实现类 ArrayList (底部通过数组) LinkedList(底部通过双向链表实现) Vector(线程安全 也是数组实现)--->Stack(线程安全的栈) set接口集合(存取无序,不可有重复值,无索引) 实现类 Hashset(底部通过哈希表)--->LinkedHashset(底部哈希表+链表) (无序,不可有重复值,无索引)(有序,不重复,无索引) TreeSet(底部通过红黑树) (默认按升序排列,不可有重复值,无索引) -
Map集合(双列集合的接口 键值对的数据)
实现类 HashMap(哈希表) LinkedHashMap(哈希表+链表) TreeMap(红黑树)
-
Iterator迭代器
一般iterator 其他迭代器
集合的整体框架图
- 集合只能存储引用类型
- 提供的方法
- Iterable 含有foreach.迭代器和一个分离器
- Iterator迭代器需要注意的地方iterator(); //迭代器 - void forEach(Consumer super T> action) //增强for循环 - void Spliterator spliterator() //分离器
* 当使用迭代器遍历的时候一定要注意:
* 1.只要调用过一次next(),指针就会下移
* 2.当出现迭代器和集合并行调用时会出现并行异常
* throw ConcurrentModificationException //并行修改异常
* while (iterator.hasNext()){
* strings.remove(iterator.next());
* 有一种特殊情况会不报错
* 当前检查异常的方法 当modCount == expectedModCount时
* 就不会报错一般在倒数几个,和你使用next()次数有关
* final void checkForComodification() {
* if (modCount != expectedModCount)
* throw new ConcurrentModificationException();
* }
* 3.在想要删除元素时,可以通过迭代器自己的 iterator.remove();
* 4.想要使用add(),需要使用下层迭代器ListIterator
二、Collection接口
- 提供的方法
基本都是一些增删改查和流的方法
int size (); //大小
boolean isEmpty (); //判空
boolean contains (Object o); //包含
T[]toArray(T[]a);//转数组
boolean add (E e); //添加
boolean remove (Object o); //删除
boolean containsAll (Collection < ? > c); //包含
boolean addAll (Collection < ? extends E > c); //添加
boolean removeAll (Collection < ? > c);
void clear (); //清除
default
Stream stream () //顺序流
Stream parallelStream () //并行流
遍历方式(五种)
//迭代器
Iterator iterator = strings.iterator();
while (iterator.hasNext()){
System.out.println(iterator.next());
}
//增强for(也是迭代器实现)
for (String str : strings){
System.out.println(str);
}
//foreach(都行)
strings.forEach(System.out::println);
strings.forEach((String s)->{
System.out.println(s);
});
strings.forEach(new Consumer() {
@Override
public void accept(String s) {
System.out.println(s);
}
});
//fori(需要逻辑判断,因为数组删除,增加会自动向前或者向后一定一位,可能会造成误差,少读)
// 集合stream流(流不修改数据,只操作数据)
strings.stream().forEach(System.out::println);
- 提供的特有方法
基本都是和索引相关的方法
boolean addAll(int index, Collection extends E> c); //提供从位置插入所有 void replaceAll(UnaryOperatorArrayList类operator) //替代所有 void sort(Comparator super E> c) //通过comparator进行排序 E get(int index) //根据下标获取元素 E set(int index, E element) //根据下标设置元素 void add(int index, E element); //根据下标增加元素 E remove(int index) //删除元素 int indexOf(Object o); //返回第一次出现数组下标 int lastIndexOf(Object o) //返回最后依次出现的下标 List subList(int fromIndex, int toIndex);//返回之间的左包右不包 static List copyOf(Collection extends E> coll) //备份
- 默认容量
当创建集合时是为一个空的数组;
向空数组加元素时
// 通过add()-->grow() return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity DEFAULT_CAPACITY = 10
- 当存入超过10时 自增策略
private Object[] grow(int minCapacity) {
int oldCapacity = elementData.length;
//当数组不为空还超出数组长度时
if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
{
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity,
oldCapacity >> 1 //除二操作 );
//数组长度的自增是通过数组的cpoyof复制到新长度下的数组中,不是在后面添加长度,所以自增时非常耗时的操作当提前预知需要的多少的时候,可以提前给数组赋长度值
return elementData = Arrays.copyOf(elementData, newCapacity);
}
}
}
//新长度定义策略
public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
// preconditions not checked because of inlining
// assert oldLength >= 0
// assert minGrowth > 0
int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow
if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {
return prefLength;
} else {
// put code cold in a separate method
return hugeLength(oldLength, minGrowth);
}
}
//异常处理,健壮性
private static int hugeLength(int oldLength, int minGrowth) {
int minLength = oldLength + minGrowth;
if (minLength < 0) { // overflow
throw new OutOfMemoryError(
"Required array length " + oldLength + " + " + minGrowth + " is too large");
} else if (minLength <= SOFT_MAX_ARRAY_LENGTH) {
return SOFT_MAX_ARRAY_LENGTH;
} else {
return minLength;
}
}
- 提供的方法
void trimToSize() //修剪容量到当前容量大小LinkedList
由于是双向链表的实现
提供的特有方法都和链表有关
public E removeFirst() //头部删除 public E removeLast() //尾部删除 public void addFirst(E e) //头插法 public void addLast(E e) //尾插法Vector
是线程安全的list集合
它的增删改查都是加了sychronized锁的
public synchronized void removeElementAt(int index) public synchronized void insertElementAt(E obj, int index) public synchronized void addElement(E obj) public synchronized E get(int index)Set接口 HashSet TreeSet 三.Map集合 HashMap TreeMap 四.数据结构模拟实现 双向链表 节点
//节点 class DouleNode实现{ T val; // 节点值 DouleNode prev; //直接前驱 DouleNode next; //直接后驱 public DouleNode(T val) { this.val = val; } }
public class DoubleLinkNode单链表 节点{ //双向链表 private DouleNode head; //头部 int size; //链表长度 public DoubleLinkNode() { //初始化头部 head = null; size = 0; } //头插法 public void addFromFirst(T data) { DouleNode newNode = new DouleNode(data); if (this.head == null) { this.head = newNode; size++; } else { newNode.next = this.head; this.head.prev = newNode; this.head = newNode; size++; } } //尾插法 public void addLast(T data) { DouleNode newNode = new DouleNode(data); if (this.head == null) { this.head = newNode; size++; } else { DouleNode cache = this.head; while (cache.next != null) { cache = cache.next; } cache.next = newNode; newNode.prev = cache; size++; } } ; //任意位置插入,第一个数据节点为0号下标 public boolean addIndex(int index, T data) { DouleNode cache = head; if (size < index) { System.out.println("插入失败"); return false; } else { for (int i = 0; i < index; i++) { cache = cache.next; } DouleNode newNode = new DouleNode(data); newNode.next = cache; /// newNode.prev = cache.prev; cache.prev = newNode; newNode.prev.next = newNode; size++; return true; } } ; //打印 public void display() { DouleNode cache = head; for (int i = 0; i < size; i++) { System.out.println(cache.val); cache = cache.next; } } ; }
class Node实现{ //数据类型 节点 T data; //节点数据 Node next; //指向下一个节点 public Node() { } public Node(T data, Node next) { this.data = data; this.next = next; } @Override public String toString() { return "Node{" + "data=" + data + '}'; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Node> node = (Node>) o; return Objects.equals(data, node.data) ; } @Override public int hashCode() { return Objects.hash(data, next); } }
public class LinkNode循环链表的实现 节点{ Node phead; public LinkNode() { //初始化 phead = new Node<>(null, null); } //头插法 public void addFromHead(T data){ Node newNode = new Node<>(data, null); Node last= phead; if (last.next == null) { last.next=newNode; return; } newNode.next=last.next; last.next=newNode; } //尾插法 public void addFromLast(T data){ Node newNode = new Node<>(data,null); Node last= phead; if (last.next == null) { last.next=newNode; return; } while (last.next != null) { last.next=last; } last.next=newNode; } //删除节点 public void remove(T t){ Node remoNode = new Node<>(t, null); Node last = phead; if (last == null) { System.out.println("链表为空"); return; } while(last.next!=null){ if (last.next.equals(remoNode)){ last.next=last.next.next; System.out.println("删除成功"); break; } last=last.next; } } //循环打印 public void printLink(){ Node last=phead; if (last.next == null) { System.out.println("链表为空"); return; } while (last.next != null) { System.out.println(last.next); last=last.next; } } }
class LoopNode实现{ T data; LoopNode next; public LoopNode() { } public T getData() { return data; } public LoopNode(T data) { this.data = data; } public void setData(T data) { this.data = data; } public LoopNode getNext() { return next; } public void setNext(LoopNode next) { this.next = next; } }
public class LoopLinkNode {
private LoopNode head;
private LoopNode last;
int size;
public LoopLinkNode() {
head=last=null;
size=0;
}
public void addFromHead(LoopNode newNode){
if(size==0){
newNode.setNext(newNode);
head=last=newNode;
size++;
}else{
last.setNext(newNode);
newNode.setNext(head);
head=newNode;
size++;
}
}
public void addFromLast(LoopNode newNode){
if(size==0){
newNode.setNext(newNode);
head=last=newNode;
size++;
}else{
last.setNext(newNode);
newNode.setNext(head);
last=newNode;
size++;
}
}
public void printLoopList(){
LoopNode cache = new LoopNode();
cache=head;
while(cache.next!=head){
System.out.println(cache.getData());
cache=cache.next;
}
System.out.println(cache.getData());
}
}



