文章目录

• 一、线性表初步认识
• • 1.常见数据结构
  • 2.线性表
  • 3.数组
• 二、动态数组的设计
• • 1.构造方法的设计
  • 2.返回元素个数 size()
  • 3.判断数组元素是否为空 isEmpty()
  • 4.查看元素索引 indexOf(E element)
  • 5.对下标是否合法的判断
  • 6.判断是否需要扩容的方法 ensureCapacity
  • 7.添加元素的方法 add
  • 8.清除所有元素 clear
  • 9.判断数组是否包含某个元素
  • 10获取某个索引位置的元素 get(int index)
  • 11.修改某个索引位置的元素
  • 12.删除某个位置的元素 remove
  • 13.打印动态数组

一、线性表初步认识

1.常见数据结构

在讲线性表之前，我们要先对数据结构有一定的了解
数据结构是计算机存储、组织数据的形式

常见的数据结构有集合结构、线性结构、树形结构、图形结构

• 线性结构
  • 数组
  • 链表
  • 栈
  • 队列
  • 哈希表(散列表)
• 树形结构
  • 二叉树
  • AVL树
  • 红黑树
  • B树
  • 堆
  • Trie
  • 哈夫曼树
  • 并查集
• 图形结构
  • 邻接矩阵
  • 邻接表

2.线性表

线性表是具有n个相同类型元素的有限序列(n>=0)

3.数组

• 数组是一种顺序存储的线性表，所有元素的内存地址是连续的

数组是申请连续的空间
但是而且一旦申请了空间，那么它的容量就无法改变了，显然不符合我们的要求，我们肯定是希望数组的容量可以根据我们的需求而发生变化，因此，我们可以采取动态数组来解决这种问题

二、动态数组的设计

在设计相关方法之前，我们先来定义相关属性

• size:用来表示动态数组里面的元素个数
• elements：数组
• DEFAULT_CAPACITY :数组默认容量
• ELEMENT_NOT_FOUND:没有找到数组中的元素，就返回这个值
  具体的方法在后文介绍

public class ArrayList<E> {    /     * 元素的数量     */    private int size;    /     * 所有的元素     */    private E[] elements;    private static final int DEFAULT_CAPACITY = 10;    private static final int ELEMENT_NOT_FOUND = -1; }

1.构造方法的设计

• capacity代表的是我们想要给动态数组多少容量
• 默认容量为10
• 如果我们给的容量小于默认容量，那么数组的容量就是默认容量
• 如果我们给的容量大默认容量，那么数组的容量就是我们给的容量

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

2.返回元素个数 size()

 /     * 元素的数量     * @return     */    public int size() { return size;    }

3.判断数组元素是否为空 isEmpty()

• 数组元素个数为0就代表数组为空

  /     * 判断是否为空     */    public boolean isEmpty() { return size == 0;    }

4.查看元素索引 indexOf(E element)

• 我们可以遍历动态数组，然后把查找的元素和数组里面的元素一一比较
  • 因为数组可以存储任何类型的值，所以可能存储的是对象，我们可以用equals方法来比较
  • 要先判断查找的元素是否为空，因为如果值为空，调用equals方法会出现空指针异常，如果element为空，就使用==
  • 如果不为空，使用equals方法来比较

    /运行存储null     * 查看元素的索引     * @param element     * @return     */    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;    }

5.对下标是否合法的判断

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

6.判断是否需要扩容的方法 ensureCapacity

• 如果原来的数组容量>=size+1,则不需要扩容
• 否则需要扩容
• 这个方法主要是为后面添加元素服务的

 /     * 确保有足够容量     */    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);    } 

7.添加元素的方法 add

• 在指定位置添加元素
• 添加元素时，先判断索引是否合法
• 然后判断是否需要扩容
• 然后再进行添加元素
• 记得size要加1

 /     * 在index位置插入一个元素     * @param index     * @param element     */    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++;    }

• 在数组末尾添加元素

 /     * 添加元素到尾部     * @param element     */    public void add(E element) { add(size, element);    }

8.清除所有元素 clear

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

9.判断数组是否包含某个元素

• 因为前面已经有了查看元素索引的方法
• 如果没有这个元素，返回的是ELEMENT_NOT_FOUND
• 我们只需要调用indexOf方法就可以进行判断了

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

10获取某个索引位置的元素 get(int index)

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

11.修改某个索引位置的元素

最后返回修改前的元素值

 public E set(int index, E element) { rangeCheck(index); E old = elements[index]; elements[index] = element; return old;    }

12.删除某个位置的元素 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;    }

13.打印动态数组

    @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();    }}