引入:
数据结构的分类，数据结构可以分成：线性表，树形结构，图形结构。
-
线性结构(线性表)包括:数组、链表、栈队列
-
树形结构:二叉树、AVL树、红黑树、B树、堆、Trie、哈夫曼树、并查集
-
图形结构:邻接矩阵、邻接表
线性表是具有存储n个元素的线性序列，常见的线性表有顺序表(数组)和链表两种实现方式。
为什么会出现ArrayList动态数组？
- 在很多开发语言中数组有一个致命的缺点，就是数组的长度一旦确定，就不能再更改。
- 我们在实际的开发中，更希望数组是可变的。
这个时候我们就可以使用数组去封装一个动态数组，java中的ArrayList的出现就是为了弥补数组长度不可变的缺点。
ArrayList的实现：
我们要对数组进行封装，也就是让这个数组如果元素装满了之后，重新创建一个更大的数组，将原来的元素复制过去。
分析:
实现动态数组，我们要创建一个类叫做ArrayList,因为他能存储所有引用类型的元素，我们要给它加一个泛型/，它要能动态获取它存储的元素的数量，所以它可以得到它应该有一个size成员，既然是一个动态数组，它的类成员一定有一个容器数组elements。这样我们就可以确定两个成员size和elements;
这个动态数组需要创建，所以我们得提供构造方法，既然它底层还是数组，那么创建的时候还是需要指定大小，可以自定义也可以创建一个默认大小的数组。java底层默认创建的是一个大小为10的数组。
package com.lut.dynamicArray;
public class ArrayList<E> {
//所装元素的数量
public int size;
//数组
private E[] elements;
//创建ArrayList底层数组默认的大小
private static final int DEFAULT_CAPACITY = 10;
//构造方法，自定义初始的ArrayList的大小，和java.util.ArrayList实现有所不同，可以自己进源码查看
public ArrayList(int capacity){
capacity = (capacity < DEFAULT_CAPACITY)?DEFAULT_CAPACITY:capacity;
elements = (E[]) new Object[capacity];
}
public ArrayList(){
//elements=new int[DEFAULT_CAPACITY];
this(DEFAULT_CAPACITY);
}
}
接口(方法)分析：
这个类已经创建出来了，我们就需要向外界提供操作这个动态数组的方法。比如必须能够向这个ArrayList的对象里面添加元素、删除元素、按索引查找元素、按元素查索引、获取这个对象里面存储的元素个数等可以操作的方法。
它至少包括以下方法:
int size();// 元素的数量
boolean isEmpty(); // 是否为空
boolean contains(E element);// 是否包含某个元素
void add(E element);// 添加元素到最后面
E get(int index);/返回index位置对应的元素
E set(int index, E element);//设置index位置的元素
void add(int index, E element);//往index位置添加元素
E remove(int index);// 删除index位置对应的元素
int index0f(E element);// 查看元素的位置
void clear();// 清除所有元素
需要注意的是，我们需要通过add方法不断地向ArrayList的对象里面添加元素，如果元素操作了我们创建ArrayList指定的大小，这个时候就需要扩容，所以我们在添加元素之前，需要调用ensureCapacity方法（这个方法只是为了方便理解，官方方法写的很复杂，名字也不叫ensureCapacity，不够调用的时机和位置一样），确保下一个元素不会索引越界，如果越界就需要进行扩容处理，扩容是直接在原数组的大小基础上扩大1.5倍。
我们在查找元素的时候或者是按索引添加元素的时候可能存在索引大于了ArrayList的默认的size或者为负数等不合理的输入，这个时候我们需要在这些方法前面调用一个rangeCheck(index)函数，确保传入的索引合适，而添加的时候索引可以比size大1，所以单独定义了一个rangeCheckForAdd(index),如果rangeCheck或者rangeCheckForAdd方法在检查索引发现不合适的时候就会调用outOfBounds方法。
下面是自定义低配版ArrayList的简单实现
private void ensureCapacity(int capacity) {
int oldCapacity = elements.length;
if(oldCapacity>=capacity) return;
//新容量为旧容量的1.5倍
int newCapacity = oldCapacity+(oldCapacity >> 1);
//位运算右移1除以2，相当于旧容量1.5倍，相反左移1相当于乘以2
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i]=elements[i];
}
elements=newElements;
System.out.println(oldCapacity+"扩容为:"+newCapacity);
}
下面对ArrayList进行了简单的实现
package com.lut.dynamicArray;
@SuppressWarnings("unchecked")
public class ArrayList<E> {
//元素的数量
public int size;
//所有的元素
private E[] elements;
//static能保证内存中只有一份此数据
private static final int DEFAULT_CAPACITY = 10;
//元素是否找到
private static final int ELEMENT_NOT_FOUND = -1;
public ArrayList(int capacity){
capacity = (capacity < DEFAULT_CAPACITY)?DEFAULT_CAPACITY:capacity;
elements = (E[]) new Object[capacity];//释放时机和外面的ArrayList同时释放
}
public ArrayList(){
this(DEFAULT_CAPACITY);
}
/**
* 清楚所有元素
*/
public void clear(){
for (int i = 0; i < size; i++) {
elements[i] = null;
}
size = 0;
}
/**
* 元素的数量
* @return
*/
public int size(){
return size;
}
/**
* 是否为空
* @return
*/
public boolean isEmpty(){
return size==0;
}
/**
* 是否包含某个元素
* @param element
* @return
*/
public boolean contains(E element){
return indexOf(element) != ELEMENT_NOT_FOUND;
}
/**
* 添加到元素尾部
*/
public void add(E element){
add(size,element);
}
/**
* 获取index位置的元素
*/
public E get(int index){
rangeCheck(index);
return elements[index];
}
/**
* 设置index位置的元素
* @return 原来的元素
*/
public E set(int index,E element){
rangeCheck(index);
E old = elements[index];
elements[index] = element;
return old;
}
/**
* 在index位置插入一个元素
*/
public void add(int index,E element){
rangeCheckForAdd(index);
ensureCapacity(size+1);
for (int i = size; i >index; i--) {
elements[i]=elements[i-1];
}
elements[index]=element;
size++;
}
/**
* 删除index位置的元素
* @return 返回删除的元素
*/
public E remove(int index){
rangeCheck(index);
E temp = elements[index];
for (int i = index+1; i < size; i++) {
elements[i-1]=elements[i];
}
//size--;
elements[--size] = null;
return temp;
}
/**
* 查看元素的索引，没找到返回-1
*/
public int indexOf(E element){
if(element == null){
for (int i = 0; i < size; i++) {
if(elements[i] == null) return i;
}
}else {
for (int i = 0; i < size; i++) {
//未重写的equals方法，就是默认比较的两个对象的地址
if(element.equals(elements[i])) return i;
}
}
return ELEMENT_NOT_FOUND;
}
/**
* 保证要有capacity的容量
* @param capacity
*/
private void ensureCapacity(int capacity) {
int oldCapacity = elements.length;
if(oldCapacity>=capacity) return;
//新容量为旧容量的1.5倍
int newCapacity = oldCapacity+(oldCapacity >> 1);
//位运算右移1除以2，相当于旧容量1.5倍，相反左移1相当于乘以2
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i]=elements[i];
}
elements=newElements;
System.out.println(oldCapacity+"扩容为:"+newCapacity);
}
private void outOfBounds(int index){
throw new IndexOutOfBoundsException();
}
private void rangeCheck(int index){
if(index<0||index>=size){
outOfBounds(index);
}
}
private void rangeCheckForAdd(int index){
if(index<0||index>size){
outOfBounds(index);
}
}
@Override
public String toString() {
StringBuilder string = new StringBuilder();
string.append("size=").append(size).append(",[");
for (int i = 0; i < size;java i++) {
if(i!=0){
string.append(",");
}
string.append(elements[i]);
}
string.append("]");
return string.toString();
}
}
仔细阅读上面的代码我们可以发现ArrayList有以下缺点:
- 固定大小：ArrayList的大小是固定的，一旦初始化后，无法动态调整大小，如果需要动态增加或减少元素，就需要创建一个新的数组elements，并将元素复制过去，这样会增加额外的开销。
- 性能问题：在插入或删除元素时，ArrayList的elements数组需要移动其他元素来保持连续性，这会导致性能下降，尤其是在大型数据集上。
- 内存占用：ArrayList在内存使用上比较消耗，因为它需要额外的空间来存储元素的索引和容量信息。
那么有没有和ArrayList一样的数据结构能够方便元素的插入删除，同时能够灵活的利用内存空间呢？有,LinkedList
LinkedList实现
分析:
LinkedList也是一个动态的线性表，所以它就必须能够存储元素，能够获取大小，ArrayList底层是通过一个数组存储元素，LinkedList内部是通过一个结点类来存储元素，同时这个Node里面有两个指针,prev指向前一个结点、next指向下一个结点，同时提供一个构造方法，当我们需要添加一个元素的时候本质是添加一个结点，再把这个元素放入到这个结点内部，同时维护好这个结点的前后结点。
所以LinkedList需要两个成员至少size和一个内部类Node
Node:
private static class Node<E> {
E element;
Node<E> prev;
Node<E> next;
public Node(Node<E> prev, E element, Node<E> next) {
this.prev = prev;
this.element = element;
this.next = next;
}
}
为了方便获取头节点，我们还需要指定一个头结点，我们需要一个成员变量Node类型的first
package com.lut.list;
public class LinkedList<E>{
private Node<E> first;
private int size;
private static class Node<E> {
E element;
Node<E> prev;
Node<E> next;
public Node(Node<E> prev, E element, Node<E> next) {
this.prev = prev;
this.element = element;
this.next = next;
}
}
}
ArrayList和LinkedList我们经常使用，ArrayList又叫做动态数组底层是由数组实现的，LinkedList底层是基于链表实现的集合，它们都是线性的数据结构。
既然ArrayList和LinkedList都具有相同的方法，我们就可以把这些相同的方法给提取出来成为一个单独的接口，这个接口就是List接口。
public interface List<E> {
//如果元素未找到返回-1
static final int ELEMENT_NOT_FOUND = -1;
//清除所有元素
void clear();
//元素的数量
int size();
// 是否为空
boolean isEmpty();
//是否包含某个元素
boolean contains(E element);
//添加元素到尾部
void add(E element);
//获取index位置的元素
E get(int index);
//获取index位置的元素
E set(int index, E element);
//在index位置插入一个元素
void add(int index, E element);
//删除index位置的元素
E remove(int index);
//查看元素的索引
int indexOf(E element);
}
所以我们只需要去LinkedList去实现这些接口就可以了，然后对于LinkedList里面还有一些和ArrayList连实现都一样的方法，我们就可以单独写一个AbstractList/抽象类来复用相同的方法。
public abstract class AbstractList<E> {
/**
* 元素的数量
*/
protected int size;
/**
* 元素的数量
* @return
*/
public int size() {
return size;
}
/**
* 是否为空
* @return
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 是否包含某个元素
* @param element
* @return
*/
public boolean contains(E element) {
return indexOf(element) != ELEMENT_NOT_FOUND;
}
/**
* 添加元素到尾部
* @param element
*/
public void add(E element) {
add(size, element);
}
protected void outOfBounds(int index) {
throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}
protected void rangeCheck(int index) {
if (index < 0 || index >= size) {
outOfBounds(index);
}
}
java
protected void rangeCheckForAdd(int index) {
if (index < 0 || index > size) {
outOfBounds(index);
}
}
}
现在我们就可以直接实现专注实现List里面的不同的方法了。
需要注意理解里面的add方法，添加的时候，无论是调用add(E element)还是add(int index,E element),我们调用的add(E element)方法均会成为调用add(int index,E element)方法，原因是 public void add(E element) {add(size, element);}。
还需要注意，如果我们第一次添加的时候，需要把first指向它
下面是LinkedList的简单实现:
package com.lut.list;
public class LinkedList<E> extends AbstractList<E> implements List<E>{
private Node<E> first;
private static class Node<E>{
E element;
Node<E> next;
public Node(E element, Node<E> next) {
this.element = element;
this.next = next;
}
}
@Override
public void clear() {
size = 0;
first = null;
}
@Override
public E get(int index) {
return node(index).element;
}
//复杂度跟node方法有关，它的复杂度为O(n)
@Override
public E set(int index, E element) {
Node<E> node = node(index);
E old = node.element;
node.element = element;
return old;
}
//O(n)
@Override
public void add(int index, E element) {
if(index == 0){
first = new Node<>(element,first);
}else{
Node<E> prev = node(index - 1);
prev.next = new Node