集合背后的数据结构

• 集合介绍：
• • Collection
• 实现List接口的类：
• • 1.Stack
  • • 栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出的原则
  • 2.Queue
  • • 队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出的特点
    • 循环队列
  • 3.ArrayList
  • • (1).add:
    • (2).void add(int index, E element):
    • (3).addAll()：
    • (4.)get():
    • (5).E remove(int index):
    • (6).boolean remove(Object o)：
  • 4.LinkedList

集合介绍：
文章图片

可以看到集合类的基本接口是Collection接口，而Collection接口继承了Iterable接口,这个接口内部只有一个方法public abstract Iterator iterator()，而这个迭代器对象用于依次访问集合中的元素

文章图片

接下来让我跟你们介绍一下迭代器Iterator：

文章图片

1.hasnext()方法：集合中有元素的时候返回true，否则返回false；

2.next()方法：首先迭代器指向第一个元素的前面的空白部分，调用next后迭代器越过下一个元素，并且返回这个元素的引用；

3.remove()方法：删除上次next返回的元素，他们互相依赖，所以next（）方法应用在remove（）方法的前面；

接下来介绍Collection集合
Collection

所包含的方法	说明
boolean add(E e)	将元素 e 放入集合中
void clear()	删除集合中的所有元素
boolean isEmpty()	判断集合是否没有任何元素，俗称空集合
boolean remove(Object e)	如果元素 e 出现在集合中，删除其中一个
int size()	返回集合中的元素个数
Object[] toArray()	返回一个装有所有集合中元素的数组

Collection作为基本接口，其中的方法能被所实现了的子类所使用
List集合是线性表，区别于Set，Set不能出现重复的元素
实现List接口的类： 1.Stack

方法	说明
E push(E item)	入栈
E pop()	出栈
E peek()	返回栈顶元素
boolean empty()	判断栈是否为空

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出的原则
实现Stack：

