Java实现线性表的顺序和链式存储

什么是线性表？

​ 线性表（Linear List），是由同类型数据元素构成有序序列的线性结构，表中元素个数称为线性表的长度；线性表没有元素时，称为空表；表的起始位置称为表头，表的结束位置称为表尾。

抽象数据类型描述

​ 类型名称：线性表（List）

​ 数据对象集：线性表是n（n>=0）个元素构成的有序序列（a,a2,...,an）

​ 操作集：Item 表示元素类型，整数 i 表示位置

• boolean isEmpty() 线性表是否为空
• int size() 线性表中的元素个数
• void insert(Item item, int i) 在 i 位置插入元素
• void delete(int i) 在第i个位置删除数据(即删除数组下标为i-1这个位置)
• int find(Item item) 查找某个元素，如果找到，返回下标；否则返回-1

顺序存储实现（固定大小）

​ 创建一个泛型类List：

public class List<Item>{
    private Item[] data; // 泛型数组存储数据
    private int last = -1; // last表示最后一个元素的下标
}

​ 构造函数：

public List(int size){
        data = (Item[]) new Object[size]; // java不允许创建泛型数组，所以需要用到类型转换
}

插入数据

​ 在这里，我们插入数据的位置范围是1_{n+1，即第一个位置到最后一个位置+1（这里的n就表示当前List中的元素个数）。所以我们就会发现我们在插入数据后，这些数据都是连续的。比如：在创建了List之后，数组中没有元素，元素个数为0，那么此时插入的范围就是1}0+1，只有1这个位置可以插入，之后再插入第二个元素，这时元素的个数已经变成了1，此时的范围是1~1+1，以此类推，存储在这个线性表中的数据总会是连续的。

image

​ 当我们向线性表中插入数据时，首先要看看这个线性表满了没有，如果满了不能插入，判断满的条件就是：last==data.length-1如果最后一个元素的下标等于数组的最后一个下标，说明满了。

​ 然后，要判断插入的位置是否合法：i < 1 || i > last+2(n+1 >= i >= 1)。

​ 之前说过，List中存储的数据是连续的，所以我们插入时不能直接插入，需要将元素往后挪出一个空位才能够在特定的位置进行插入：

// 挪动的顺序毫无疑问是从最后一个元素挪，否则你从第i个元素挪的话就会覆盖掉后面的元素
for (int j=last; j>=i-1; j--){
    data[j+1] = data[j];
}
// 插入数据
data[i-1] = item;
// last加1
last = last + 1;

删除元素

​ 和插入元素类似，只是挪动元素是往前挪动元素，填补删除后留下的空位。直接上代码：

// 如果List空，不能删除
if (isEmpty()){
    System.out.println("List为空，不能删除");
}
// 规定的删除位置在1~n+1
if (i < 1 || i > last+2){
    System.out.println("删除位置非法，无法插入!");
}
// 在删除之后需要先将数据往前挪
for (int j=i-1; j<last; j++){
    data[j] = data[j+1];
}
last = last - 1;

完整代码：

public class List<Item> {
    // Java不允许创建泛型数组，所以做强制类型转换
    private Item[] data;
    private int last = -1; // 表示List中最后一个元素的下标

    // 构造函数-创建List时指定大小
    public List(int size){
        data = (Item[]) new Object[size];
    }

    // List是否为空
    public boolean isEmpty(){
        return last==-1;
    }

    // 返回List的大小
    public int size(){
        return last+1;
    }

    // 在第i个位置插入数据(即插入到数组下标为i-1这个位置)
    public void insert(Item item, int i){
        // 如果List满了，不能插入
        if (last==data.length-1){
            System.out.println("数组满，无法插入!");
        }
        // 规定的插入位置在1~n+1之间
        if (i < 1 || i > last+2){
            System.out.println("插入位置非法，无法插入!");
        }
        // 在插入之前需要先将数据往后挪
        for (int j=last; j>=i-1; j--){
            data[j+1] = data[j];
        }
        data[i-1] = item;
        last = last + 1;
    }

    // 在第i个位置删除数据(即删除数组下标为i-1这个位置)
    public void delete(int i){
        // 如果List空，不能删除
        if (isEmpty()){
            System.out.println("List为空，不能删除");
        }
        // 规定的删除位置在1~n+1
        if (i < 1 || i > last+2){
            System.out.println("删除位置非法，无法插入!");
        }
        // 在删除之后需要先将数据往前挪
        for (int j=i-1; j<last; j++){
            data[j] = data[j+1];
        }
        last = last - 1;
    }

    // 查找某个元素，如果查找到，返回下标，否则返回-1
    public int find(Item item){
        for (int i=0; i<last+1; i++){
            if (data[i]==item){
                return i;
            }
        }
        return -1;
    }

    public void printData(){
        for (Item item:data){
            System.out.print(" " + item);
        }
        System.out.println("");
    }

    // 测试
    public static void main(String[] args) {
        List<Integer> testList = new List(5);
        testList.insert(1,1);
        testList.insert(2,2);
        testList.insert(3,3);
        testList.insert(4,4);
        testList.insert(5,5);
        testList.printData();
        testList.delete(1);
        testList.printData();
        System.out.println(testList.find(3));
    }
}

链式存储实现

​ 创建一个泛型类 LinkedList：

public class LinkedList<Item> {
    private Node head; // 线性表的表头（链表的入口）
    private int N; // 结点的数量（线性表中的元素数量）

    // node结点类
    private class Node{
        Item item;
        Node next;
        // 构造器
        public Node(Item item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
}

​ 求线性表的长度和是否为空：

public int length(){
    return N;
}

public boolean isEmpty(){
    return head==null; // 当head为null或N为0
}

​ 查找相应的位置的结点：

public Node findXth(int X){
    Node temp = head;
    int i = 1;
    // 当当前结点不为空且位置小于X时
    while (temp != null && i < X){
        temp = temp.next;
        i = i+1;
    }
    // 跳出循环有两种可能，当前结点为空或i==X
    if (i == X){
        return temp;
    } else{
        return null;
    }
}

插入数据

​ 因为是链式存储，所以不必关心空间的问题，只需care插入问题。

​ 要向链表中插入结点，首先要分插入的位置。如果是插到链表的头，需要做特殊处理：让插入结点的next的值变为head，head的值置为新插入的结点；如果插入到其他位置，只需要先找到插入位置的前一个结点p，然后是两步（顺序不能更改）：1、设置插入的结点的next的值为p的next。2、改变p的next的值为插入的结点。

public void insert(int i, Item item){
    Node temp, p;
    if (i == 1){
        temp = new Node(item, head);
        head = temp;
        N = N+1;
        return;
    }
    p = findXth(i-1);
    if (p == null){
        System.out.println("参数i错误!");
        return;
    } else{
        temp = new Node(item, p.next);
        p.next = temp;
        N = N+1;
        return;
    }
}

删除数据

​ 和插入类似，区分删除的是头结点还是其他位置，删除头结点：只需head置为head的next；删除其他结点：找到前一个结点p，使其next置为p.next.next即可，java会自动进行垃圾回收。

public void delete(int i){
    Node p;
    if (i == 1){
        if (head == null){
            System.out.println("链表为空!");
            return;
        } else{
            head = head.next;
            N = N-1;
            return;
        }
    }
    p = findXth(i-1);
    if (p == null || p.next == null){
        System.out.println("第i个结点不存在!");
    } else {
        p.next = p.next.next;
        N = N-1;
    }
}