【数据结构】单向链表的原理及实现

public class SingleLinkedList<T> {

    /**
     * 定义头节点
     */
    public Node<T> head = new Node<>(null);

    /**
     * 链表有效元素个数
     */
    private int length=0;

    /**
     * 向单链表中添加一个元素
     * @param data
     */
    public void add(T data){
        //定义当前数据
        Node<T> nodeData = new Node<>(data);
        //定义辅助指针
        Node<T> cur = head;
        //while 循环不断遍历找到最后一个节点
        while (cur.next != null) {
            //只要有下一个节点，辅助指针就向下移动一位
            cur = cur.next;
        }
        //while循环之后，cur已经是最后一个节点，将data赋值到cur的下一个节点上
        cur.next = nodeData;
        //整体链表长度++
        length++;
    }

    /**
     * 向单链表中添加一个元素
     * @param data
     */
    public void add(int index,T data){
        //判断index是否合法
        if(index <0 || index >length){
            System.out.println("index不合法");
            return;
        }
        //定义当前数据
        Node<T> nodeData = new Node<>(data);
        //定义辅助指针
        Node<T> cur = head;
        //找到当前index的元素
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        //将当前节点的next设置成cur的next
        nodeData.next = cur.next;
        //将cur.next设置成nodeData（当前节点）
        cur.next = nodeData;
        //整体链表长度++
        length++;
    }

    /**
     * 遍历输出链表中全部节点
     */
    public void show(){
        //定义辅助指针
        Node<T> cur = head;
        //判断链表中是否存在元素
        if (cur.next == null){
            System.out.println("当前单向链表中元素为空");
            return;
        }
        while (cur.next != null){
            System.out.print(cur.next.data+" ");
            cur = cur.next;
        }
        System.out.print("\n");
    }

    /**
     * 修改指定下标的数据
     * @param index
     * @param data
     */
    public void update(int index,T data){
        Node<T> cur = head;
        if(index > length){
            System.out.println("当前index查过边界");
            return;
        }
        //遍历寻找指定index的节点
        for (int i = 0; i <= index; i++) {
            cur = cur.next;
        }
        //找到之后将新的data赋值上去
        cur.data = data;
    }

    /**
     * 删除指定下标元素
     * @param data
     */
    public void delete(int index){
        Node<T> cur = head;
        if(index > length){
            System.out.println("当前index超过边界");
            return;
        }
        //遍历寻找指定index的节点
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        //找到之后将新的data赋值上去，将后一个data赋值到当前节点上
        cur.data = cur.next.data;
        //将当前节点的next变成当前节点的next.next相当于将当前元素的next节点删掉
        cur.next = cur.next.next;
        //单链表整体有效元素减一
        length--;
    }

    /**
     * 获取指定下标元素的数据
     * @param index
     * @return
     */
    public T get(int index){
        //校验参数是否合法
        if(index<0 || index>length){
            System.out.println("当前index超过边界");
        }
        //定义辅助节点
        Node<T> cur = head;
        //找到对应下标的node
        for (int i = 0; i <=index; i++) {
            cur = cur.next;
        }
        //返回node.data
        return cur.data;
    }

    /**
     * 获取单链表的长度
     * @return
     */
    public int length(){
        return this.length;
    }

    /**
     * 内部节点类
     * @param <T>
     */
    class Node<T>{

        /**
         * 定义数据
         */
        public T data;

        /**
         * 定义下一个节点的
         */
        public Node<T> next;

        public Node(T data) {
            this.data = data;
        }
    }
}

public class Main {
    public static void main(String[] args) {
        SingleLinkedList<Integer> singleLink = new SingleLinkedList<>();

        //增加元素
        singleLink.add(1);
        singleLink.add(2);
        singleLink.add(3);
        System.out.print("新增之后：");
        singleLink.show();

        //删除元素
        singleLink.delete(0);
        System.out.print("删除index为0之后：");
        singleLink.show();

        //修改元素
        singleLink.update(0,9);
        System.out.print("修改index为0之后：");
        singleLink.show();

        //获取单链表的长度
        int length = singleLink.length();
        System.out.println("单链表的长度："+length);

        //获取指定下标的数据
        System.out.println("获取指定下标的数据："+singleLink.get(1));

        //指定下标插入数据
        singleLink.add(1,6);
        System.out.print("在index为1位置插入数据之后：");
        singleLink.show();
    }
}