Java -线性表——单链表（包含增删查改CURD）

Java -线性表——单链表（包含增删查改CURD）

1.无头单链表（无虚拟头结点）

package seqlist;

import com.sun.media.sound.RIFFInvalidDataException;
import sun.awt.image.GifImageDecoder;

class  Node{
    int data;
    Node next;
    public Node(int data){this.data = data;}
    public Node(int data, Node next){
        this.data = data;
        this.next = next;
    }
}
public class SinglelinkList {
    private int size;
    private Node head;


    //addFirst
    public void addFirst(int data) {
        if (size == 0) {
            Node node = new Node(data);
            head = node;
            size ++;
        } else {
            Node node = new Node(data);
            node.next = head;
            head = node;
            size ++;
        }
    }

    //addIndex 1.0(prev前驱结点）
    public void addIndex(int index, int data) {
        if (index < 0 || index > size) {
            System.err.println("illegal!!");
            return;
        }
        if (index == 0) {
            addFirst(data);
            return;
        }
        Node node = new Node(data);
        Node prev = head;
        for (int i = 0; i < index - 1; i++) {
            prev = prev.next;
        }
        node.next = prev.next;
        prev.next = node;
        size++;
    }
   

有虚拟头结点{直接代入上述完整单链表即可解决问题}（方便做题）{方法代码块}

1.在index位置传入新的数值data（addIndex2）

    //addIndex 2.0(接入虚拟头结点）
    public Node addIndex2(int index,int data){
        if (index < 0 || index > size){
            System.err.println("illegal!!!");
            return null;
        }
        //设置一个虚拟头
        Node dummyHead = new Node(-1);
        //dummyhead 需要传入链表
        dummyHead.next = head;

        Node prev = dummyHead;
        //找到prev的前驱结点
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        //进行传值交换
        Node node = new Node(data);
        node.next = prev.next;
        prev.next = node;
        size ++;
        head = dummyHead.next;
        return dummyHead.next;
    }

2.在index位置删除（removeIndex2）

//有虚拟头结点
    public void removeIndex2 (int index){
        //边界条件
        if (index < 0 || index >= size){
            System.err.println("illegal!!!");
            return;
        }
        //传入一个虚拟头
        Node dummyHead = new Node(-1);//-1 无意义
        dummyHead.next = head;
        Node prev = dummyHead;
        //转移到prev结点
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        //进行移除工作
        Node node = prev.next;
        prev.next = node.next;
        node.next = null;
        size --;
        return ;
    }

3.删除值为value 的值（removevalue）

 //虚拟头节点法
    public Node removevalue2( int val) {
        //定义一个虚拟头结点
        Node dummyHead = new Node(-1);
        // 与传入链表链接
        dummyHead.next = head
        Node prev = dummyHead;
        // prev是虚拟头节点，值不存在，从prev.next开始看元素值是否要删除
        while (prev.next != null) {
            // 此时prev就是待删除的节点
            if (prev.next.data == val) {
                Node node = prev.next;
                prev.next = node.next;
                node.next = null;
                size--;
            } else {
                // 此时prev不是待删除节点的前驱，继续移动，向后判断
                prev = prev.next;
            }
        }
        return dummyHead.next;
    }