单链表实现

创立节点类

public class Node {
    /**
     * 为了便于了解 不应用 private 润饰
     */
    Object data;// 存储数据的援用
    Node next;// 下一个节点的援用
public Node() {}

    public Node(Object data, Node next) {
        this.data = data;
        this.next = next;
    }
 }

创立链表类

public class SingleLinkedList implements List {private Node head = new Node();// 头节点，不存储数据，为了编程不便
    
    private int size;// 一共有几个结点
    }

查找第 i 个节点的值

在单链表中进行查找操作只能从链表的首节点开始，通过每个节点的 next 援用来顺次拜访链表中的每个节点，以实现相应的查找操作

public Object get(int i) {
// 如果 i 的地位谬误报异样
        if (i<0 ||i >size){throw new MyArrayIndexOutOfBoundsException("指针越界异样："+"i");
        }
        // 和程序表不一样了，不能通过索引间接定位，须要从头节点开始进行查找
        // 从头节点开始挪动指针
        Node p = head;
        for (int j = 0; j <= i; j++) {p = p.next;}
        return p.data;
    }

增加节点操作

增加节点不须要挪动元素，只须要批改元素的指针
须要先查找到增加地位 i，再增加新节点

public void add(int i, Object e) {
        // 如果 i 的地位谬误报异样
        if (i < 0 || i > size){throw new MyArrayIndexOutOfBoundsException("指针越界异样："+"i");
        }
        // 找到前一个节点，从头节点 head 开始挪动指针
        Node p = head;
        for (int j = 0; j < i; j++) {p = p.next;}
        // 新创建一个节点
        Node newNode = new Node(e,null);
        // 须要先指明新节点的间接后继节点，newNode.next = p.next;
        // 再指明新节点的间接前驱节点
        p.next = newNode;
        // 节点个数 +1
        size++;
    }

删除节点操作

public Object remove(int i) {if (i < 0 || i > size){throw new MyArrayIndexOutOfBoundsException("指针越界异样："+"i");
        }
        Node p = head;
        for (int j = 0; j < i; j++) {p = p.next;}
        Node temp = p.next;
        p.next = temp.next;
        temp.next = null;
        size--;
        return temp.data;
    }