import java.util.Arrays; public class MyStack {private T[] elem; //数组 private int top; //栈顶指针public MyStack() {this.elem = (T[])new Object[10]; }public void push(T item) {//1、判断当前栈是否是满 if(isFull()){this.elem = Arrays.copyOf(this.elem,2*this.elem.length); } this.elem[this.top++] = item; }public boolean isFull(){return this.elem.length == this.top; }public T pop() {if(empty()) {throw new UnsupportedOperationException("栈为空！"); } T ret = this.elem[this.top-1]; this.top--; return ret; } public T peek() {if(empty()) {throw new UnsupportedOperationException("栈为空！"); } return this.elem[this.top-1]; } public boolean empty(){return this.top == 0; } } public static void main(String[] args) {MyStack myStack = new MyStack<>(); myStack.push(1); myStack.push(2); myStack.push(3); System.out.println(myStack.peek()); //3 System.out.println(myStack.pop()); //3 System.out.println(myStack.pop()); //2 System.out.println(myStack.pop()); //1 System.out.println(myStack.empty()); //true }

动画演示：

文章图片

2.Queue

方法	说明
void offer()	向队尾插入一个元素
int poll()	删除队头元素
int peek(）	获取队头元素
boolean isEmpty()	判断队列是否为空

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出的特点
进行插入操作的一端称为队尾
进行删除操作的一端称为队头
实现：

class Node {private int val; private Node next; public int getVal() {return val; } public void setVal(int val) {this.val = val; } public Node getNext() {return next; } public void setNext(Node next) {this.next = next; } public Node(int val) {this.val = val; } } public class MyQueue {private Node first; private Node last; //入队 public void offer(int val) {//判断是不是第一次插入 Node node = new Node(val); if(this.first == null) {this.first = node; this.last = node; }else {this.last.setNext(node); //last.next = node; this.last = node; } } //出队 public int poll() {//判断是否为空的 if(isEmpty()) {throw new UnsupportedOperationException("队列为空！"); } //this.first = this.first.next; int ret = this.first.getVal(); this.first = this.first.getNext(); return ret; } //得到队头元素 public int peek() {if(isEmpty()) {throw new UnsupportedOperationException("队列为空！"); } return this.first.getVal(); } //队列是否为空 public boolean isEmpty() {return this.first == null; } public static void main(String[] args) {MyQueue myQueue = new MyQueue(); myQueue.offer(1); myQueue.offer(2); myQueue.offer(3); myQueue.offer(1); myQueue.offer(2); myQueue.offer(3); System.out.println(myQueue.peek()); //1 System.out.println(myQueue.poll()); //1 System.out.println(myQueue.poll()); //2 System.out.println(myQueue.poll()); //3 while(myQueue!=null){System.out.println(myQueue.poll()); } System.out.println(myQueue.isEmpty()); //true } }

文章图片

循环队列
循环队列由front队头指针和rear队尾指针分别来删除元素和添加元素
循环队列的特点：
1.在rear等于front的时候队列空
2.rear+1==front的时候队满
3.大小为size的队列实际用到的只有size-1个空间
循环队列的一个好处是我们可以利用这个队列之前用过的空间

文章图片

代码实现：

class MyCircularQueue {public int front; public int rear; public int length; public int []elem; public MyCircularQueue(int k) {elem=new int[k+1]; rear=0; front=rear; length=k+1; }public boolean enQueue(int value) {if(isFull()){return false; } elem[rear]=value; rear=(rear+1)%length; return true; }public boolean deQueue() {if(isEmpty()){return false; } front=(front+1)%length; return true; }public int Front() {if(isEmpty()){return -1; } return elem[front]; }public int Rear() {if(isEmpty()){return -1; } return elem[((rear-1)+length)%length]; }public boolean isEmpty() {if(rear==front) return true; else{return false; } }public boolean isFull() {if((rear+1)%length==front){return true; }else{return false; } } }

3.ArrayList 底层是数组：
缺点：
①数组长度固定,超过数组大小需要扩容并且元素拷贝，返回一个新的数组，效率低下
②插入(删除)元素慢：往数组的中插入(删除)一个元素，要把数组中那个新增元素后面的元素往后面（前面）挪动一位，消耗时间多，效率低
优点：
①随机访问，查找修改快，时间复杂度为O(1)

主要方法	说明
boolean add()	表尾添加一个元素
boolean addAll(Collection c)	按照集合的顺序，将指定集合中的所有元素追加到列表尾
E get(int index)	返回Index位置的元素
boolean remove(Object o)	删除指定元素的第一个出现元素(如果存在)

// 默认容量private static final int DEFAULT_CAPACITY = 10; //空数组，容量为0调用 private static final Object[] EMPTY_ELEMENTDATA = https://www.it610.com/article/{ }; // 空数组，传入容量时使用，添加第一个元素的时候会扩展为默认容量大小 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = { }; //存储元素的数组 transient Object[] elementData; // non-private to simplify nested class access// 集合中元素的个数private int size;

(1).add:
添加元素到队尾位置，平均时间复杂度为O(1)

public boolean add(E e) {// 检查是否扩容 ensureCapacityInternal(size + 1); elementData[size++] = e; return true; }private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); }private static int calculateCapacity(Object[] elementData, int minCapacity) {//如果是为才创建的是空数组 if (elementData =https://www.it610.com/article/= DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//返回10与所需大小较大的一个 return Math.max(DEFAULT_CAPACITY, minCapacity); } //否则返回所需大小 return minCapacity; }private void ensureExplicitCapacity(int minCapacity) {modCount++; // 如果所需大小比数组大小更大就扩容 if (minCapacity - elementData.length> 0) grow(minCapacity); //扩容 } private void grow(int minCapacity) {int oldCapacity = elementData.length; //1.5倍扩容 int newCapacity = oldCapacity + (oldCapacity >> 1); // 如果扩容量后发现比需要的容量还小，则返回需要的容量 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // 创建新容量的数组并把老数组拷贝到新数组 elementData = https://www.it610.com/article/Arrays.copyOf(elementData, newCapacity); } private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity> MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }

(2).void add(int index, E element):

public void add(int index, E element) {rangeCheckForAdd(index); //检查index位置是否合理 //是否需要扩容 ensureCapacityInternal(size + 1); // Increments modCount!! // 把插入索引位置后的元素都往后挪一位 System.arraycopy(elementData, index, elementData, index + 1, size - index); // 在插入索引位置放置插入的元素 elementData[index] = element; size++; } private void rangeCheckForAdd(int index) {if (index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }

(3).addAll()：

public boolean addAll(Collection c) { //将集合转化为数组 Object[] a = c.toArray(); int numNew = a.length; //是否扩容 ensureCapacityInternal(size + numNew); // Increments modCount //拷贝到表尾 System.arraycopy(a, 0, elementData, size, numNew); size += numNew; return numNew != 0; }

(4.)get():

//获取指定索引位置的元素： public E get(int index) {rangeCheck(index); return elementData(index); } E elementData(int index) {return (E) elementData[index]; }

(5).E remove(int index):

public E remove(int index) {rangeCheck(index); modCount++; E oldValue = https://www.it610.com/article/elementData(index); //移动元素次数 int numMoved = size - index - 1; if (numMoved> 0)System.arraycopy(elementData, index+1, elementData, index,numMoved); // 将最后一个元素删除，帮助GC elementData[--size] = null; // clear to let GC do its workreturn oldValue; }

(6).boolean remove(Object o)：

//找到第一个等于指定元素值的元素； 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; }private void fastRemove(int index) {modCount++; 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}

4.LinkedList 底层是双向链表，由于既实现了List有实现了Queue，所以可以作为队列或者栈来使用
优点：
不用扩容，增删元素方便
.缺点：
查改元素消耗时间多
【笔记|集合背后的数据结构（一）】慎用get(int index)这个方法，需要遍历链表，虽然get方法优化在前size/2在从头开始遍历，否则从尾开始遍历，但是当元素非常多的时候，遍历的所花的时间是非常多的

推荐阅读

• 

  oracle undo分析 sql,表分析oracle
• 

  运维|nginx error_page
• 

  iPhone11多重 苹果11手机多少克
• 

  想生双胞胎的孕前准备 如何能生双胞胎
• 

  大蒜有点烂可以吃吗
• 

  车身划痕的保养及修复小窍门是什么 车身划痕的保养及修复小窍门
• 

  脸色暗黄可以喝藏红花吗
• 

  初级会计考试考哪些科目，初级会计师考试要考哪几门
• 

  2020年结婚黄道吉日大全 老黄历2020吉日查询
• 

  原棉大豆被是什么意思
• 

  旗木卡卡西忍界大战的奥义是 火影忍者手游12月10日每日一题答案
• 

  用友软件 往来账龄分析表,假设对个人往来账龄分析表的时间
• 

  心狠手辣的司马懿是怎么死的？ 司马懿之死
• 

  详解React中组件之间通信的方式
• 

  注册商标多久可以拿到证书 注册商标证该怎么查真伪，许可证注册商标证号
• 

  雪梨水煮多久才好
• 

  传统玩具有哪些
• 

  明基摄像机不充电维修价格
• 

  合肥有什么酒出名 安徽比较有名的酒
• 

  远程控制别人的电脑怎么做 电脑如何远程控制

• EffectiveObjective-C2.0|EffectiveObjective-C2.0 笔记 - 第二部分
• 图书集合完毕
• Android中的AES加密-下
• 孩子行为背后的秘密（2）胡老师讲座感悟
• 私通和背叛，他怎么看（——晨读小记）
• 漫画初学者如何学习漫画背景的透视画法（这篇教程请收藏好了！）
• 【读书笔记】贝叶斯原理
• 【韩语学习】（韩语随堂笔记整理）
• 人性的弱点-笔记
• 读书笔记:博登海默法理学|读书笔记:博登海默法理学 —— 正义的探索（1）