线性表
-
线性表是具有n个相同类型元素的有限序列（n >= 0）
- a1是首节点（首元素），an是尾节点（尾元素） - a1是a2的前驱，a2是a1的后继
对于非空的线性表和线性结构，其特点如下：
- 存在唯一的一个被称作“第一个”的数据元素
- 存在唯一的一个被称作“最后一个”的数据元素
- 除了第一个之外，结构中的每个数据元素均有一个前驱
- 除了最后一个之外，结构中的每个数据元素都有一个后继
- 常见的线性表有
- 数组
- 链表
- 栈
- 队列
- 哈希表（散列表）
数组（Array）
- 数组是一种顺序存储的线性表，所有元素的内存地址是连续的
int[] array = new int[]{11,22,33};
- 在很多编程语言中，数组都有个致命的缺点：无法动态修改容量
- 实际开发中，更希望数组的容量是可以动态改变的
动态数组(Dynamic Array)接口设计
-
intsize(); //元素的数量 -
booleanisEmpty(); //是否为空 -
booleancontains(E element); //是否包含某个元素 -
voidadd(E element); //添加元素到最后面 - E get (
intindex); //返回index位置对应的元素 - E set (
intindex,E element); //设置index位置的元素 -
voidadd(intindex,E element); //往index位置添加元素 - E remove(
intindex); //删除index位置对应的元素 -
intindexOf(E element); //查看元素的位置 -
voidclear(); //清除所有的元素
简单的数组接口设计，动态扩容在后面
package com.ld;
public class Main {
public static void main(String[] args) {
//new 是向堆空间申请内存，java垃圾回收机制：list局部变量在自动释放时，对应的指向的堆内存空间也释放
ArrayList list = new ArrayList();
list.clear();
list.add(99);
list.add(88);
list.add(77);
list.add(66);
list.add(55);
list.remove(list.size()-1);
System.out.println(list.toString());
}
}
package com.ld;
public class ArrayList {
/*
* 元素的数量
* */
private int size;
/*
* 所有的元素
* */
private int[] 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 = new int[capaticy];
}
public ArrayList() {
// elements = new int[DEFAULT_CAPACITY];
this(DEFAULT_CAPACITY);
}
/*
* 清除所有元素
* */
public void clear() {
size = 0;
}
/*
* 元素的数量
* @return
* */
public int size() {
return size;
}
/*
* 是否为空
* @return
* */
public boolean isEmpty() {
return size == 0;
}
/*
* 是否包含某个元素
* @param element
* @return
* */
public boolean contains(int element) {
return indexOf(element) != ELEMENT_NOT_FOUND;
}
/*
* 添加元素到尾部
* @param element
* */
public void add(int element) {
elements[size++] = element;
//等价于add(size, element);
}
/*
* 获取index位置的元素
* @param index
* @return
* */
public int get(int index) {
rangeCheck(index);
return elements[index];
}
/*
* 设置index位置的元素
* @param index
* @param element
* @return 原来的元素
* */
public int set(int index,int element) {
rangeCheck(index);
int old = elements[index];
elements[index] = element;
return old;
}
/*
* 在index位置插入一个元素
* @param index
* @param element
* */
public void add(int index,int element) {
rangeCheckForAdd(index);
for (int i = size-1; i >=index; i--) {
elements[i+1] = elements[i];
}
elements[index] = element;
size++;
}
/*
* 删除index位置的元素
* @param index
* @return
* */
public int remove(int index) {
rangeCheck(index);
int old = elements[index];
for (int i = index+1; i <= size-1; i++) {
elements[i - 1] = elements[i];
}
size--;
return old;
}
/*
* 查看元素的索引
* @param element
* @return
* */
public int indexOf(int element) {
for (int i = 0; i < size; i++) {
if (elements[i] == element) {
return i;
}
}
return ELEMENT_NOT_FOUND;
}
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
//打印数组
//重写toString方法，在toString方法中将元素拼接成字符串，
//字符串拼接建议使用StringBuilder
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++) {
string.append(elements[i]);
if (i != size-1) {
string.append(",");
}
}
string.append("]");
return string.toString();
}
}
动态扩容以及泛型
动态扩容的思路：堆内存开辟空间时，是随机分配的，所以之前的数组如果内存不够用时，是不可以直接在之前的数组后边继续开辟空间的，只能是判断内存不够用时，重新开辟一个新的更大的数组内存空间，把之前的数组的内容拷贝到新的数组里边，然后销毁之前的旧数组就可以了
泛型：使用泛型技术可以让动态数组更加通用，可以存放任何数据类型
最后的代码结果
ArrayList.java
package 动态数组;
import java.util.Iterator;
public class ArrayList<E> {
/*元素的数量*/
private int size;
/*所有的元素*/
private E[] elements;
//private 私有，static静态，能保证内存只有一份，final常量，相当于其他语言的const
private static final int DEFAULT_CAPACITY = 2;
private static final int ELEMENT_NOT_FOUND = -1;
//构造函数
@SuppressWarnings("unchecked")
public ArrayList(int capaticy) {
//最开始用户给的数小于常量的值，就直接给设置成常量的值，个人设计问题，也可以判断<0.直接设置容量为1，但是很快就会不够用了，所以暂时先设计成，容量小于我给的常量就先设置成容量为常量的数值
capaticy = (capaticy < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY:capaticy;
elements = (E[]) new Object[capaticy];
}
public ArrayList() {
//elements = new E[DEFAULT_CAPACITY];
//或者用下边的方法
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() {
// if (size == 0) {
// return true;
// }else {
// return false;
// }
return size == 0;
}
/*是否包含某个元素
* @param element
* @return*/
public boolean contains( E element) {
return indexOf(element) != ELEMENT_NOT_FOUND;
}
/*
* 添加元素到尾部
* @param element*/
public void add(E element) {
// elements[size] = element;
// size++;
// //或者
// //elements[size++] = element;
add(size, element);
}
/*获取index位置的元素
* @param index
* @return*/
public E get(int index) {
rangeCheck(index);
return elements[index];
}
/*设置index位置的元素
* @param index
* @param element
* @return原来的元素*/
public E set(int index,E element) {
rangeCheck(index);
E old = elements[index];
elements[index] = element;
return old;
}
/*在index位置插入一个元素
* @param index
* @param element*/
public void add(int index,E element) {
rangeCheckForAdd(index);
ensureCapacity(size+1);
for (int i = size-1; i >=index ; i--) {
elements[i+1] = elements[i];
}
elements[index] = element;
size++;
}
/*删除index位置的元素
* @param index
* @return*/
public E remove(int index) {
rangeCheck(index);
E old = elements[index];
for (int i = index+1; i <=size-1; i++) {
elements[i-1] = elements[i];
}
size -- ;
elements[size] = null;
return old;
}
/*查看元素的索引
* @param element
* @return*/
public int indexOf(E element) {
//因为add的方法是可以寸null的，java里也是支持保存null的，但是如果某一个对象是null，
//当调用下边的.equals(element)方法时是会报异常的，所以这里需要判断if==null的情况
if (element == null) {
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;
/*if这里不能直接用==号去判断，需要调用对象方法里边的equals方法去判断对象是否相等，
在对象的类里需要去重写equals方法，如果对象里没有重写equals方法，
那么对比的就是两个对象是否完全相等，也就是意味着两个对象的地址值是否完全相等
如果重写了equals，就意味着自己去定义相等的条件是什么
*/
}
}
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.5*oldCapacity
@SuppressWarnings("unchecked")
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() {
// TODO Auto-generated method stub
StringBuilder string = new StringBuilder();
string.append("size=").append(size).append(",[");
for (int i = 0; i < size; i++) {
string.append(elements[i]);
if (i != size-1) {
string.append(",");
}
}
string.append("]");
return string.toString();
}
}
Main.java
package 动态数组;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
ArrayList<Person> persons = new ArrayList<>();
persons.add(new Person(10, "jack"));
persons.add(new Person(12, "james"));
persons.add(new Person(15, "rose"));
System.out.println(persons);
// list.add(99);
// list.add(88);
// list.add(77);
// list.add(66);
// list.add(55);
//
//
// list.set(3, 80);
//
//
// System.out.println(list.toString());
}
}
Person.java
package 动态数组;
public class Person {
private int age;
private String name;
//option+command+s快捷键，-> Generate Constructors from Superclass->勾选要生成构造函数的属性->Generate
//自动生成如下的构造方法
public Person(int age, String name) {
super();
this.age = age;
this.name = name;
}
//option+command+s快捷键，-> Generate toString()自动生成toString方法
@Override
public String toString() {
return "Person [age=" + age + ", name=" + name + "]";
}
@Override
//判断对象是否相等，在java中可以重写equals方法，在equals方法中自定义是否相等的条件，
public boolean equals(Object obj) {
// TODO Auto-generated method stub
Person person = (Person) obj;
return this.age == person.age;
}
}
