基本数据结构底层原理——线性存储和链式存储_什么是线性存储

线性存储

线性存储指的是顺序表，其底层原理通过数组来实现。数组中的元素是有序的，通过下标访问。对于需要频繁访问使用的元素，使用顺序表的效率非常之高。

顺序表的优缺点

优点：

• 顺序表有序，访问顺序表中的数据很快。

缺点：

• 由于底层由数组实现，每当分配的空间用完后都需要扩容，而对于未使用的空间，也是一种浪费。

• 进行插入和删除操作的效率很低，因为可能需要挪动大量的元素。

模拟实现顺序表

public class MyArraylist {
 
    public int[] elem;
    public int usedSize;//0
    //默认容量
    private static final int DEFAULT_SIZE = 10;
 
    public MyArraylist() {
        this.elem = new int[DEFAULT_SIZE];
    }
 
    /**
     * 打印顺序表:
     * 根据usedSize判断即可
     */
    public void display() {
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(this.elem[i] + " ");
        }
        System.out.println();
    }
 
    // 新增元素,默认在数组最后新增
    public void add(int data) {
        //判断
        if (isFull()) {
            //扩容
            this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);
        }
        this.elem[this.usedSize] = data;
        this.usedSize++;
    }
 
    /**
     * 判断当前的顺序表是不是满的！
     *
     * @return true:满   false代表空
     */
    public boolean isFull() {
        return this.usedSize == this.elem.length;
    }
 
 
    private boolean checkPosInAdd(int pos) {
        //判断
        if (pos < 0 || pos > this.usedSize)
            return false;
        return true;//合法
    }
 
    // 在 pos 位置新增元素
    public void add(int pos, int data) {
        if (checkPosInAdd(pos)) {
            if (isFull()) {
                //扩容
                this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);
            }
            // 1 2 3 4 5  pos: 2 -> 99
            // 1 2  99 3 4 5
            for (int i = this.usedSize; i > pos; i--) {
                this.elem[i] = this.elem[i - 1];
            }
            this.elem[pos] = data;
            this.usedSize++;
        }
 
    }
 
    // 判定是否包含某个元素
    public boolean contains(int toFind) {
        for (int i = 0; i < this.usedSize; i++) {
            if (this.elem[i] == toFind) {
                return true;
            }
        }
        return false;
    }
 
    // 查找某个元素对应的位置
    public int indexOf(int toFind) {
        for (int i = 0; i < this.usedSize; i++) {
            if (this.elem[i] == toFind) {
                return i;
            }
        }
        return -1;
    }
 
    private void checkIndex(int pos) {
        if (pos < 0 || pos >= this.usedSize) {
            //该异常需要自定义
            throw new IndexOutOfException("位置输入不合法！");
        }
    }
 
    // 获取 pos 位置的元素
    public int get(int pos) {
        //判断
        try {
            checkIndex(pos);
        } catch (IndexOutOfException e) {
            e.printStackTrace();
        }
        return this.elem[pos];
    }
 
    private boolean isEmpty() {
        if (this.usedSize == 0) {
            return true;
        }
        return false;
    }
 
    // 给 pos 位置的元素设为【更新为】 value
    public void set(int pos, int value) {
        //判断
        try {
            checkIndex(pos);
        } catch (IndexOutOfException e) {
            e.printStackTrace();
        }
        this.elem[pos] = value;
    }
 
    /**
     * 删除第一次出现的关键字key
     *
     * @param key
     */
    public void remove(int key) {
        //查找位置
        int index = indexOf(key);
        if (index == -1) {
            System.out.println("没有找到这个数据！");
            return;
        }
        for (int i = index; i < this.usedSize - 1; i++) {
            this.elem[i] = this.elem[i + 1];
        }
        this.usedSize--;
    }
 
    // 获取顺序表长度
    public int size() {
        return this.usedSize;
    }
 
    // 清空顺序表
    public void clear() {
        this.usedSize = 0;
    }
 
}

链式存储

链式存储主要指链表，链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

链表有一个个结点连接而成，每个结点都存储着一定的信息，它可以包含存放的数据信息，下一个结点的地址和上一个结点的地址。通过这些地址可以访问到下一个结点，从而实现链式访问。

