java数据结构基础:线性表

时间:2022-10-30 08:36:54

前言

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

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

需求分析

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

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

?
1
2
3
4
private Object[] arr; // 底层的结构
private int index = -1; // 代表元素的索引位置
private int size; // 当前线性表的长度
private int LinearListLength = 4; // 线性表的默认长度

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

编码

add方法

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

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

?
1
2
3
4
5
6
7
8
9
10
11
public E add(E item) {
        // 先初始化线性表
        capacity();
        // 初始化完成后先把index指针后移一位,也就是+1
        // 后移一位之后将要添加的元素赋值到数组中
        this.arr[++index] = item;
        System.out.println(index);
        // 添加完成后长度+1
        this.size++;
        return item;
    }

getIndex方法

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

?
1
2
3
public E getIndex(int index) {
        return (E) this.arr[index];
    }

pop方法

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

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * 删除指定位置的元素
 */
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类型的索引值,一个泛型数据。在指定位置插入该泛型值,然后将后面的值全部后移一位。

?
1
2
3
4
5
6
7
8
9
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

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

?
1
2
3
4
5
public void getAll() {
        for (Object o : this.arr) {
            System.out.println(o);
        }
    }

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

全部代码

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
package com.zxy.xianxingbiao;
/**
 * @Author Zxy
 * @Date 2021/2/4 16:54
 * @Version 1.0
 */
import java.util.Arrays;
/**
 * 演示线性表的使用  底层使用数组
 */
public class MyLinearList<E> {
    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<String> 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();
    }
}

总结

本篇文章就到这里了,希望能给你带来帮助,也希望您能够多多关注服务器之家的更多内容!

原文链接:https://blog.csdn.net/weixin_43581288/article/details/113658746