目录

1.线性表

2.接口涉及

3.简单接口的实现

4.clear

5.add

6.打印

7.remove

8.add_index

9.接口测试

10.动态扩容

11.泛型

12.对象数组

13.clear_细节

14.remove_细节

15.equals

16.null值处理

17.ArrayList源码分析

1.线性表

• 什么是数据结构？
•  线型表示具有n个相同类型元素的有限序列（n>=0）
•  生活之中的线型表

2.接口涉及

• 第一种线型表：数组这里的array是存放在相应的栈空间之中，new出来的数据是存放在相应的堆空间之中，并且new出来的内存地址是连续的。数组存在一个严重缺点，无法进行动态的申请相应的容量（改变这个方式，可以进行自己写一个动态数据）。
• 动态数组的接口设计
•  初始代码块的设计，这里是设计的相应的ArrayList。

  public class ArrayList {
  
      
      public void clear() {
  
      }
  
      
      public int size() {
          return 0;
      }
  
      
      public boolean isEmpty() {
          return false;
      }
  
      
      public boolean contains(int element) {
          return false;
      }
  
      
      public void add(int element) {
  
      }
  
      
      public int get(int index) {
         return 0;
      }
  
      
      public int set(int index,int element) {
          return 0;
      }
  
      
      public void add(int index, int element) {
  
      }
  
      
      public int remove(int index) {
          return 0;
      }
  
      
      public int indexOf(int element) {
  
          return -1;
      }
  
  }
  

3.简单接口的实现

• 动态数组的设计

public class ArrayList {
    private int size;//元素数量
    private int[] elements;//存放数组

    private static final int DEFAULT_CAPACITY = 10;//默认是相应的为10的存储空间
    private static final int ELEMENT_NOT_FOUND = -1;//这里是进行一个return的声明

    //提供容量的一个相应的数组
    public ArrayList(int capacity)
    {
        capacity = (capacity < DEFAULT_CAPACITY)? DEFAULT_CAPACITY:capacity;
        elements = new int[capacity];
    }

    
    //上面的相应的构造函数还可以进行下面的写法
    public ArrayList()
    {
        this(DEFAULT_CAPACITY);//直接是使用相应的无参构造函数调用相应的有参构造函数
    }
    