根据链表中结点所包含的信息不同，链表可以是单向或者双向，可以是循环或者非循环。除此之外，链表可以带头或者不带头。因此链表可以分为8种，其中，以单向不带头非循环链表和双向不带头非循环链表为主。

链表的优缺点

优点：

链表不需要初始化，直接添加元素即可。

对于增删操作，只需更改前一个结点和后一个结点的指向即可。

缺点：

查找元素只能通过遍历来实现，耗时较多。对于单链表，不能后退，如果必须得到该结点和上一个结点，必须在遍历到上一个结点时记录下来。

链表的模拟实现（单链表）

// 1、无头单向非循环链表实现
public class SingleLinkedList {
    static class ListNode {
        public int val;
        public ListNode next;
 
        public ListNode() {
        }
 
        public ListNode(int val) {
            this.val = val;
        }
 
        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
    public ListNode head;
 
    //头插法
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        node.next = head;
        head = node;
    }
    //尾插法
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        if (head == null) {
            head = node;
            return;
        }
        ListNode cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }
    private Boolean checkIndex(int index) {
        return index >= 0 && index <= size();
    }
    private ListNode findIndex(int index) {
        ListNode cur = head;
        int count = 0;
        while (count < index - 1) {
            cur = cur.next;
            count++;
        }
        return cur;
    }
    //任意位置插入,第一个数据节点为0号下标
    public boolean addIndex(int index,int data) {
        if (!checkIndex(index)) {
            return false;
        }
        if (index == 0) {
            addFirst(data);
            return true;
        }else if (index == size()) {
            addLast(data);
            return true;
        }
        ListNode cur = findIndex(index);
        ListNode node = new ListNode(data);
        node.next = cur.next;
        cur.next = node;
        return true;
    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key) {
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    private ListNode findPrevNode(int key) {
        ListNode cur = head;
        while (cur.next != null) {
            if (cur.next.val == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }
    //删除第一次出现关键字为key的节点
    public void remove(int key) {
        if (head == null) {
            return;
        }
        if (head.val == key) {
            head = head.next;
            return;
        }
        ListNode cur = findPrevNode(key);
        if (cur == null) {
            return;
        }
        cur.next = cur.next.next;
    }
 
    //删除所有值为key的节点
    public void removeAllKey(int key) {
        if (head == null) {
            return;
        }
        ListNode p = head;
        ListNode q = head.next;
        while (q != null) {
            if (q.val == key) {
                p.next = q.next;
            }else {
                p = q;
            }
            q = q.next;
        }
        if (head.val == key) {
            head = head.next;
        }
    }
    //得到单链表的长度
    public int size() {
        int count = 0;
        ListNode cur = head;
        while (cur != null) {
            cur = cur.next;
            count++;
        }
        return count;
    }
    public void display() {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
    public void display(ListNode head) {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
 
        public void clear() {
        head = null;
    }
}

Java的数据结构题一般只涉及到单链表，而Java底层实现的链表是双向链表。

栈和队列

栈和队列底层由顺序表实现，栈和队列大体上是相似的，都具有以下特点：

• 增删操作都在栈顶（队头）

• 每次增删或者访问都只能操作一个元素。

二者的区别在于：

栈的逻辑是“先进后出“，而队列是”先进先出“；

栈的实现就像是往箱子里放东西，最先放进去的东西，等到要拿出来的时候，总是最后一个拿出来。

而队列的实现就像去食堂排队打饭，只有排你前面的人都打好饭才能轮到你。

栈和队列具有的功能较少，栈的功能有：push()->入栈，pop()->出栈，peek()->查看栈顶元素，empty()->判空，search->查找等，队列功能有：offer()->入队列，poll()->出队列，peek->查看队头元素等。

当然，除了普通队列以外，还存在双端队列Deque，双端队列不局限于先进先出，它可以在队头或者队尾进，也可以在队头或者队尾出，没有限制。

栈和队列的实现不仅仅可以通过顺序表，也可以通过链表实现，也就是所谓的链式栈和链式队列。而实际上，Java底层自己实现的链表中就包含了栈和队列的所有方法，也就是说链表不单单是链表，它也可以是栈，也可以是队列。

当然，为了方便识别所创建的链表是普通的链表，还是栈或者队列，通常需要更改变量名。

栈和队列有着相似的特点，因此栈可以模拟实现队列，队列也可以模拟实现栈：

用队列实现栈

用栈实现队列