[数据结构与算法]Java实现顺序表与链表

Java顺序表与链表

AbstractList,下面两种数据结构基于这个抽象类修改完成

package 数据结构.线性表;//@date :2022/2/5 18:04

public abstract class AbstractList<E> {
    public abstract int size();

    public abstract void add(E e, int index);

    public abstract E pop(int index);

    public abstract E get(int index);
}

将数据依次存储在连续的整块物理空间中，这种存储结构称为顺序存储结构，而以这种方式实现的线性表，我们称为顺序表。

同样的，表中的每一个个体都被称为元素，元素左边的元素（上一个元素），称为前驱，同理，右边的元素（后一个元素）称为后驱

我们设计线性表的目标就是为了去更好地管理我们的数据，也就是说，我们可以基于数组，来进行封装，实现增删改查！既然要存储一组数据，那么很容易联想到我们之前学过的数组，数组就能够容纳一组同类型的数据。

Java实现

ArrayList

package 数据结构.线性表;//@date :2022/2/5 18:08

public class ArrayList<E> extends AbstractList<E> {
    //底层数组
    private Object[] arr = new Object[0];
    //数组长度
    private int size = 0;

    @Override
    public int size() {
        return size;
    }

    @Override
    public void add(E e, int index) {  //插入元素到arr[index]
        if (index < 0 || index > size) throw new IllegalArgumentException("非法的位置参数");
        if (size >= this.arr.length) {
            Object[] arr = new Object[this.arr.length + 10];   //每次扩容+10
            for (int i = 0; i < this.arr.length; i++) arr[i] = this.arr[i];  //把以前的数据放入新建的数组
            this.arr = arr;  //将扩容后的新数组赋值到arr
        }

        int i = size - 1;
        while (i >= index) {
            this.arr[i + 1] = this.arr[i];
            i--;
        }
        arr[index] = e;
        size++;
    }

    public void add(E e) {  //插入元素在arr[0]
        if (size >= arr.length) {
            Object[] arr = new Object[this.arr.length + 10];   //每次扩容+10
            for (int i = 0; i < this.arr.length; i++) arr[i] = this.arr[i];  //把以前的数据放入新建的数组
            this.arr = arr;  //将扩容后的新数组赋值到arr
        }
        int i = size - 1;
        while (i >= 0) {
            this.arr[i + 1] = this.arr[i];
            i--;
        }
        arr[0] = e;
        size++;
    }


    @Override
    public E pop(int index) {
        if (index > size - 1) throw new IllegalArgumentException("非法的参数位置");

        E e = (E) arr[index];
        int i = index;
        while (i < size) {
            arr[i] = arr[i + 1];
            i++;
        }

        size--;
        return e;
    }

    @Override
    public E get(int index) {
        if (index > size - 1 || index < 0) throw new IllegalArgumentException("非法的参数位置");
        return (E) arr[index];
    }
}

数据分散的存储在物理空间中，通过一根线保存着它们之间的逻辑关系，这种存储结构称为链式存储结构

实际上，就是每一个结点存放一个元素和一个指向下一个结点的引用（C语言里面是指针，Java中就是对象的引用，代表下一个结点对象）

LinkedList

package 数据结构.线性表;//@date :2022/2/5 20:52

public class LinkedList<T> extends AbstractList<T> {

    private Node<T> head = new Node<>(null);   //头结点
    private int size = 0;

    private static class Node<T> {
        private T t;
        private Node<T> next;

        public Node(T t) {
            this.t = t;
        }
    }

    @Override
    public int size() {
        return size;
    }


    //  head -> node1 -> node2 -> node3
    //在第3的位置插入node0
    //  head -> node1 -> node2 -> node0 -> node3
    @Override
    public void add(T t, int index) {  //将元素插入到指定位置
        if (index > size) throw new IllegalArgumentException("非法的位置参数");
        Node<T> node = head;//创建头结点
        Node<T> temp;  //存放中间节点
        for (int i = 0; i < index; i++) node = node.next;    //定位到index节点,因为有头结点的存在,头结点不存放数据
        temp = node.next;  //将index的节点存放在temp中,
        node.next = new Node<>(t);  //创建一个新节点作为index-1节点的后驱节点
        node.next.next = temp;  //把原本index节点作为  index-1节点的后驱的后驱也就是,新节点的后驱,

        size++;
    }

    public void add(T t) {    //头插发
        Node<T> node = head;
        Node<T> temp;
        temp = head.next;
        head.next = new Node<>(t);
        head.next.next = temp;
        size++;
    }
    //  head -> node1 -> node2 -> node3
    //删除第3的位置的node
    //  head -> node1 -> node3
    @Override
    public T pop(int index) {
        if (index > size) throw new IllegalArgumentException("非法的位置参数");
        Node<T> node = head, pop;
        for (int i = 0; i < index; i++) node = node.next;  //定位到要删除节点的前驱
        System.out.println(node.t);
        pop = node.next;
        node.next = node.next.next;

        return pop.t;
    }

    @Override
    public T get(int index) {
        if (index > size) throw new IllegalArgumentException("非法的位置参数");
        Node<T> node = head;
        for (int i = 0; i <= 3; i++) {
            node = node.next;
        }
        return node.t;
    }
}