什么是链表

链表是一个数据结构
在内存中，数组和链表都是最基本的数据结构(表、线性表)

线性表：线性的结构，它是一个含有 n >= 0 个节点的有限序列
而且只有一个"上一个"结点，有且只有一个"下一个"结点，有头有尾的一条线

单向链表 在维护一个结点自身的值时，还要维护下一个值的结点
双向链表 在维护一个结点自身的值时，还要维护它的上一个和下一个结点的指向

单向链表

Node类

public class Node {
    private Integer data;
    private Node next;

    public Integer getData() {
        return data;
    }
    public void setData(Integer data) {
        this.data = data;
    }
    public Node getNext() {
        return next;
    }
    public void setNext(Node next) {
        this.next = next;
    }
    public Node() { // 无参构造器
    }
    public Node(Integer data, Node next) { // 有参构造器 双向链表也是一样的结构
        this.data = data; // 只是多了一个Previous
        this.next = next;
    }
}

SuperLinked类

public class SuperLinked {
    private int size;
    private Node first;
    private Node last;
    
    public SuperLinked() {
    }
    public boolean add(Integer data){
        Node node = new Node(data,null);
        if(first == null) {
            first = node;
        }else {
            last.setNext(node);
        }
        last = node;
        size++;
        return true;
    }
    public boolean addIndex(Integer data,Integer index) {
        if (index ==0) {
            Node node = new Node(data,first);
            first = node;
        } else {
            Node preNode = getNode(index-1);
            Node node = new Node(data,preNode.getNext());
            preNode.setNext(node);
        }
        size++;
        return true;
    }
    public void delTop() {
        if (first!=null) {
            first=first.getNext();
            size--;
        }
    }
    public void delLast() {
        if (first!=null) {
            getNode(size-2).setNext(null);
            size--;
        }
    }
    public void delIndex(int index) {
        Node cursor = new Node();
        if (first!=null) {
            getNode(index-1).setNext(getNode(index-1).getNext().getNext());
            size--;
        }
    }
    public boolean del(Integer data) {
        Node preNode = first;
        Node cursor = first;
        for (int i = 0; i <= size; i++) {
            preNode = cursor;
            cursor = cursor.getNext();
            if (cursor.getData().equals(data)) {
                preNode.setNext(cursor.getNext());
                break;
            }
        }
        size--;
        return true;
    }
    public Node getNode(int index){
        if(index < 0){
            index = 0;
        }
        if(index >= size - 1){
            index = size - 1;
        }
        Node cursor = first;
        for (int i = 0; i < index; i++) {
            cursor = cursor.getNext();
        }
        return cursor;
    }
    public int getSize() {
        return size;
    }
}

Demo类 (测试类)

public class Demo {

    public static void main(String[] args) {
        SuperLinked superLinked = new SuperLinked();
        superLinked.add(1);
        superLinked.add(2);
        superLinked.add(3);
        superLinked.addIndex(4,1);
        superLinked.addIndex(5,2);
        superLinked.addIndex(6,0);
        superLinked.del(4);
        superLinked.delTop();
        superLinked.delLast();
        superLinked.delIndex(1);

        for (int i = 0; i < superLinked.getSize(); i++) {
            System.out.println(superLinked.getNode(i).getData());
        }

    }
}

双向链表

有点懒了，没做那么多关于error的判断
都是假象在正常操作下的执行
正常使用不会出现任何问题，但是如果超出size
添加、删除或查询不符合规定的位置，将会报错

Node类

public class Node {
    Integer data;
    Node previous;
    Node next;

    public Node() { }
    public Node(Node previous, Integer data,  Node next) {
        this.data = data;
        this.previous = previous;
        this.next = next;
    }
    public Integer getData() {
        return data;
    }
    public void setData(Integer data) {
        this.data = data;
    }
    public Node getPrevious() {
        return previous;
    }
    public void setPrevious(Node previous) {
        this.previous = previous;
    }
    public Node getNext() {
        return next;
    }
    public void setNext(Node next) {
        this.next = next;
    }
}

SuperLinked类

public class SuperLinked {

    private int size;
    private Node first;
    private Node last;

    public void removeFirst() {
        first = first.getNext();
        first.setPrevious(null);
        size--;
    }
    public void removeLast() {
        last = last.getPrevious();
        last.setNext(null);
        size--;
    }
    public void removeIndex(int index) {
        Node node = getNode(index);
        node.getPrevious().setNext(node.getNext());
        size--;
    }
    public void addIndex(Integer data,int index) {
        Node node = new Node(getNode(index),data,getNode(index).getNext());
        getNode(index+1).setPrevious(node);
        getNode(index).setNext(node);
        size++;
    }
    public void addLast(Integer data) {
        Node node = new Node(null,data,null);
        if (first == null) {
            first = node;
            last = node;
        } else {
            last.setNext(new Node(last,data,null));
            last = last.getNext();
        }
        size++;
    }
    public void addFirst(Integer data) {
        Node node = new Node(null,data,null);
        if (first == null) {
            first = node;
            last = node;
        } else {
            first = new Node(null,data,first);
        }
        size++;
    }

    public Node getNode(int index) {
        Node cursor = first;
        for (int i = 1; i < index; i++) {
            cursor = cursor.getNext();
        }
        return cursor;
    }

    public int getSize() {
        return size;
    }
}

Demo类 (测试类)

public class Demo {
    public static void main(String[] args) {
        SuperLinked superLinked = new SuperLinked();
        superLinked.addFirst(3);
        superLinked.addFirst(2);
        superLinked.addFirst(1);
        superLinked.addLast(4);
        superLinked.addIndex(5,1);
        superLinked.removeFirst();
        superLinked.removeLast();
        superLinked.addIndex(1,1);
        superLinked.removeIndex(3);

        for (int i = 1; i <= superLinked.getSize(); i++) {
            System.out.println(superLinked.getNode(i).getData());
        }
    }
}