顺序表的实现以及相关的源码
·
ArrayList动态扩容机制的分析~~
先了解一下成员属性
假设我们使用了这个代码创建了顺序表
ArrayList<Integer> arrayList = new ArrayList<>();它的构造方法~~
构造方法初始化是一个空数组~~刚才不是说默认容量不是10吗？这里为什么是一个空数组，
不着急我们先往后看
当我们调用了这个方法，我们进入这个方法的内部~
arrayList.add(1);这个就是add内部的方法~~
public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
}再进入这个add方法的内部
private void add(E e, Object[] elementData, int s) {
// 判断数组中元素数量是否达到上限，如果达到，就会调用grow()
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}这个grow方法内部又有一个grow方法~~ 这里的实参是2 ~~ 也就是size + 1 == 2
private Object[] grow() {
return grow(size + 1);
} private Object[] grow(int minCapacity) {
int oldCapacity = elementData.length;
if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity, /* minimum growth */
oldCapacity >> 1 /* preferred growth */);
return elementData = Arrays.copyOf(elementData, newCapacity);
} else {
return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
}
}主要的分析逻辑在下面⬇️
以上就是构建大小为10的顺序表内部实现~~⬆️
那我们接下来说说，顺序表如何动态扩容，其实代码和上面都差不多~~
假设顺序表中的元素已经是10了，已经达到数组的最大容量了，需要动态扩容~~
这个以下⬇️图片就是动态扩容的源码分析，~ 动态扩容扩容为原数组的大小1.5倍~·
最后返回值，成功动态扩容
顺序表模拟实现
成员变量和构造方法
使用了两个构造方法一个无参构造方法和有参构造方法用来初始化数组~~
private int[] elem;
// 用来统计数组元素的个数
public int usedSize;
//默认容量为2，如果超过2就会扩容
private static final int DEFAULT_CAPACITY = 2;
public MyArrayList() {
elem = new int[DEFAULT_CAPACITY];
}
// 将顺序表的底层容量设置为intialCapacity
public MyArrayList(int initialCapacity) {
elem = new int[initialCapacity];
}
add方法
如果使用add方法需要先判断数组中元素是否已经满了~~如果满了就直接二倍扩容
扩容完了，就直接数组最后放元素即可~~ 放完元素，记得+1~~
// 新增元素,默认在数组最后新增
public void add(int data) {
if(isFull()) {
// 扩容
this.elem = Arrays.copyOf(this.elem, this.elem.length * 2);
}
this.elem[usedSize] = data;
usedSize++;
}这是用来判断是否扩容~~
如果数组元素个数已经达到数组大小了，就直接返回true ，否则返回false
// 判断数组是否是满的
public boolean isFull(){
if(this.usedSize == elem.length){
return true;
}
return false;
}
在某个位置添加元素
// 在 pos 位置新增元素
public void add(int pos, int data) {
if(pos < 0 || pos > this.usedSize){
throw new PostOutOfBoundsException("位置不合法");
}
if(isFull()) {
// 扩容
this.elem = Arrays.copyOf(this.elem, this.elem.length * 2);
}
for (int i = this.usedSize-1; i >= pos ; i--) {
this.elem[i+1] = elem[i];
}
this.elem[pos] = data;
this.usedSize++;
}
这下面的图就是这个代码的逻辑，仔细悟悟，相信你可以理解的~~
display方法
遍历数组
public void display() {
for (int i = 0; i < this.usedSize; i++) {
System.out.print(this.elem[i]+" ");
}
System.out.println();
}
contains方法
查找下标中的元素是否存在
也就是遍历一下数组中，判断数组中元素是否与其相等~~
// 判定是否包含某个元素
public boolean contains(int toFind) {
for (int i = 0; i < this.usedSize ; i++) {
if(this.elem[i] == toFind){
return true;
}
}
return false;
}
indexOf方法
找到某数值的下标，如果找到了就返回下标，找不到，就返回-1
public int indexOf(int toFind) {
for (int i = 0; i < this.usedSize; i++) {
if(this.elem[i] == toFind){
return i;
}
}
return -1;
}get方法
这个就是可以从数组下标直接找到某个元素，但在执行这些操作之前，需要判断pos位置是否合法~~
// 获取 pos 位置的元素
public int get(int pos) {
if(pos < 0 || pos >= this.usedSize){
throw new PostOutOfBoundsException("位置不合法");
}
return this.elem[pos];
}set方法
更新其值~~还是一样，需要判断pos位置是否合法~~，如果合法，直接更改~~
// 给 pos 位置的元素设为 value
public void set(int pos, int value) {
if(pos < 0 || pos >= this.usedSize){
throw new PostOutOfBoundsException("位置不合法");
}
this.elem[pos] = value;
}
remove方法
删除元素
//删除第一次出现的关键字key
public void remove(int toRemove) {
int index = this.indexOf(toRemove);
if(index == -1){
System.out.println("没有这个数据");
return;
}
// 这里面usedSize - 1 是用来防止下标越界的~~
for (int i = index; i < this.usedSize -1 ; i++) {
this.elem[i] = this.elem[i+1];
}
this.usedSize--;
}这下面就是这个代码实现的逻辑~~
size方法
获取数组的长度
// 获取顺序表长度
public int size() {
return this.usedSize;
}clear方法
清空数组
// 清空顺序表
public void clear() {
this.usedSize = 0;
}
最后把代码完整版放进来
import java.util.Arrays;
public class MyArrayList {
private int[] elem;
public int usedSize;
private static final int DEFAULT_CAPACITY = 2;
public MyArrayList() {
elem = new int[DEFAULT_CAPACITY];
}
// 将顺序表的底层容量设置为intialCapacity
public MyArrayList(int initialCapacity) {
elem = new int[initialCapacity];
}
// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
public void display() {
for (int i = 0; i < this.usedSize; i++) {
System.out.print(this.elem[i]+" ");
}
System.out.println();
}
// 新增元素,默认在数组最后新增
public void add(int data) {
if(isFull()) {
// 扩容
this.elem = Arrays.copyOf(this.elem, this.elem.length * 2);
}
this.elem[usedSize] = data;
usedSize++;
}
// 判断数组是否是满的
public boolean isFull(){
if(this.usedSize == elem.length){
return true;
}
return false;
}
// 在 pos 位置新增元素
public void add(int pos, int data) {
if(pos < 0 || pos > this.usedSize){
throw new PostOutOfBoundsException("位置不合法");
}
if(isFull()) {
// 扩容
this.elem = Arrays.copyOf(this.elem, this.elem.length * 2);
}
for (int i = this.usedSize-1; i >= pos ; i--) {
this.elem[i+1] = elem[i];
}
this.elem[pos] = data;
this.usedSize++;
}
// 判定是否包含某个元素
public boolean contains(int toFind) {
for (int i = 0; i < this.usedSize ; i++) {
if(this.elem[i] == toFind){
return true;
}
}
return false;
}
// 查找某个元素对应的位置
public int indexOf(int toFind) {
for (int i = 0; i < this.usedSize; i++) {
if(this.elem[i] == toFind){
return i;
}
}
return -1;
}
// 获取 pos 位置的元素
public int get(int pos) {
if(pos < 0 || pos >= this.usedSize){
throw new PostOutOfBoundsException("位置不合法");
}
return this.elem[pos];
}
// 给 pos 位置的元素设为 value
public void set(int pos, int value) {
if(pos < 0 || pos >= this.usedSize){
throw new PostOutOfBoundsException("位置不合法");
}
this.elem[pos] = value;
}
//删除第一次出现的关键字key
public void remove(int toRemove) {
int index = this.indexOf(toRemove);
if(index == -1){
System.out.println("没有这个数据");
return;
}
// 这里面usedSize - 1 是用来防止下标越界的~~
for (int i = index; i < this.usedSize -1 ; i++) {
this.elem[i] = this.elem[i+1];
}
this.usedSize--;
}
// 获取顺序表长度
public int size() {
return this.usedSize;
}
// 清空顺序表
public void clear() {
this.usedSize = 0;
}
}
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
28
0- 0
已为社区贡献1条内容
所有评论(0)