1.线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列... 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
2.顺序表
2.1接口的实现
我们先自己来完成一个顺序表8：
具体效果如图：
源码如下：
建议小伙伴们自己思考一下上手敲一敲代码，对后续的学习可以更好的理解哟~
MyArrayList.java
代码语言：javascript复制import javax.xml.bind.annotation.XmlType;
import java.lang.reflect.Array;
import java.util.Arrays;
public class MyArratList {
public int[] elem;
public int usedSize;
public static final int DEFAULT_SIZE = 10;
public MyArratList(){
this.elem = new int[DEFAULT_SIZE];
}
//打印数组
public void display(){
for (int i = 0; i < this.usedSize; i ) {
System.out.print(elem[i] " ");
}
System.out.println();
}
//新增元素，默认在素组最后新增
public void add(int data) {
//1.判断是不是满了
if(isFull()){
// 2.如果满了，要扩容
this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
}
//3.增加数据
this.elem[this.usedSize] = data;
//4.useSize
usedSize ;
}
public int size() {
return this.usedSize;
}
public boolean isFull(){
if(size() >= this.elem.length ){
return true;
}
return false;
}
// 在 pos 位置新增元素
//如果pos位置不合法，那么就会抛出一个PosWronfulExpection
public void add(int pos, int data) throws PosWronfulExpection{
if(isFull()){
System.out.println("满了!");
this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
}
if(pos < 0 || pos > this.usedSize){
System.out.println("pos位置不合法！");
throw new PosWronfulExpection("pos位置不合法！");
}
//pos合法
//1.开始挪动数据
for (int i = usedSize-1; i >= pos; i--) {
this.elem[i 1] = this.elem[i];
}
//2.插入数据
this.elem[pos] = data;
//3.useSize
usedSize ;
}
// 判定是否包含某个元素
public boolean contains(int toFind) {
for (int i = 0; i < usedSize; i ) {
if(toFind == this.elem[i]){
return true;
}
}
return false;
}
// 查找某个元素对应的位置
public int indexOf(int toFind) {
for (int i = 0; i < usedSize; i ) {
if(toFind == elem[i]){
return i;
}
}
return -1;
}
// 获取 pos 位置的元素
public int get(int pos) {
if(isEmpty()){
throw new EmptyExpection("当前顺序表为空！");
}
if(pos < 0||pos >=this.usedSize){
throw new PosWronfulExpection("pos不合法！");
}
return elem[pos];
}
public boolean isEmpty(){
return size()== 0;
}
// 给 pos 位置的元素设为 value
public void set(int pos, int value) {
if(isEmpty()){
throw new EmptyExpection("当前顺序表为空！！");
}
if(pos < 0||pos >=this.usedSize){
throw new PosWronfulExpection("pos位置不合法！！！");
}
this.elem[pos] = value;
}
//删除第一次出现的关键字key
public void remove(int key) {
if(isEmpty()){
throw new EmptyExpection("当前顺序表为空！");
}
int index = this.indexOf(key);
if(index == -1){
System.out.println("没有这个数字！");
}
for (int i = index; i < this.usedSize-1; i ) {
this.elem[i] = this.elem[i 1];
}
usedSize--;
}
// 获取顺序表长度
// 清空顺序表
public void clear() {
/* //当变量是引用类型时：
for (int i = 0; i < size(); i ) {
this.elem = null;
}*/
this.usedSize = 0;
}
}EmptyExpection.java
代码语言：javascript复制public class EmptyExpection extends RuntimeException{
public EmptyExpection() {
}
public EmptyExpection(String message) {
super(message);
}
}PosWronfulExpection.java
代码语言：javascript复制public class PosWronfulExpection extends RuntimeException{
public PosWronfulExpection(){
}
public PosWronfulExpection(String message){
super(message);
}
}TestList.java
代码语言：javascript复制import com.sun.xml.internal.bind.v2.TODO;
public class TestList {
public static void main(String[] args) {
MyArratList myArratList = new MyArratList();
myArratList.add(1);
myArratList.add(2);
myArratList.add(3);
myArratList.display();
try {
myArratList.add(1,10);
}catch (PosWronfulExpection e){
e.printStackTrace();
}
myArratList.display();
//trycatch的快捷键！！
System.out.println(myArratList.contains(10));
System.out.println(myArratList.contains(100));
System.out.println(myArratList.indexOf(10));
System.out.println(myArratList.indexOf(100));
try{
System.out.println(myArratList.get(1));
}catch (PosWronfulExpection e){
e.printStackTrace();
}
System.out.println("-------------------------------------");
myArratList.set(0,99);
myArratList.display();
}
}3. ArrayList简介
在集合框架中，ArrayList是一个普通的类，实现了List接口.如图：
【说明】 1. ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问 2. ArrayList实现了Cloneable接口，表明ArrayList是可以clone的 3. ArrayList实现了Serializable接口，表明ArrayList是支持序列化的 4. 和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者CopyOnWriteArrayList 5. ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表
4.ArrayList使用
4.1 ArrayList的构造
方法 | 解释 |
|---|---|
ArrayList() | 无参构造 |
ArrayList(Collection<? extends E> c) | 利用其他 Collection 构建 ArrayList |
ArrayList(int initialCapacity) | 指定顺序表初始容量 |
4.2ArraysList常见操作
详情可以去帮助手册中查找：
方法 | 解释 |
|---|---|
boolean add(E e) | 尾插 e |
void add(int index, E element) | 将 e 插入到 index 位置 |
boolean addAll(Collection<? extends E> c) | 尾插 c 中的元素 |
E remove(int index) | 删除 index 位置元素 |
boolean remove(Object o) | 删除遇到的第一个 o |
E get(int index) | 获取下标 index 位置元素 |
E set(int index, E element) | 将下标 index 位置元素设置为 element |
void clear() | 清空 |
boolean contains(Object o) | 判断 o 是否在线性表中 |
int indexOf(Object o) | 返回第一个 o 所在下标 |
int lastIndexOf(Object o) | 返回最后一个 o 的下标 |
List<E> subList(int fromIndex, int toIndex) | 截取部分 list |
