单链表的增删改查

单链表： 是一种链式存取的数据结构，用一组任意地址空间（即存储单元）来存放线性表的数据元素。单链表中的每个数据都以节点的形式来表示，每个节点都是由值域及指针next域构成，其中值域保存当前节点的数据值，next域保存下个节点的地址。

单链表的结构如下所示：（以不带头节点为例）

下面简单介绍下链表“增删改查”的原理(附代码)：
（1）头插： 将新节点newEntry的next域链接到头节点的地址中，同时更新头节点

public void addHead(E value) {
        Entry<E> newEntry = new Entry(value);
        if (headEntry == null) {
            headEntry = newEntry;
            tailEntry = newEntry;
        } else {
            newEntry.next=headEntry;
            headEntry = newEntry;//用newEntry更新headEntry，使newEntry变为新的头节点，尾部节点不做改动
        }
    }

（2）尾插： 将尾节点tailEntry的next域链接到新节点的地址中，同时更新尾节点

public void addTail(E value) {
        Entry<E> newEntry = new Entry(value);
        if (headEntry == null) {
            headEntry = newEntry;
            tailEntry = newEntry;
        } else {
            tailEntry.next=newEntry;
            tailEntry = newEntry;
        }
    }

（3）头删： 头节点的value域置空以防止内存泄漏，将其下个节点的地址更新为新的头节点

public void removeHead() {
        if (headEntry == null) {
            return;
        }
        headEntry.value=null;//防止内存泄漏
        headEntry = headEntry.next;
    }

（4）尾删： 遍历整个链表，标记尾部前驱节点，将前驱节点的next域置空，同时更新尾节点

public void removeTail() {
        if (headEntry == null) {
            return;
        } else if (headEntry.next== null) {//只有一个节点
            headEntry = null;
            tailEntry = null;
            return;
        } else { //尾删时需要找到尾结点前驱，将前驱节点的next域置空即找实现尾删
            Entry<E> beforeEntry=headEntry;
            for(;beforeEntry.next.next!=null;beforeEntry=beforeEntry.next){
                ;
            }
            tailEntry.value=null;//防止内存泄漏
            beforeEntry.next=null;  //将尾结点置空
            tailEntry=beforeEntry;
        }
    }

（5）删除指定元素： 遍历链表找到与指定元素值相同的元素value，将value前一个节点的next域指向value下一个元素的地址

public void removeValue(E value) {
        if (headEntry == null) {
            return;
        }
        if (headEntry.value.compareTo(value)==0) {  //指定元素恰为头节点
            removeHead();
        }
        if(tailEntry.value.compareTo(value)==0){    //指定元素恰为尾节点
            removeTail();
        }
        for (Entry<E> p = headEntry; p.next.next!= null; p = p.next) {
            if(p.next.value.compareTo(value)==0){
                p.next.value=null;
                p.next=p.next.next;
                break;
            }
        }
    }

不带头节点的双向单链表结构如下：

双向单链表的增删改查与上面的原理对应无基本差别，但要分析时记得 更新前驱 pro