最新公告
  • 新注册用户请前往个人中心绑定邮箱以便接收相关凭证邮件!!!点击前往个人中心
  • 数据结构笔记总结(3.2)在链表中添加元素

    在链表头添加元素

    对于链表来说,如果我们要想访问存在于链表中所有的节点,那么我们必须把链表的头给存储起来,通常这个链表头叫head。

    也就是说在LinkedList中应该有一个node型的变量叫head,指向链表中第一个节点。

    接下来首先把LinkedList中基本的成员变量给声明出来,

    private Node head;
        private int size;
    
        public LinkedList(){
            head = null;
            size = 0;
        }
    

    接下来为我们的链表写两个基本的方法,获取链表中元素的个数getSize()方法和返回链表是否为空isEmpty()方法。

    // 获取链表中的元素个数
    public int getSize(){
         return size;
    }
    
    // 返回链表是否为空
    public boolean isEmpty(){
        return size == 0;
    }
    

    接下来我们研究一下如何为链表添加元素?

    在数组中添加元素是从数组尾添加,而链表恰恰相反,在链表头添加元素是非常方便的。

    其实这非常容易理解,对于数组来说,有size这个变量,直接指向了数组中最后一个元素的下一个位置,也就是下一个待添加元素的位置,所以直接添加元素就非常容易。

    因为有size这个变量直接跟踪数组的尾巴,对于链表来说,我们设立了一个链表头这样一个变量,也就相当于我们有一个变量在跟踪链表头,可是却没有一个变量在跟踪链表尾,所以在链表头添加元素是很方便的。

    假设要将666添加进链表中,就要把666放进相应节点里,在这个节点里存了666这个元素以及一个next。

    添加过程的关键在于如何把这个节点挂接在链表中,与此同时不破坏这个链表的结构,那么我们该怎么做呢?

    假设这个666叫node的话,首先要做的就是将node的next指向链表的头,也就是node.next=head,执行完这句话之后,666成了新的链表头。

    下面要做的事情就是让head=node,也就是让head指向666这个节点。

    这样一来就完成了将666这个节点插入到整个链表的头部,整个过程是在函数中执行的。

    所以对于node这个变量来说,它指向的是666这个节点,这个函数结束之后,node这个变量的块作用域就结束了,这个变量相应的也就没用了。

    完善在链表头添加元素代码

    接下来我们继续完善上一节的代码,在链表头添加新的元素方法

    // 在链表头添加新的元素e
    public void addFirst(E e){
    //     Node node = new Node(e);
    //     node.next = head;
    //     head = node;
    
        head = new Node(e, head);
        size ++;
    }
    

    在链表中间添加元素

    如下是一个链表,现在想在“索引”为2的地方添加元素666

    首先创建出666这个节点,要想将666节点插入特定位置,就必须要找到当我们插入666这个节点之后,这个节点之前的那个节点是谁,我们叫它prev。

    它初始化和head在一个地方,其实非常好理解,我们要找到666之前的那个节点,就直接把之前的那个节点的next指向666。

    666的next指向之前的那个节点的之后的那个节点就完成了这个插入了,有些人可能已经懵逼了吧?(;′⌒`)

    所以现在的任务就是搜索插入666之前的那个节点。

    显然,插入666之后的索引为2,之前的索引就为1。

    所以我们从0开始遍历到索引为1的位置就好了。

    下面要做的就是将node的next指向prev的下一个元素,对应的代码就是node.next=prev.next

    然后再让prev.next=node

    经过这两步操作后,就完成了将666插入了“索引”为2的地方。这个过程的关键:

    这里还有个问题,如果我们要将这个元素添加到索引为0的地方,也就是链表的头部,那么链表头部的节点是没有前一个节点的,所以对于这种情况需要特殊处理一下。

    完善在链表中间添加元素代码

    // 在链表的index(0-based)位置添加新的元素e
    // 在链表中不是一个常用的操作,练习用:)
    public void add(int index, E e){
    
        if(index < 0 || index > size)
            throw new IllegalArgumentException("Add failed. Illegal index.");
    
        if(index == 0)
            addFirst(e);
        else{
            Node prev = head;
            for(int i = 0 ; i < index - 1 ; i ++)
                prev = prev.next;
    
    //          Node node = new Node(e);
    //          node.next = prev.next;
    //          prev.next = node;
    
            prev.next = new Node(e, prev.next);
            size ++;
        }
    }
    

    顺手再完成一个在链表尾部添加元素的方法

    // 在链表末尾添加新的元素e
    public void addLast(E e){
        add(size, e);
    }
    

    源码下载

    [dm href='https://www.jikewenku.com/product/1487.html']下载地址[/dm]

    导航目录

    [dm href='https://www.jikewenku.com/geeknote/2241.html']查看导航[/dm]

    本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
    极客文库 » 数据结构笔记总结(3.2)在链表中添加元素

    常见问题FAQ

    如果资源链接失效了怎么办?
    本站用户分享的所有资源都有自动备份机制,如果资源链接失效,请联系本站客服QQ:2580505920更新资源地址。
    如果用户分享的资源与描述不符怎么办?
    可以联系客服QQ:2580505920,如果要求合理可以安排退款或者退赞助积分。
    如何分享个人资源获取赞助积分或其他奖励?
    本站用户可以分享自己的资源,但是必须保证资源没有侵权行为。点击个人中心,根据操作填写并上传即可。资源所获收益完全归属上传者,每周可申请提现一次。
    如果您发现了本资源有侵权行为怎么办?
    及时联系客服QQ:2580505920,核实予以删除。

    参与讨论

    • 184会员总数(位)
    • 3737资源总数(个)
    • 0本周发布(个)
    • 0 今日发布(个)
    • 572稳定运行(天)

    欢迎加入「极客文库」,成为原创作者从这里开始!

    立即加入 了解更多
    成为赞助用户享有更多特权立即升级