[数据结构与算法]单链表的增、删、改、查操作

?

• 定义一个接口，里面包含?增、删、改、查等操作

public interface List<E> {
    void addHead(E value);

    void addTail(E value);

    void removeHead();

    void removeTail();

    void removeValue(E value);

    void change(E srcValue, E aimValue);

    boolean contains(E value);

    void show();

}

• ?定义SingLink类，继承以上该接口，并进行类型限定，对链表进行初始化，将链表的头和尾都置为空。
• <T extends 基接口>：T只能是实现基接口的派生类。

public class SingleLink<E extends Comparable> implements List<E> {
    private Node<E> head;   //标记头部位置
    private Node<E> tail;  // 尾部位置  ，尾插时间复杂度O(1)
    private int size;

    public SingleLink() {
        this.head = null;    //链表为空
        this.tail = null;
    }

• ?实现List接口，所以其中的方法需要重写 @Override
• 头部增加操作addHead ，首先判断链表是否为空，若为空，将头和尾都为添加的节点，否则，原来的头变为新节点的下一个节点，新节点变为头。

@Override
    public void addHead(E value) {    // 时间复杂度 O(1)
        Node<E> node = new Node<>(value);
        if (head == null) {
            head = node;
            tail = node;
        } else {
            node.next = head;  //新节点下一个指向head
            head = node;   // 更新头部
        }
        size ++;
    }

• 尾部添加操作 addTail ，同上，首先判断链表是否为空，若为空，将头和尾都为添加的节点，否则，直接是尾部的next修改为新节点，尾部变为新节点。

public void addTail(E value) {  //时间复杂度O(1)

        Node<E> node = new Node<>(value);//1.申请value节点
        if (head == null) {   // 头尾维护
            head = node;
            tail = node;
        } else {
            tail.next = node;
            tail = node;
        }
        size++;

    }

• 头部删除操作 removeHead ，?首先判断链表是否为空，若为空，直接return即可；再判断链表是否只有一个节点，若只有一个，将尾巴置为null；否则，头部指向原来头部的下一个节点，头部的value和next为空，防止内存泄漏。

 public void removeHead() {

        if (head == null) {
            return;
        } else if (head.next == null) {  //只有一个节点
            tail = null;
        }
        head.value = null;  // 防止内存泄露
        Node<E> p = head.next;
        head.next = null;
        head = p;
        size--;
    }

• 尾部删除操作 removeTail ，首先判断链表是否为空，若为空，直接return即可；再判断链表是否只有一个节点，若只有一个，head.value、head、tail都置为null；否则，定义一个新节点，从head开始遍历，找的尾巴的前一个节点，使前一个结点成为新尾巴，新尾巴的next 置为null，尾巴的value置为null，

 public void removeTail() {
        if (head == null) { //链表为空
            return;
        } else if (head.next == null) {  //链表只有一个节点  下述循环中无法遍历到head
            head.value = null;
            head = null;
            tail = null;
        } else {   //>=两个节点
            Node<E> p = head;
            for (; p.next.next != null; p = p.next) { // p.next 尾巴节点的next为空，要找到尾巴节点的上一个，就要以p.next.next为条件，即p为尾巴的前一个
                ;
            }
            p.next = null;
            tail.value = null;
            tail = p;
        }
        size--;
    }

• ?删除指定节点 removeValue? ，首先，判断链表是否为空，若为空，直接return即可；在判断头结点的值是否是要找的，若是，进行头删操作；从head .?next进行循环，找到要删除的节点进行贯穿，使得p. next = p.next.next;为防止内存泄漏，使待删节点的value为空。
• 要删除待删节点，需知道待删节点的前一个节点，所以从p.next出发，无法遍历head，则单独进行比较。

public void removeValue(E value) {
        if (head == null) {
            return;
        } else if (head.value.compareTo(value) == 0) {  // 引用数据类型用compareTo进行比较
            removeHead();
        } else {
            Node<E> p = head;
            for (; p.next.value.compareTo(value) != 0; p = p.next) {  //越过头
                ;
            }
            p.next.value = null;  //防止内存泄漏
            p.next = p.next.next;
        }
        size--;
    }

• ?改 change ，从头开始遍历，找到待改的节点，将其value改为目标value即可。

for (Node<E> p = head; p != null; p = p.next) {
            if (p.value.compareTo(srcValue) == 0) {
                p.value = aimValue;
            }
        }
    }

• ?查找 contains ，从head开始遍历，找到待查找的节点，如找到，返回true；若没有，循环结束，返回false。

public boolean contains(E value) {
        for (Node<E> p = head; p != null; p = p.next) {
            if (p.value.compareTo(value) == 0) {
                return true;
            }
        }
        return false;
    }

?