数据结构之数组

数组

0.简介

数组是一种线性表数据结构，它用一组连续的内存空间，来存储一组具有相同类型的数据。

线性表：零个或者多个元素构成的有限序列。每个线性表的数据只存在于前后两个方向。除数组外还有链表，栈，队列都是线性表结构。

说到数组是利用连续的存储空间，这个性质既有优势也有劣势。

• 优势：在进行数组的随机访问时我们只需要知道索引就能相应的访问到该索引的数据，十分高效。
• 劣势：在进行数据的添加和删除时，由于数组是由连续的存储空间构成的，故而添加和删除时需要进行大规模的数据搬移工作。

1.数组基础

• 用来存储一类类型相同的数据。

• 在内存中是连续的空间，创建数组时要指定数组长度。

• 数据类型 [] 数组名

  int arr = new int[10];
  int arr = {1,2,3,4};
  1
  2

• 访问数组时通过索引进行操作（索引由0开始道arr.length()-1结束）。

• 常见的错误有NullPointException（空指针异常） ArrayIndexOutOfBoundsException（非法索引）

2.数组的操作

我们基于java中的数组进行二次封装，实现自己的数组（可变数组）

• 数组的初始化及基础方法

  public class MySelfArray<T> {
  	private T[] data;//数组
  	private int size;//数组实际存放长度
  	private int capacity;//指定数组容积
  
  	//构造函数
      //无参构造
  	public MySelfArray() {
  		this(100);
  	}
      //有参构造
  	public MySelfArray(int capacity) {
  		this.data = (T[]) new Object[capacity];
  		this.size = 0;
  		this.capacity = capacity;
  	}
  
  	//获取数组实际存放的元素的长度
      public int getSize(){
  	    return this.size;
      }
      //获取数组的容量
      public int getCapacity(){
  	    return this.capacity;
      }
      //判断数组是否为空
      public boolean isEmpty(){
  	    return this.size==0;
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30

• 添加元素（add）

  	//任意位置插入元素
  	public void add(int index, T value) {
  		if (index < 0 || index > this.size) {
  			throw new IllegalArgumentException("the index is Invalid");
  		}
  		//扩容
  		if (this.size == this.data.length) {
  			resize(this.capacity * 2);
  		}
  		//先后移再添加
  		for (int i = this.size; i > index; i--) {
  			this.data[i] = this.data[i - 1];
  		}
  //        for(int i=index;i
  //            this.data[i]=this.data[i+1];
  //        }
  		this.data[index] = value;
  		this.size++;
  	}
  
  	//尾插法
  	public void addTail(T value) {
  		this.add(this.size, value);
  	}
  
  	//头插法
  	public void addHead(T value) {
  		this.add(0, value);
  	}
  
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30

• 扩容（当数组中已占用的长度+将要添加的元素>=数组的容量）

  • ArrayList默认初始化容量是10，当超出容量时进行1.5倍的扩容。

  	//数组扩容
  	public void resize(int newCapacity) {
  		T[] newArr = (T[]) new Object[newCapacity];
  		//将就数组中的元素写入新数组
  		for (int i = 0; i < this.size; i++) {
  			newArr[i] = this.data[i];
  		}
  		this.data = newArr;
  		this.capacity = newCapacity;
  	}
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10

• 获取指定位置的元素；修改指定位置的元素为value；判断是否包含某元素

  	public T getEleByIndex(int index) {
  		if (index < 0 || index >= this.size) {
  			throw new IllegalArgumentException("the index is invail");
  		}
  		return this.data[index];
  	}
  //修改指定位置元素为value
  	public void setEleByIndex(int index, T value) {
  		if (index < 0 || index >= this.size) {
  			throw new IllegalArgumentException("the index is invail");
  		}
  		this.data[index] = value;
  	}
  
  	//判断是否包含某元素
  	public int contains(T value) {
  		for (int i = 0; i < this.size; i++) {
  			if (this.data[i].equals(value)) {
  				return i;
  			}
  		}
  		return -1;
  	}
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23

• 删除操作

  	public void removeEle(T value) {
  		int index = this.contains(value);
  		if (index != -1) {
  			for (int i = index; i < this.size - 1; i++) {
  				this.data[i] = this.data[i + 1];
  			}
  			this.size -= 1;
  		} else {
  			System.out.println("该数组不包含" + value + "!!");
  		}
  		//缩容
  		if (this.size <= this.capacity / 4 && this.capacity / 2 > 0) {
  			resize(this.capacity / 2);
  		}
  	}
  
  	public T removeFirst() {
  		if (this.isEmpty()) {
  			return null;
  		}
  		T result = this.data[0];
  		for (int i = 1; i < this.size; i++) {
  			this.data[i - 1] = this.data[i];
  		}
  		this.size--;
  		if (this.size == this.capacity / 4 && this.capacity / 2 > 1) {
  			resize(this.capacity / 2);
  		}
  		return result;
  	}
  
  	public T removeLast() {
  		if (this.isEmpty()) {
  			return null;
  		}
  		T result = this.data[size - 1];
  		this.size--;
  		return result;
  	}
  
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40