赞
踩
目录
线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列...
线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储。
我们先自己来完成一个顺序表8:
具体效果如图:
源码如下:
建议小伙伴们自己思考一下上手敲一敲代码,对后续的学习可以更好的理解哟~
MyArrayList.java
- 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
- public class EmptyExpection extends RuntimeException{
- public EmptyExpection() {
-
- }
- public EmptyExpection(String message) {
- super(message);
- }
- }
PosWronfulExpection.java
- public class PosWronfulExpection extends RuntimeException{
- public PosWronfulExpection(){
-
- }
- public PosWronfulExpection(String message){
- super(message);
- }
- }
TestList.java
- 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();
- }
- }

在集合框架中,ArrayList是一个普通的类,实现了List接口.如图:
【说明】
1. ArrayList实现了RandomAccess接口,表明ArrayList支持随机访问
2. ArrayList实现了Cloneable接口,表明ArrayList是可以clone的
3. ArrayList实现了Serializable接口,表明ArrayList是支持序列化的
4. 和Vector不同,ArrayList不是线程安全的,在单线程下可以使用,在多线程中可以选择Vector或者CopyOnWriteArrayList
5. ArrayList底层是一段连续的空间,并且可以动态扩容,是一个动态类型的顺序表
方法 | 解释 |
ArrayList() | 无参构造 |
ArrayList(Collection<? extends E> c) | 利用其他 Collection 构建 ArrayList |
ArrayList(int initialCapacity) | 指定顺序表初始容量 |
详情可以去帮助手册中查找:
方法 | 解释 |
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 |
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。