    public void clear() {

    }

    
    public int size() {
        return 0;
    }

    
    public boolean isEmpty() {
        return size == 0;
    }

    
    public boolean contains(int element) {
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }

    
    public void add(int element) {

    }

    
    public int get(int index) {
        if(index < 0 || index >= size)
        {
            throw new IndexOutOfBoundsException("Index:" + index + ",Size:" + size);//这里是直接使用抛出异常的方式进行相应的处理
            //抛出异常的情况就是相应的颜色编程红色
            
        }
       return elements[index];
    }

    
    public int set(int index,int element) {
        if(index < 0 || index >= size)
        {
            throw new IndexOutOfBoundsException("Index:" + index + ",Size:" + size);//这里是直接使用抛出异常的方式进行相应的处理
            //抛出异常的情况就是相应的颜色编程红色
            
        }
        int old = elements[index];
        elements[index] = element;
        return old;
    }

    
    public void add(int index, int element) {

    }

    
    public int remove(int index) {
        return 0;
    }

    
    public int indexOf(int element) {
        //这个含义就是进行相应的遍历的过程
        for(int i= 0; i 
4.clear 
 public void clear() {
       
        size = 0;//只要控制相应的size的大小就是可以控制相应的异常的抛出
        

    }
 
 
斐波那契数的另一种写法
 
public static int fib3(int n)
	{
		if(n <= 1) return n;
		int first = 0;
		int second = 1;
		for(int i= 0;i < n-1; i++)//或者这里的条件是进行相应的while（n-- > 1）,这里的含义就是进行相应的n-1的一个执行过程
		{
			second += first;
			first = second - first;
		}
		return second;
	}
 
斐波那契数的另一种写法
 一个数组new出来之后，一般而言，new出来一个对象就是进行相对空间进行一个申请空间的过程。一般而言，在后面我们是要进行一个delete的一个过程，但是在相应的java之中，是不需要这个过程的，直接存在一个垃圾回收的过程。
5.add 
    
    public void add(int element) {
        elements[size++] = element;
        
    }
 
6.打印 
这里System.out.println（）方法是直接进行调用相应的toString的方式进行打印，我们希望将立面的元素进行打印出来，这里的调用方式是如下所示：
 @Override
    public String toString() {
        //size = 3，[99,88,77]
        StringBuilder string = new StringBuilder();//这里的StringBuilder是需要转换成为相应的String格式
        string.append("size=").append(size).append(",[");
        for (int i = 0; i< size;i++ )
        {


         
            if (i!=0)//选择这种方式的原因是他不进行相应的减法运算
            {
                string.append(",");
            }
            string.append(elements[i]);
        }

        string.append("]");

        return string.toString();
    }
 
流程 
 
7.remove 
删除操作进行的时候，需要注意最后一个元素的过程使用。
最后一个元素是不需要进行处理的，防止后面是需要进行使用的。并且上面的字节是连续的，因此，使用的过程之中只能是进行相应的元素挪动的过程。
 
 比如我们这里是需要进行挪动的是index为3，那么相应的一个挪动范围是index+1 - size-1
 
具体的挪动的代码是如下所示： 
    public int remove(int index) {
        //首先是对于相应的index进行判断
        if(index<0 || index>=size){
            throw new IndexOutOfBoundsException("Index超出了范围");
        }
        
        //记录原始的old元素是什么
        int old = elements[index];
        
        //进行相应的一个挪动过程使用
        for(int i = index+1;i 
8.add_index 
注意挪动的时候，首先进行挪动的是最后面的先进行挪动，注意顺序问题。
 这里的使用过程是如下所示：
 
    public void add(int index, int element) {
        //首先是需要进行相应的index的判断.这里的索引的判断是需要进行相应的注意的,是与别的判断是不同的.
        //这里的index可以是等于相应的size的大小的.
        if(index < 0 || index > size)
        {
            throw new IndexOutOfBoundsException("Index:" + index + ",Size:" + size);//这里是直接使用抛出异常的方式进行相应的处理
            //抛出异常的情况就是相应的颜色编程红色
            
        }

        //挪动的范围 从相应的index - size-1,一定要注意相应的顺序.
        for(int i = size-1;i >= index;i--)
        {
            elements[i+1] = elements[i];
        }
        elements[index] = element;
        size++;


    }
 
 
接下来是进行相应的一个封装异常的过程使用，将上述异常出现的情况直接进行了相应的封装，免去了相应的处理的过程使用。
 
    private void outOfBounds(int index)
    {
        throw new IndexOutOfBoundsException("Index:" + index + ",Size" + size);
    }
    private void rangeCheck(int index)
    {
        if(index < 0 || index >= size)
        {
            outOfBounds( index);
        }
        
    }
    private void rangeCheckForAdd(int index)
    {
        if(index < 0 || index > size)
        {
            outOfBounds( index);
        }
    }
    
 
 
将相应的add方法进行相应的修改
 
    
    public void add(int element) {
       // elements[size++] = element;
        
        add(size,element);
    }
 
9.接口测试 
在开发之中，我们会遇到各种的测试，一般是采用打印的方式。另一种方式是进行抛出异常的方式进行。
使用声明一个Asserts工具方式，相应的代码段是如下所示： 
public class Asserts {
	public static void test(boolean value) {
		try {
			if (!value) throw new Exception("测试未通过");
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}
 
测试的主函数如下所示：
 
10.动态扩容 
进行扩容的方式，如下所示：这里是不可以new一个新的数组在后面接着使用，原因是因为new出来的内存空间是随机的吧，不能够保证内存是在它后面的，只能是新申请一个空间。原来的内存空间是没有使用的，需要将原来的内存空间自动进行垃圾回收。
创建一个新的方法,是进行扩容的方法. 
 
    public void ensureCapacity(int capacity)
    {
        int oldCapacity = elements.length;
        if(oldCapacity >= capacity) return;
        
        int newCapacity = oldCapacity + (oldCapacity>>1); //这里的含义是原始的容量变成原来的1.5倍
        int[] newElements = new int[newCapacity];//新声明一个数组
        for(int i = 0 ;i 
原始的函数之中需要进行改变.
11.泛型 
我们在使用的过程之中,希望可以放入一些别的类型的.这里我们应当注意的是,泛型只能是放入相应的一个对象类型的,不能够放入基本数据类型,比如就是说:如果要是放入相应的int类型就是需要进行更改为Integer(包装类).
在使用泛型编写的过程之中,发现出现了这个问题.如下所示 
 我们知道，所有类型的父类都是Object类型，但是Object类型是不可以进行继承自己的。因此，我们这里使用一个强制类型转换方式进行。如下所示：
 此刻的ArrayList是如下所示: 
import com.sun.java.swing.plaf.windows.WindowsDesktopIconUI;

import java.net.BindException;
import java.util.Arrays;
public class ArrayList {
    
    private int size;
    
    private E[] elements;

    private static final int DEFAULT_CAPACITY = 10;
    private static final int ELEMENT_NOT_FOUND = -1;

    public ArrayList(int capaticy) {
        capaticy = (capaticy < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capaticy;
        elements = (E[]) new java.lang.Object[capaticy];
    }

    public ArrayList() {
        this(DEFAULT_CAPACITY);
    }

    
    public void clear() {
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        size = 0;
    }

    
    public int size() {
        return size;
    }

    
    public boolean isEmpty() {
        return size == 0;
    }

    
    public boolean contains(E element) {
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }

    
    public void add(E element) {
        add(size, element);
    }

    
    public E get(int index) {
        rangeCheck(index);
        return elements[index];
    }

    
    public E set(int index, E element) {
        rangeCheck(index);

        E old = elements[index];
        elements[index] = element;
        return old;
    }

    
    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++;
    }

    
    public E remove(int index) {
        rangeCheck(index);

        E old = elements[index];
        for (int i = index + 1; i < size; i++) {
            elements[i - 1] = elements[i];
        }
        elements[--size] = null;
        return old;
    }

    
    public int indexOf(E element) {
        if (element == null) {  // 1
            for (int i = 0; i < size; i++) {
                if (elements[i] == null) return i;
            }
        } else {
            for (int i = 0; i < size; i++) {
                if (element.equals(elements[i])) return i; // n
            }
        }
        return ELEMENT_NOT_FOUND;
    }

//	public int indexOf2(E element) {
//		for (int i = 0; i < size; i++) {
//			if (valEquals(element, elements[i])) return i; // 2n
//		}
//		return ELEMENT_NOT_FOUND;
//	}
//
//	private boolean valEquals(Object v1, Object v2) {
//		return v1 == null ? v2 == null : v1.equals(v2);
//	}

    
    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        if (oldCapacity >= capacity) return;

        // 新容量为旧容量的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        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("Index:" + index + ", Size:" + size);
    }

    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() {
        // size=3, [99, 88, 77]
        StringBuilder string = new StringBuilder();
        string.append("size=").append(size).append(", [");
        for (int i = 0; i < size; i++) {
            if (i != 0) {
                string.append(", ");
            }

            string.append(elements[i]);

//			if (i != size - 1) {
//				string.append(", ");
//			}
        }
        string.append("]");
        return string.toString();
    }
}
 
 
12.对象数组 
上面代码进行更改之后,出现一个内存管理.为什么要放入地址,因为如果要是放入的是相应的值的话,会产生一系列的问题,对象的大小是不确定的,放入空间会由对象的大小决定,会产生一定的问题.
主函数的测试代码图如下所示:
13.clear_细节 
对象的销毁过程,如上图所示,将地址位置变成null,就是进行一个断线的过程,数组的内存和对象的内存是不一样的.
这里的clear为什么要进行调整的过程,之前为什么不进行调整,以前的时候直接将size变成0,原来的内存是可能使用的.这里的意思就是clear使用过之后,后面还是会进行add的过程.  而 本处如果要是使用对于对象的地址值时,是将原来的地址值进行一个覆盖的过程,然后将原来的对象进行清空.拿下面的代码进行讲解:
clear方法是如下所示: 
   
    public void clear() {
        
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        size = 0;
    }
 
如何证明最终的Person对象是挂了的???在Person代码之中添加如下所示,就是当地址指针不再指向Person对象的时候,调用如下的析构函数,说明对象挂了. 
    @Override
    protected void finalize() throws Throwable {
        super.finalize();
        System.out.println("Person对象挂了");
    }
 
我们发现在使用clear之后,并没有出现垃圾回收,因此,在clear之后可以使用一个提醒机制.相应的代码是如下所示:System.gc();//这里的含义就是对于垃圾回收之后,直接调用上面所谓的"对象挂了"的函数.
 
14.remove_细节 
处理的过程中,将此处的地址值进行删除,后面的地址值依次向前移动.最后的地址值设置为null.
remove对应的代码是如下所示:
    
    public E remove(int index) {
        rangeCheck(index);

        E old = elements[index];
        for (int i = index + 1; i < size; i++) {
            elements[i - 1] = elements[i];
        }
        elements[--size] = null;
        return old;
    }
 
15.equals 
在原始的Person之中添加重写equals方法,相应的代码是如下所示: 
 @Override//使用重写的方式进行equals方式的实现,一般对于对象是不进行地址的比较的,都是使用对象之中相应的属性进行比较,如果要是元素之中的两个元素是一样的就是可以判断是一致的.
    public boolean equals(Object o) {
     Person person = (Person)o;
     return this.age == person.age;
    }
 
如果要是不进行重写equals方法就是直接进行使用地址比较的方式.如果不是对象是Integer,相当于重写equals,内部直接进行比较相应的数值是否相等,并不是进行地址的比较.
 
 
IndexOf()方式代码是如下所示:
 
    
    public int indexOf(E element) {
   
        
            for (int i = 0; i < size; i++) {
                if (element.equals(elements[i])) return i; // n
            
        }
        return ELEMENT_NOT_FOUND;
    }
 
16.null值处理 
如果null值是可以存的,add代码是不用进行改正的.如果要是不能够存取空null值,这里在add方法之中就是需要进行一个添加操作. 
 
        添加上面所示这一句就是可以的. 
 
如果传入对象是null的,直接查询第一个null的位置.因此,Index函数是需要进行分开处理的. 
  
    public int indexOf(E element) {
        if (element == null) {  // 1
            for (int i = 0; i < size; i++) {
                if (elements[i] == null) return i;
            }
        } else {
            for (int i = 0; i < size; i++) {
                if (element.equals(elements[i])) return i; // n
            }
        }
        return ELEMENT_NOT_FOUND;
    }
 
17.ArrayList源码分析 
直接在IDEA页面上敲击java.util.ArrayList点击进入源码之中进行查看.代码之中modCount是在迭代器之中才是有用的,在一般的过程之中是没有那么大的作用.
== 是进行比较的是内存地址是否相等,一般我们是使用equals进行重写复用的方式进行.
重写的改写 
    @Override//使用重写的方式进行equals方式的实现,一般对于对象是不进行地址的比较的,都是使用对象之中相应的属性进行比较,如果要是元素之中的两个元素是一样的就是可以判断是一致的.
    public boolean equals(Object o) {
        if (o == null) return false;
        if (o instanceof Person) {
            Person person = (Person) o;
            return this.age == person.age;
        }
        return false;//这里是比较的两种类型是不同的.

    }