java数据结构基础:线性表

java数据结构基础:线性表

目录前言需求分析编码add方法getIndex方法pop方法insert方法getAll全部代码总结

前言

其实线性表在生活中和栈的结构差不多。昨天总结了一篇单链表，也是线性表的一种。

今天用另一种写法来控制指针的移动实现数据的顺序存储结构。

需求分析

首先要明确，这种顺序存储结构的线性表底层用什么。根据之前查看过的源码来看，list一般都是以数组为底层。我们也不例外。

其次，我们还得去定义好线性表的长度，以及每个元素的指针。

private Object[] arr; // 底层的结构

private int index = -1; // 代表元素的索引位置

private int size; // 当前线性表的长度

private int LinearListLength = 4; // 线性表的默认长度

我们这儿只演示添加、删除、获取指定位置、获取全部以及判http://断是否为空这五种形式。

编码

add方法

add方法为向线性表中添加元素，需要传入一个泛型参数。实现思路是让index+1然后把index赋值给数组得到索引区域，再让size+1

总体设计比较简单，看代码。

public E add(E item) {

// 先初始化线性表

capacity();

// 初始化完成后先把index指针后移一位，也就是+1

// 后移一位之后将要添加的元素赋值到数组中

this.arr[++index] = item;

System.out.println(index);

// 添加完成后长度+1

this.size++;

return item;

}

getIndex方法

getIndex方法主要是用来获取指定位置的元素，这个就很简单了，因为底层是数组，所以我们可以直接用数组的索引去获取。

public E getIndex(int index) {

return (E) this.arr[index];

}

pop方法

pop方法作用是删除指定位置的元素。需要传入一个int类型的索引。由于特殊性，我们必须得借用上面的获取指定位置的元素的方法来实现这一步骤。

在元素删除后，通过遍历循环去将index位置向前移动一位。具体代码如下：

/**

* 删除指定位置的元素

*/

public E pop(int index) {

E e = getIndex(index);

if (e != null) {

for (int i = index; i < size; i++) {

arr[i] = arr[i + 1];

}

this.size--;

return e;

} else {

return null;

}

}

insert方法

insert方法需要传入两个参数，一个int类型的索引值，一个泛型数据。在指定位置插入该泛型值，然后将后面的值全dMxlVmMwy部后移一位。

public E insert(int index, E item) {

System.out.println(size);

for (int i = index; i < size; i++) {

arr[i + 1] = arr[i];

}

arr[index] = item;

this.size++;

return item;

}

getAll

这个方法不用我多说了，一个简单的遍历循环

public void getAll() {

for (Object o : this.arr) {

System.out.println(o);

}

}

这儿遍历的Object类型会自动转化成添加元素时的类型

全部代码

package com.zxy.xianxingbiao;

/**

* @Author Zxy

* @Date 2021/2/4 16:54

* @Version 1.0

*/

import java.util.Arrays;

/**

* 演示线性表的使用 底层使用数组

*/

public class MyLinearList {

private Object[] arr; // 底层的结构

private int index = -1; // 代表元素的索引位置

private int size; // 当前线性表的长度

private int LinearListLength = 4; // 线性表的默认长度

/**

* 判断线性表是否为空

*/

public boolean empty() {

return this.size == 0 ? true : false;

}

/**

* 给线性表中添加元素

*/

public E add(E item) {

// 先初始化线性表

capacity();

// 初始化完成后先把index指针后移一位，也就是+1

// 后移一位之后将要添加的元素赋值到数组中

this.arr[++index] = item;

System.out.println(index);

// 添加完成后长度+1

this.size++;

return item;

}

/**

* 在指定位置插入元素

*/

public E insert(int index, E item) {

System.out.println(size);

for (int i = index; i < size; i++) {

arr[i + 1] = arr[i];

}

arr[index] = item;

this.size++;

return item;

}

/**

* 获取指定位置的元素

*/

public E getIndex(int index) {

return (E) this.arr[index];

}

/**

* 删除指定位置的元素

*/

public E pop(int index) {

E e = getIndex(index);

if (e != null) {

for (int i = index; i < size; i++) {

arr[i] = arr[i + 1];

}

this.size--;

return e;

} else {

return null;

}

}

/**

* 获取全部的元素

*/

public void getAll() {

for (Object o : this.arr) {

System.out.println(o);

}

}

/**

* 数组初始化或者以1.5倍容量对数组扩容

*/

private void capacity() {

// 数组初始化

if (this.arr == null) {

this.arr = new Object[this.LinearListLength];

}

// 以1.5倍对数组扩容

if (this.size - (this.LinearListLength - 1) >= 0) { // 如果当前数组的元素个数大于了当前数组的最后一个索引值

this.LinearListLength = this.LinearListLength + (this.LinearListLength >> 1); // 位运算，让长度变成原来的1/2

this.arr = Arrays.copyOf(this.arr, this.LinearListLength); // 复制一个新的数组，用新开辟的长度

}

}

public static void main(String[] args) {

MyLinearList list = new MyLinearList<>();

list.add("a");

list.add("b");

list.add("c");

System.out.println(list.getIndex(1));

list.pop(1);

System.out.println(list.getIndex(1));

list.getAll();

}

}

总结

本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注我们的更多内容！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。