【数据结构（1）-线性表（顺序存储结构）】概念：指的是用一段地址连续的存储单元依次存储线性表的数据元素；用一维数组来实现顺序存储结构；
重要属性：存储空间的起始位置、线性表的最大存储量、线性表的当前长度；
优点：无须为表示表中元素之间的逻辑关系而增加额外的存储空间；可以快速的查看任意位置的元素。
缺点：插入和删除操作需要移动大量元素；当线性表长度变化比较大时，难以确定存储空间的容量；造成存储空间的“碎片”；
/*
* 1. 顺序结构（数组）实现单链表
*/
public class MyArrayList {public static void main(String[] args) {
MyArrayList list = new MyArrayList();
list.add("aaa");
list.add("bbb");
list.add("ccc");
list.insert("ddd", 2);
list.remove();
System.out.println(list);
System.out.println(list.locate("aaa"));
}private static final int DEFAULT_SIZE = 10;
// 数组的默认长度
private int size;
// 记录元素的个数
private int capacity;
// 记录数组的长度
private Object[] elementData;
// 保存元素的数组// 以默认数组长度创建空顺序线性表
public MyArrayList() {
capacity = DEFAULT_SIZE;
elementData = https://www.it610.com/article/new Object[capacity];
}// 以一个初始化元素来创建顺序表
public MyArrayList(T element) {
this();
// 调用上面的无参构造函数
elementData[0] = element;
size++;
}// 以初始化元素和初始大小创建顺序线性表
public MyArrayList(int initSize, T element) {
capacity = 1;
while (capacity < initSize) {
capacity <<= 1;
// //把capacity设为大于initSize的最小的2的n次方
}
elementData = new Object[capacity];
elementData[0] = element;
size++;
}// 获取线性表元素的个数
public int length() {
return size;
}// 获取顺序线性表中索引为i出的元素
public T getValue(int i) {
if (i < 0 || i> size - 1) {
throw new IndexOutOfBoundsException("线性表索引越界");
}
return (T) elementData[i];
}// 查找顺序线性表中制指定元素的索引
public int locate(T element) {
for (int i = 0;
i < size;
i++) {
if (elementData[i].equals(element))
return i;
}
return -1;
}// 向线性表的指定位置插入一个元素
public void insert(T element, int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("线性表索引越界");
}
ensureCapacity(size + 1);
// 将index处以后的所有元素向后移动一格
System.arraycopy(elementData, index, elementData, index + 1, size
- index);
elementData[index] = element;
size++;
}// 在线性顺序表开始添加一个元素
public void add(T element) {
insert(element, size);
}// 扩充底层数组长度
private void ensureCapacity(int minCapacity) {
// 如果数组的原有长度小于目前所需长度
if (minCapacity > capacity) {
// 不断的将capacity*2，直到capacity大于minCapacity为止
while (capacity < minCapacity) {
capacity <<= 1;
}
elementData = https://www.it610.com/article/Arrays.copyOf(elementData, capacity);
}
}// 删除顺序线性表中指定索引出的元素
public T delete(int index) {
if (index < 0 || index> size - 1) {
throw new IndexOutOfBoundsException("线性表索引越界");
}
T oldValue = https://www.it610.com/article/(T) elementData[index];
int numMoved = size - index - 1;
if (numMoved> 0) {
System.arraycopy(elementData, index + 1, elementData, index,
numMoved);
}
elementData[--size] = null;
// 清空最后一个元素
return oldValue;
}// 删除最后一个元素
public T remove() {
return delete(size - 1);
}// 判断线性表是否为空表
public boolean empty() {
return size == 0;
}// 清空线性表
public void clear() {
Arrays.fill(elementData, null);
size = 0;
}// 重写toString方法
public String toString() {
if (size == 0) {
return "[]";
} else {
StringBuilder sb = new StringBuilder("[");
for (int i = 0;
i < size;
i++) {
sb.append(elementData[i].toString() + ",");
}
int len = sb.length();
return sb.delete(len - 1, len).append("]").toString();
}
}
}
推荐阅读
- 笔记|C语言数据结构——二叉树的顺序存储和二叉树的遍历
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- 数据结构和算法|LeetCode 的正确使用方式
- 先序遍历 中序遍历 后序遍历 层序遍历
- 数据结构|C++技巧（用class类实现链表）
- 数据结构|贪吃蛇代码--c语言版 visual c++6.0打开
- 算法|算法-二分查找
- 数据结构学习指导|数据结构初阶（线性表）
- leetcode题解|leetcode#106. 从中序与后序遍历序列构造二叉树
- java|ObjectOrientedProgramming - 面向对象的编程（多态、抽象类、接口）- Java - 细节狂魔