数据结构 玩转数据结构 4-3 使用链表的虚拟头结点

标签：Node null return 28 链表 玩转 数据结构 public

0　　　　课程地址

https://coding.imooc.com/lesson/207.html#mid=13446

 

1　　　　重点关注

1.1　　　　代码草图解析

 

1.2　　　　为何为链表头设立虚拟头节点

为了解决链表任意索引位置添加元素时 索引为0的位置的差异化处理做统一口径

 

2　　　　课程内容

2.1　　　　虚拟头节点是什么

在链表头设立一个假的节点dummyHead,节点存储内容为null,指向头节点。

3　　　　Coding

3.1　　　　关键代码

• 重点看草图部分，代码中index=0,做了统一优化（可以和上节比较）
  

/**
     * 7  链表添加元素本节 
**/
    public void addElement(int index,E e){
        if(index<0||index>size){
            throw new IllegalArgumentException("索引不正确");
        }

        Node pre = dummyHead;
        for(int i = 0;i<index;i++){
            pre = pre.next;
        }

        //优雅写法
        pre.next = new Node(e,pre.next);
        size++;
    }


/**
     * 7  链表添加元素(上节)
**/
    public void addElement(int index,E e){
        if(index<0||index>size){
            throw new IllegalArgumentException("索引不正确");
        }

        if(index==0){
            addFirst(e);
        }else{
            Node pre = head;
            for(int i = 0;i<index-1;i++){
                pre = pre.next;
            }

            //优雅写法
            pre.next = new Node(e,pre.next);
            size++;
        }
    }

 

3.2　　　　全量代码（链表添加元素）

package com.company;

/***
 * 链表
 * @author weidoudou
 * @date 2022/10/28 7:56
 **/
public class LikedList<E> {

    /**
     * 1  内部类node
     * @author weidoudou
     * @date 2022/10/28 7:59
     * @return null
     **/
    private class Node{
        //Node 只有两个属性，下一个节点和本节点存储的元素
        private Node next;
        private E e;

        /**
         * 通用调用node方法
         * @author weidoudou
         * @date 2022/10/28 8:17
         * @param e 请添加参数描述
         * @param  nodeNew 请添加参数描述
         * @return null
         **/
        public Node(E e,Node nodeNew){
            this.e = e;
            this.next = nodeNew.next;
        }

        /**
         * node 无参构造
         * @author weidoudou
         * @date 2022/10/28 8:15
         * @return null
         **/
        public Node(){
            this(null,null);
        }

        /**
         * node 有参构造
         * @author weidoudou
         * @date 2022/10/28 8:16
         * @param e 请添加参数描述
         * @return null
         **/
        public Node(E e){
           this(e,null);
        }


        @Override
        public String toString() {
            final StringBuffer sb = new StringBuffer("Node{");
            sb.append("next=").append(next);
            sb.append(", e=").append(e);
            sb.append('}');
            return sb.toString();
        }
    }

    //2 LinkedList 属性 链表头元素（火车头），大小
    private int size;
    private Node dummyHead;

    /**
     * 3    LikedList 无参
     * @author weidoudou
     * @date 2022/10/28 8:27
     * @return null
     **/
    public LikedList() {
        this.dummyHead = new Node(null,null);
        this.size = 0;
    }

    /**
     * 4  getSize
     * @author weidoudou
     * @date 2022/10/28 8:23
     * @return null
     **/
    public int getSize(){
        return size;
    }

    /**
     * 5  isEmpyt
     * @author weidoudou
     * @date 2022/10/28 8:24
     * @return boolean
     **/
    public boolean isEmpty(){
        return size == 0;
    }

    /**
     * 6  链表头部添加元素
     * @author weidoudou
     * @date 2022/10/28 8:37
     * @param e 请添加参数描述
     * @return void
     **/
    public void addFirst(E e){
        /*Node nodeNew = new Node(e);
        nodeNew.next = head;    //火车尾指向 上个尾巴
        this.head = nodeNew;    //火车尾 变成了当前的node*/

        //称之为优雅写法
        addElement(0,e);
    }

    /**
     * 7  链表添加元素(链表通常不在中间添加元素，编写此段代码完全是为了后续便于理解和二叉树相关知识做铺垫)
     * @author weidoudou
     * @date 2022/10/28 8:45
     * @param index 请添加参数描述
     * @param  e 请添加参数描述
     * @return void
     **/
    public void addElement(int index,E e){
        if(index<0||index>size){
            throw new IllegalArgumentException("索引不正确");
        }


        Node pre = dummyHead;
        for(int i = 0;i<index;i++){
            pre = pre.next;
        }

        /*Node nodeNew = new Node(e);
        nodeNew.next = pre.next;
        pre.next = nodeNew;*/

        //优雅写法
        pre.next = new Node(e,pre.next);
        size++;
    }


    /**
     * 8  链表尾部添加元素 认真分析下
     * @author weidoudou
     * @date 2022/10/28 18:11
     * @param e 请添加参数描述
     * @return void
     **/
    public void addLast(E e){
        addElement(size,e);
    }


}

 

标签：Node,null,return,28,链表,玩转,数据结构,public
From： https://www.cnblogs.com/1446358788-qq/p/16838017.html