搜云库技术团队
1.数组基础
数组最一种存放数据的线性数据结构 ，最原始的数组是一种静态数组，需要声明数组的容量，一旦new出来数组对象大小不可改变，可以通过索引来进行数据的增删改查。我们可以通过对静态数组的二次封装来进行改进成动态数组。
- 数组最大的优点：快速查询。
- 数组最好用于“索引有语意”的情况。
- 但并非所有有有语意的索引都适用于数组。 例如当用数组存放人员时，用身份证号来充当索引，此时能够区别人员，但身份证号太长，极大浪费内存空间得不偿失。
- 数组也可以处理索引没有语意的情况。
2.手写基于静态数组的动态数组链表（可对比与java中的ArrayList）
package com.tc.javabase.datastructure.array;
import java.util.Arrays;
/**
* @Classname ArrayList
* @Description 动态列表 对静态数组的二次封装
*
* 时间复杂度分析：
* 增加一个元素
* 在数组的首位增加一个元素 O(n)
* 在数组的末尾增加一个元素 O(1)
* 在指定位置的下标增加一个元素 O(n)
*
* 查询元素
* 查询首位元素 O(1)
* 查询末尾元素 O(1)
* 查询指定下标元素 O(1)
* 是否包含该元素 O(n)
* 查询元素的下标 O(n)
*
* 删除一个元素
* 删除头元素 O(n)
* 删除尾元素 O(1)
* 删除指定下标元素 O(n)
*
* 更新一个元素
* 更新头元素 O(1)
* 更新尾元素 O(1)
* 更新指定元素 O(1)
*
* 综上所述：
* 增：O(n) addLast(): O(1)
* 删：O(n) removeLast(): O(1)
* 改：知道索引: O(1) 不知道索引: O(n)
* 查: 知道索引: O(1) 不知道索引: O(n)
*
* 所以用动态列表这种数据结构 最好用于索引有语义的情况，适合做查询和更新操作（在知道索引的情况下）
* 时间复杂度均为O(1).
*
* @Date 2020/7/15 19:53
* @Created by zhangtianci
*/
public class ArrayList<E> {
private E[] data;
private int size;
/**
* 默认构造函数
* 初始数组容量为8
*/
public ArrayList() {
this.data = (E[]) new Object[8];
this.size = 0;
}
public ArrayList(int capacity) {
this.data = (E[]) new Object[capacity];
this.size = 0;
}
public ArrayList(E[] arr){
data = (E[])new Object[arr.length];
for(int i = 0 ; i < arr.length ; i ++)
data[i] = arr[i];
size = arr.length;
}
/**
* 增加一个元素
* 在数组的首位增加一个元素
* 在数组的末尾增加一个元素
* 在指定位置的下标增加一个元素
*/
/**
* 在数组的首位增加一个元素
*
* 时间复杂度:O(n)
*/
public void addFirst(E e) {
add(0, e);
}
/**
* 在数组的末尾增加一个元素
*
* 时间复杂度:O(1)
*/
public void addLast(E e) {
//考虑边界情况
//当数组已经装满时
// if (size == getArrayLength()){
// throw new IllegalArgumentException("数组已经装满，不能够继续添加元素！");
// }
//
// array[size] = e;
// size++;
//复用方法add(int index,int e)
add(size, e);
}
/**
* 在指定位置的下标增加一个元素
*
*
* 时间复杂度:O(n)
* @param index
* @param e
*/
public void add(int index, E e) {
//考虑边界情况
//1.当数组已经装满时
// if (size == getArrayLength()){
// throw new IllegalArgumentException("数组已经装满，不能够继续添加元素！");
// }
//2.指定的下标不合法 index < 0 || index >= getArrayLength() || index > size
if (index < 0 || index > size) {
throw new IllegalArgumentException("指定下标不合法!");
}
// 扩容
if (size == getCapacity()) {
resize(data.length * 2);
}
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = e;
size++;
}
private void resize(int capacity) {
E[] newData = (E[]) new Object[capacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
data = newData;
}
/**
* 查询元素
* 查询首位元素
* 查询末尾元素
* 查询指定下标元素
*/
/**
* 查询首位元素
*
* 时间复杂度:O(1)
* @return
*/
public E getFirst() {
return get(0);
}
/**
* 查询末尾元素
*
* 时间复杂度:O(1)
* @return
*/
public E getLast() {
return get(size - 1);
}
/**
* 查询指定下标元素
*
* 时间复杂度:O(1)
* @param index
* @return
*/
public E get(int index) {
//考虑边界情况
// 指定下标不合法 index < 0 || index >= size
if (index < 0 || index >= size) {
throw new IllegalArgumentException(" 指定下标不合法！");
}
return data[index];
}
/**
* 删除一个元素
* 删除头元素
* 删除尾元素
* 删除指定下标元素
*/
/**
* 删除头元素
*
* 时间复杂度:O(n)
*/
public E removeFirst() {
return remove(0);
}
/**
* 删除尾元素
*
* 时间复杂度:O(1)
*/
public E removeLast() {
return remove(size - 1);
}
/**
* 删除指定下标元素
*
*时间复杂度:O(n)
* @param index
*/
public E remove(int index) {
//考虑边界情况
//指定下标不合法 index < 0 || index >= size
if (index < 0 || index >= size) {
throw new IllegalArgumentException("指定下标不合法");
}
E e = get(index);
for (int i = index; i < size - 1; i++) {
data[i] = data[i + 1];
}
size--;
data[size] = null;
//缩容
if (size == data.length / 4 && data.length / 2 != 0) {
resize(data.length / 2);
}
return e;
}
/**
* 更新一个元素
* 更新头元素
* 更新尾元素
* 更新指定元素
*
*/
/**
* 更新头元素
*
* 时间复杂度:O(1)
* @param e
*/
public void setFirst(E e) {
set(0, e);
}
/**
* 更新尾元素
*
* 时间复杂度:O(1)
* @param e
*/
public void setLast(E e) {
set(size - 1, e);
}
/**
* 更新指定元素
*
* 时间复杂度:O(1)
* @param index
* @param e
*/
public void set(int index, E e) {
//考虑边界
//指定下标不合法 index < 0 || index >= size
if (index < 0 || index >= size) {
throw new IllegalArgumentException("指定下标不合法 ！");
}
data[index] = e;
}
/**
* 是否包含该元素
*
* 时间复杂度:O(n)
*/
public boolean contain(E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return true;
}
}
return false;
}
/**
* 查询元素的下标
*
* 时间复杂度:O(n)
*/
public int find(int e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return i;
}
}
return -1;
}
/**
* 获得数组中的元素的个数
*
* @return
*/
public int getSize() {
return size;
}
/**
* 获取数组的长度
*
* @return
*/
public int getCapacity() {
return data.length;
}
public boolean isEmpty(){
return size == 0 ? true : false;
}
public void swap(int i, int j){
if(i < 0 || i >= size || j < 0 || j >= size)
throw new IllegalArgumentException("Index is illegal.");
E t = data[i];
data[i] = data[j];
data[j] = t;
}
/**
* 重写toString
*
*/
@Override
public String toString() {
return "ArrayList{" +
"array=" + Arrays.toString(data) +
", size=" + size +
'}';
}
public static void main(String[] args) {
int i = 1;
while (i == 1){
}
/**
* 测试添加一个元素
*/
ArrayList<Integer> arrayList = new ArrayList(5);
arrayList.addFirst(1);
arrayList.addFirst(2);
;
arrayList.addFirst(3);
System.out.println(arrayList.toString());
arrayList.add(2, 0);
System.out.println(arrayList.toString());
arrayList.addLast(99);
System.out.println(arrayList.toString());
arrayList.addLast(99);
System.out.println(arrayList.toString());
/**
* 测试查询一个元素
*/
System.out.println("first element: " + arrayList.getFirst());
System.out.println("last element: " + arrayList.getLast());
System.out.println("get element index of 1 :" + arrayList.get(1));
/**
* 测试删除一个元素
*/
arrayList.removeFirst();
arrayList.removeLast();
arrayList.remove(1);
arrayList.removeLast();
System.out.println(arrayList.toString());
/**
* 测试更新一个元素
*/
arrayList.setFirst(12);
arrayList.setLast(13);
arrayList.set(1, 55);
System.out.println(arrayList.toString());
/**
* 测试是否包含该元素
*/
System.out.println(arrayList.contain(12));
System.out.println(arrayList.contain(55));
System.out.println(arrayList.contain(515));
/**
* 测试返回元素的下标
*/
System.out.println(arrayList.find(12));
System.out.println(arrayList.find(55));
System.out.println(arrayList.find(515));
}
}
