我们每天做着和昨天一样的事情，却又希望明天的结果与今天不一样。呵呵！！！前言

程序 = 数据结构 + 算法。其重要性不言而喻，不多说，直接进入正题。

线性表是由零个或多个元素组成的有限序列，通俗来说就是具有线性一样的性质----好家伙，说了跟没说一样。

线性表从存储方式来看可以分为顺序存储与链式存储。顺序表有几个基础操作，插入，删除，及查询。当然，还有一些很多其它的操作，为了简单，本例将通过代码实现顺序存储与链式存储。

一、顺序存储

如下图，按照顺序存储下去，一般采用数组实现

插入：

​

删除：

第一步，将待删除数据删除

第二步，将后面数据往前挪

查询：

可直接通过索引位置查询。

不多说，直接上代码。

public class ZListImpl implements ZList {    // 数据集合    private ZElement[] datas;    // 数组最大长度    private final int maxLength;    /**     * 数组初始长度为0     */    private int length = 0;    public ZListImpl(int maxLength) {        this.maxLength = maxLength;        this.datas = new ZElement[maxLength];    }    @Override    public void delete(int index) {        if (index < 0 || index > length - 1) {            System.err.println("index越界");        }        // 当前索引位置数据后面的往前挪一位        for (int i = index; i < length; i++) {            datas[i] = datas[i+1];        }        //数组长度减一        length--;    }    @Override    public void add(ZElement zElement) {        // 不允许插入空值        if (zElement.getData() == null) {            return;        }        // 当前数组长度大于最大长度，暂不支持动态扩容        if (length >= maxLength) {            System.err.println("该链表数据已满");        }        datas[length] = zElement;        // 数组长度增加        length++;    }    @Override    public int getId(ZElement element) {        // -1 表示不存在该元素        if (element.getData() == null) {            return -1;        }        // 如果有多个元素匹配，返回第一个索引值        for (int i = 0; i < length; i++) {            if (datas[i].getData().equals(element.getData())) {                return i;            }        }        return -1;    }    @Override    public int length() {        return length;    }}

链式存储的特性节点信息存储着两部分内容，数据与上/下一个节点的地址，这里以单链表为例。

插入，画的略显粗糙

如图，我们要在节点2后面插入5，需要将节点5的后继指向节点2下一个节点-即3，然后再将节点2和后继节点指向5，完成插入操作

​

删除

第一步，当前节点的后继节点指向待删除节点的后继节点

第二步，。。。。，对没有了

查询

使用游标，从头节点开始，如果查询不到，游标往后走，遍历到下一个节点，直到查询到数据或全部链表查询完成。

代码如下（删除的代码）

import javax.xml.soap.Node;public class ZLinkImpl implements ZLinkInterface {    // 初始化头节点    ZNode head = null;    // 链表长度    public int size = 0;    @Override    public void add(String target, String data) {        ZNode targetNode = get(target);        if (targetNode == null) {            add(data);        } else {            ZNode zNode = new ZNode(data);            zNode.setNext(targetNode.getNext());            targetNode.setNext(zNode);            size++;        }    }    @Override    public void delete(String data) {        ZNode pNode = getPreNode(data);        ZNode next = pNode.getNext();        // 不是最后一个节点        if (next != null) {            // 上一节点数据指向当前节点的下一个节点            pNode.setNext(next.getNext());        } else {            pNode.setNext(null);        }        this.size--;    }    @Override    public ZNode get(String data) {        if (this.size != 0 && data != null) {            ZNode next = head;            while (next != null) {                if (data.equals(next.getData())) {                    return next;                } else {                    next = next.getNext();                }            }        }        return null;    }    public ZNode getPreNode(String data) {        if (this.size != 0 && data != null) {            ZNode next = head.getNext();            while (next != null) {                if (data.equals(next.getNext().getData())) {                    return next;                } else {                    next = next.getNext();                }            }        }        return null;    }    // 没有目标，采用尾插法插入到链表最后    public void add(String data) {        // 当前链表为空        if (this.size == 0) {            head = new ZNode(data);        } else {            // 当前链表游标，获取链表最后游标            ZNode thisCur = head;            while (thisCur != null && thisCur.getNext() != null) {                thisCur = thisCur.getNext();            }            // 待插入链表插入到当前节点后面            ZNode willNode = new ZNode(data);            thisCur.setNext(willNode);        }        size++;    }}

主类

public class ZLinkMain {    public static void main(String[] args) {        ZLinkImpl zLink = new ZLinkImpl();        zLink.add("1");        zLink.add("2");        zLink.add("3");        zLink.add("4");        zLink.add("2","5");        System.out.println(zLink.size);    }}

调试看到的结果 1 -> 2 -> 5- > 3 ->4

​

三、总结

顺序存储相对于链式存储来说

优点：快速存取元素，无需记录元素关联的数据

缺点：数据碎片化，插入删除效率较低

当然，其实里面还有一些bug以及很多设计的不完善的地方，最完整的代码可以看看jdk List集合的源码，里面有各种各样的api，例如倒置，两个线性表之间 操作，底层还有自动扩容等，都是需要我们大量时间去研究和学习的，话说回来，理解了与写代码是两回事儿。

还有快慢指针（可用来查询链表中间值），静态链表（数组实现了链式存储，虽然现在基本上不用，其中的思考方式值得我们学习），约瑟夫算法以及魔术师发牌的实现，有机会我会把这几个算法整理一下发出来。从一个学习者来说，我已经懂了，如果要结合代码将这个问题讲清楚，我还得再学习，反之，如果我能把这些问题全部都写出来，那我肯定掌握了这些内容，这也是我写文章的初衷。最后，希望大家做时间的朋友，共勉。最最后附上代码地址。