无头非循环双向链表的增删查改

1、头插法：
思路：首先判断链表是否是第一次插入；不是就直接将其前驱、后继进行相应的“变换”！
代码：

class Node{
    private int data;//数据域
    private Node pre;//前驱
    private Node next;//后继
    //构造方法
    public Node(int data) {
        this.data = data;
        this.next = null;
        this.pre = null;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node getPre() {
        return pre;
    }

    public void setPre(Node pre) {
        this.pre = pre;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}
public class DoubleLinkedList {
    private Node head;
    private Node last;
    //头插法：
    public void addFirst(int data){
        //产生一个要插入的节点
        Node node = new Node(data);
        //1、判断链表是否为空
        if(this.head == null){
            this.head = node;
            this.last = node;
            return;
        }
        //不为空时：
        node.setNext(head);
        this.head.setPre(node);
        this.head = node;
    }
    //打印该链表
    public void display(){
        Node cur = this.head;
        while(cur != null){
            System.out.print(cur.getData() + " ");
            cur = cur.getNext();
        }
        System.out.println();
    }
}
测试类：
public class TestDemo {
    public static void main(String[] args) {
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        doubleLinkedList.addFirst(10);
        doubleLinkedList.addFirst(20);
        doubleLinkedList.addFirst(30);
        doubleLinkedList.addFirst(40);
        doubleLinkedList.display();
    }
}
输出结果：40 30 20 10

2、尾插法：
思路：判断是否是第一次插入；不是首次插入就直接在表尾插入新的数值，并修改前驱和后继！
代码：

//尾插法
    public void addLast(int data) {
        Node node = new Node(data);
        //首次插入
        if(this.head == null){
            this.head = node;
            this.last = node;
            return;
        }
        Node cur = this.head;
        //找当前单链表的尾巴
        while(cur.getNext() != null){
            cur = cur.getNext();
        }
        cur.setNext(node);
        node.setPre(cur);
        this.last = node;
    }
}

3、在任意位置插入key值
思路：先判断位置是否合法；再判断是否为第一次插入或者在尾部插入，并调用相应的方法；关键在于寻找“插入位置”！
代码：

//求单链表的长度
    public int size(){
        Node cur = this.head;
        int count = 0;
        while(cur != null){
            count++;
            cur = cur.getNext();
        }
        return count;
    }
    //寻找index位置
    public Node findIndex(int index){
        Node cur = this.head;
        while(index >0 ){
            cur = cur.getNext();
            index--;
        }
        return cur;
    }
    //在index位置插入key
    public void addIndex(int index,int key){
        //判断index位置是否合法
        if(index <0 || index>size()){
            throw new RuntimeException("index位置不合法！");
        }
        //首次插入
        if(index == 0){
            addFirst(key);
            return;
        }
        //尾部插入
        if(index == size()){
            addLast(key);
            return;
        }
        //任意合法位置插入
        //定义cur表示走到index位置
        Node cur = findIndex(index);
        Node node = new Node(key);
        node.setNext(cur);
        node.setPre(cur.getPre());
        cur.setPre(node);
        node.getPre().setNext(node);

    }

}

4、链表中是否包含某个关键字：
思路：遍历链表，看是否存在某位置的data==关键字，找到则返回true，否则返回false；
代码：

//判断链表中是否包含某个关键字
public boolean contains(int key){
        Node cur = this.head;
        //遍历链表
        while(cur != null){
            if(cur.getData() == key){
                return true;
            }
            cur = cur.getNext();
        }
        return false;
    }

5、删除链表中的某个第一次出现的关键字对应的节点
思路：判断删除的是否是头节点，给出相应的删除操作；然后考虑怎么删除其他节点，最后处理“尾巴”！
代码：

 public void delete(int key){
        //cur表示要删除的节点
        Node cur = this.head;
        while(cur != null){
            if(cur.getData() == key){
                //判断当前节点是否为头节点
                if(this.head.getData() == key) {
                    this.head = this.head.getNext();
                    this.head.setPre(null);
                }
            else  {
                    cur.getPre().setNext(cur.getNext());
                    if (cur.getNext() != null) {
                        cur.getNext().setPre(cur.getPre());
                    } else {
                        this.last = cur.getPre();
                    }
                }
                return;
            }
            cur = cur.getNext();
        }
    }

6、删除所有关键字为key的节点：
代码：

 public void allDelete(int key){
        //cur表示要删除的节点
        Node cur = this.head;
        while(cur != null){
            if(cur.getData() == key) {
                //判断当前节点是否为头节点
                if (this.head.getData() == key) {
                    this.head = this.head.getNext();
                    this.head.setPre(null);
                } else {
                    cur.getPre().setNext(cur.getNext());
                    if (cur.getNext() != null) {
                        cur.getNext().setPre(cur.getPre());
                    } else {
                        this.last = cur.getPre();
                    }
                }
            }
            cur = cur.getNext();
        }
    }
}

7、清空链表
思路：头尾制空法

public void clear(){
        this.head = null;
        this.last = null;
    }