《算法通关村第一关——链表青铜挑战笔记》-CSDN博客

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

《算法通关村第一关——链表青铜挑战笔记》

Java如何构造出链表

概念

如何构造出链表首先必须了解什么是链表

单向链表就像一个铁链一样元素之间相互链接包含多个节点每个节点有一个指向后继元素的next指针。表中最后一个元素的next指向null。

在这里插入图片描述

链表的核心是一个节点只能有一个后继节点但不代表链表指向本节点的只有一个。

Java与C++不同没有了指针只有引用不用进行内存的回收会使得代码的书写更加简单。

Java如何编写链表

先放代码

package AlgorithmFirst;

public class LinkedNode {
    private int data;
    private LinkedNode next;
    public LinkedNode(int data){
        this.data = data;
    }

    /**
     * 获取数据
     * @return 数据值
     */
    public int getData(){
        return this.data;
    }

    /**
     * 设置数据的值
     * @param data 数据
     */
    public void setData(int data){
        this.data = data;
    }

    /**
     * 获取下一个节点
     * @return 当前节点的下一个几点
     */
    public LinkedNode getNext(){
        return this.next;
    }

    /**
     * 设置下一个节点的值
     * @param next 下一个节点
     */
    public void setNext(LinkedNode next){
        this.next = next;
    }

    /**
     * 获取链表长度
     * @param head 头节点
     * @return
     */
    public static int getListLength(LinkedNode head){
        int length = 0 ;
        LinkedNode node = head;
        while(node != null){
            length ++ ;
            node = node.next;
        }
        return length;
    }

    /**
     * 缺省位置直接在最后插入
     * @param head 头节点
     * @param insertNode 插入节点
     * @return 头节点
     */
    public static LinkedNode insertNode(LinkedNode head,LinkedNode insertNode){
        int size = getListLength(head);
        // return insertNode(head,insertNode,size+1); 修改一下以便insertNode后面的元素能够全部插入进来。
        int count = 1;
        LinkedNode temp = head;
        while(temp != null){
            if(count == size ){
                temp.next = insertNode;
            }
            temp = temp.next;
            count++;
        }
        return head;
    }

    /**
     * 指定位置插入
     * @param head 头节点
     * @param nodeInsert 插入节点
     * @param position 插入位置从1开始
     * @return 返回头节点
     */
    public static LinkedNode insertNode(LinkedNode head , LinkedNode nodeInsert, int position){
        if (head == null ){
            // 如果head == null 表示当前链表为空可以直接返回当前节点或者报异常这里直接把它当作头节点。
            return nodeInsert;
        }
        // 已经存在的元素的个数
        int size = getListLength(head);
        if(position > size + 1 || position < 1 ){
            System.out.println("位置参数越界");
            return head;
        }

        // 表头插入
        if(position == 1 ){
            nodeInsert.next = head;
            // 这里可以直接 return nodeInsert
            head = nodeInsert;
            return head;
        }

        LinkedNode pNode = head;
        int count = 1;
        // 这里position 被上面的size限制住了不用考虑pNode = null
        while(count < position -1){
            pNode = pNode.next;
            count ++ ;
        }
        nodeInsert.next = pNode.next;
        pNode.next = nodeInsert;
        return head;
    }

    /**
     * 缺省参数的删除最后一个节点
     * @param head 链表头节点
     * @return 返回新链表头节点
     */
    public static LinkedNode deleteNode(LinkedNode head){
        int size = getListLength(head);
        return deleteNode(head,size);
    }

    /**
     * 根据位置删除节点
     * @param head 链表头节点
     * @param position 位置从1开始最大链表大小 超出不删除返回原头节点。
     * @return 新链表头节点
     */
    public static LinkedNode deleteNode(LinkedNode head , int position){
        if(head == null) {
            // 链表为空无法删除
            return null ;
        }
        int size = getListLength(head);
        if(position > size || position < 1 ){
            System.out.println("输入参数有误" );
            return head;
        }
        if( position == 1){
            return head.next;
        }else{
            LinkedNode cur = head;
            int count = 1;
            while(count<position-1){
                cur = cur.next;
                count ++;
            }
            LinkedNode curNode = cur.next;
            cur.next = curNode.next;
            //上面两行可以简化成  cur.next = cur.next.next
        }
        return head;
    }

    public static void  printLinkedList(LinkedNode head){
        int count = 0;
        while(head != null){
            System.out.println("第 "+ ++count +" 个"+ head.data);
            head = head.next;
        }
    }

    public static void main(String[] args) {
        LinkedNode head = new LinkedNode(0);
        for(int i = 0 ; i<10 ; i++){
            head = LinkedNode.insertNode(head,new LinkedNode(i+1));
        }
        System.out.println("origin:");
        printLinkedList(head);
        head = deleteNode(head,3);
        System.out.println("delete the third ");
        printLinkedList(head);
        head = deleteNode(head);
        System.out.println("delete the last one");
        printLinkedList(head);
        head = insertNode(head,new LinkedNode(11));
        System.out.println("insert one from last");
        printLinkedList(head);
        head = insertNode(head,new LinkedNode(22222),1);
        System.out.println("insert to first");
        printLinkedList(head);
    }

}