单链表的增删改查（进阶版）

一、带头单链表的增删改查

package seqlist;
import java.util.Arrays;
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 SingleLinkedList {
    private int size;
    private Node head;

    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++;
        }
    }

    public void addIndex(int index, int data) {
        if (index < 0 || index > size) {
            System.err.println("add Index is 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++;
    }

    public void addLast(int data) {
        addIndex(size, data);
    }

    public int get(int index) {
        if (rangeCheck(index)) {
            Node node = head;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            int data = node.data;
            return data;
        } else {
            System.err.println("get index illegal!");
            return -1;
        }
    }

    public int set(int index, int data) {
        if (rangeCheck(index)) {
            Node node = head;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            int oldData = node.data;
            node.data = data;
            return oldData;
        } else {
            System.err.println("set index illegal!");
            return -1;
        }
    }

    private boolean rangeCheck(int index) {
        if (index < 0 || index >= size) {
            return false;
        }
        return true;
    }

    public boolean contains(int data) {
        Node node = head;
        while (node != null) {
            if (node.data == data) {
                System.out.println("找到元素");
                return true;
            }
            node = node.next;
        }
        System.out.println("没有找到该元素");
        return false;
    }

    public void removeFirst() {
        Node node = head;
        head = head.next;
        node.next = null;
        size--;
    }

    public void removeIndex(int index) {
        if (rangeCheck(index)) {
            if (index == 0) {
                removeFirst();
            } else {
                Node prev = head;
                for (int i = 0; i < index - 1; i++) {
                    prev = prev.next;
                }
                Node node = prev.next;
                prev.next = node.next;
                node.next = null;
                size--;
            }
        } else {
            System.out.println("remove index illegal");
        }
    }

    public void removeValueOnce(int data) {
        if (head.data == data) {
            removeFirst();
        } else {
            Node prev = head;
            while (prev.next != null) {
                if (prev.next.data == data) {
                    Node node = prev.next;
                    prev.next = node.next;
                    node.next = null;
                    size--;
                    break;
                } else {
                    prev = prev.next;
                }
            }
        }
    }

    public void removeAllValue(int data) {
        while (head != null && head.data == data) {
            Node node = head;
            head = head.next;
            node.next = null;
            size--;
        }
        if (head == null) {
            return;
        } else {
            Node prev = head;
            while (prev.next != null) {
                if (prev.next.data == data) {
                    Node node = prev.next;
                    prev.next = node.next;
                    node.next = null;
                    size--;
                } else {
                    prev = prev.next;
                }
            }
        }
    }

    public static void main(String[] args) {
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addLast(4);
        singleLinkedList.addLast(4);
        singleLinkedList.addLast(4);
        singleLinkedList.addLast(3);
        singleLinkedList.addLast(4);
        singleLinkedList.addFirst(1);
        singleLinkedList.addIndex(3, 8);
        System.out.println(singleLinkedList);
        singleLinkedList.contains(4);
        singleLinkedList.get(3);
        singleLinkedList.set(4, 5);
        System.out.println(singleLinkedList);
        singleLinkedList.removeAllValue(4);
        System.out.println(singleLinkedList);
    }

    @Override
    public String toString() {
        String ret = " ";
        Node node = head;
        while (node != null) {
            ret += node.data + "->";
            node = node.next;
        }
        ret += "NULL";
        return ret;
    }
}

运行截图：

二、不带头（虚拟头结点）单链表的增删改查

package seqlist;

class DummyHead {
    private Node dummyHead = new Node(-1);
    private int size;

    public void addIndex(int index,int data) {
        if(index < 0 || index > size) {
            System.err.println("add index illegal");
            return;
        }
        Node prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        Node node = new Node(data);
        node.next = prev.next;
        prev.next = node;
        size++;
    }

    public void addFirst(int data) {
        addIndex(0,data);
    }

    public void addLast(int data) {
        addIndex(size-1,data);
    }

    public int removeIndex(int index) {
        if(index < 0 || index >= size ) {
            System.err.println("remove index illegal");
            return -1;
        }
        Node prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        Node node = prev.next;
        prev.next = node.next;
        node.next = null;
        size--;
        return node.data;
    }

    @Override
    public String toString() {
        String ret = " ";
        Node node = dummyHead.next;
        while (node != null) {
            ret += node.data + "->";
            node = node.next;
        }
        ret += "NULL";
        return ret;
    }

    public static void main(String[] args) {
        DummyHead withHead = new DummyHead();
        withHead.addFirst(7);
        withHead.addLast(11);
        withHead.addLast(888);
        withHead.addFirst(1024);
        withHead.addIndex(3,8);
        withHead.addLast(9);
        System.out.println(withHead);
        withHead.removeIndex(3);
        System.out.println(withHead);
    }
}

运行截图：