顺序表
线性表是具有相同特征的n个数据元素的有限序列。线性表是实践中广泛使用的数据结构。常见的线性表：顺序表、链表、栈、队列、字符串等.线性表在逻辑上是一个线性结构，也就是说是一条连续的直线。然而，它在物理结构上不一定是连续的。当线性表被物理存储时，通常以数组和链式结构存储。
顺序表和链表的区别：顺序表：元素之间，在一个连续的内存空间中。
链表：在元素之间，可以在不连续的内存空间中。
一、 ArrayList 的使用
1.1 创建 ArrayList 实例
ListString arrayList=new arrayList()；//向上转换
system . out . println(ArrayList . size())；
system . out . println(ArrayList . isempty())；
1.2 添加元素
//add(一个参数):添加到序列表的末尾。
ArrayList . add(' c ')；
ArrayList . add(' c ')；
ArrayList . add(' Java ')；
ArrayList . add(' python ')；
system . out . println(ArrayList . size())；
System.out.println('后缀四次：' arrayList ')；
//add(两个参数):添加到序列表的末尾。
arrayList.add(2，' JavaScript ')；
system . out . println(ArrayList . size())；
System.out.println('在中间插入一次：' arrayList ')；00-1010//按下标删除
ArrayList . remove(1)；
System.out.println('按位置删除' ArrayList)；
//按内容删除
ArrayList . remove(' c ')；
System.out.println('按值删除：' ArrayList ')；00-1010//按内容搜索
boolean ret=ArrayList . contains(' Java ')；
System.out.println('查找java的结果是：' ret ')；
//按下标搜索
int index=ArrayList . indexof(' Java ')；
System.out.println('查找java的位置是：' index ')；
1.3 删除
String elem=ArrayList . get(0)；
System.out.println('0元素为：' elem ')
arrayList.set(0，' PHP ')；
System.out.println('修改订单表：' ArrayList ')；00-1010//(1)下标遍历
System.out.println('下标遍历：')；
for(int I=0；I ArrayList . size()；I){ 0
system . out . println(ArrayList . get(I))；
}
//(2)遍历迭代器
System.out.println('遍历迭代器：')；
//首先通过迭代器方法获取迭代器对象。
IteratorString迭代器=ArrayList . iterator()；
//然后遍历while循环。
while(iterator . HasNeXt()){ 0
string e=iterator . next()；
system . out . println(e)；
}
//(3)for-要遍历的每个(本质上基于迭代器)
System.out.println('遍历for-each:')；
对于(字符串e :数组列表){ 0
System.out.println(
e);
}
二、 实现自己的 MyArrayList
public class MyArrayList {
private String[] data = null;
// 当前顺序表中有效的元素个数
private int size = 0;
// 当前顺序表中的最大容纳元素个数，如果 size 超过了capacity 就需要扩容
private int capacity = 100;
public MyArrayList() {
data = new String[capacity];
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("[");
for (int i = 0; i < size; i++) {
stringBuilder.append(data[i]);
if (i < (size - 1)) {
stringBuilder.append(",");
}
}
stringBuilder.append("]");
return stringBuilder.toString();
}
// 扩容
private void realloc() {
capacity = 2 * capacity;
String[] newData = new String[capacity];
for (int i = 0; i < data.length; i++) {
newData[i] = data[i];
}
data = newData;
}
// 1.把元素插到顺序表末尾
public void add(String elem) {
if (size >= capacity) {
realloc();
}
data[size] = elem;
size ++;
}
// 时间复杂度：O（N）
// 2.把元素插入到任意中间位置
public void add (int index,String elem) {
if (index < 0 || index > size) {
return;
}
if (size >= capacity) {
realloc();
}
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = elem;
size ++;
}
// 3.按照下标位置删除元素
public String remove (int index) {
if (index < 0 || index > size) {
return null;
}
String result = data[index];
for (int i = index; i < size - 1; i++) {
data[i] = data[i + 1];
}
return result;
}
// 4.按照元素的值删除
public boolean remove (String elem) {
int index = 0;
for (; index < size; index++) {
if (data[index].equals(elem)) {
break;
}
}
if (index >= size) {
return false;
}
for (int i = index; i < size; i++) {
data[i] = data[i + 1];
}
size --;
return true;
}
// 5 根据下标获取元素
public String get (int index) {
if (index < 0 || index > size) {
// return null;
// 也可以抛出一个异常
throw new MyArrayListIndexOutOfRangeException("下标越界了！ index = " + index);
}
return data[index];
}
// 6 根据下标修改元素
public void set (int index,String elem) {
if (index < 0 || index > size) {
return;
}
data[index] = elem;
}
// 7 判断元素是否存在
public boolean contains (String elem) {
for (int i = 0; i < size; i++) {
if (data[i].equals(elem)) {
return true;
}
}
return false;
}
// 8 查找元素位置
public int location (String elem) {
for (int i = 0; i < size; i++) {
if (data[i].equals(elem)) {
return i;
}
}
return -1;
}
// 9 查找元素位置，从后往前找
public int locationFromTail (String elem) {
for (int i = size - 1; i > 0; i--) {
if (data[i].equals(elem)) {
return i;
}
}
return -1;
}
public void clear(){
size = 0;
}
public int size(){
return size;
}
public boolean isEmpty(){
return size == 0;
}
// 测试
public static void main(String[] args) {
MyArrayList myArrayList = new MyArrayList();
myArrayList.add("c");
myArrayList.add("c++");
myArrayList.add("python");
myArrayList.add("java");
System.out.println(myArrayList);
// myArrayList.add(2,"Go");
// System.out.println(myArrayList);
// String result = myArrayList.remove(0);
// System.out.println(result);
// System.out.println(myArrayList);
// System.out.println(myArrayList.get(1));
// myArrayList.set(0,"VB");
// System.out.println(myArrayList);
// // 验证下标越界
// System.out.println(myArrayList.get(100));
}
