• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

数据结构笔记总结(3.2)在链表中添加元素

极客笔记 Geekerstar 12个月前 (05-10) 325次浏览 已收录 0个评论 扫描二维码
文章目录[隐藏]

在链表头添加元素

对于链表来说,如果我们要想访问存在于链表中所有的节点,那么我们必须把链表的头给存储起来,通常这个链表头叫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);
}

源码下载

下载地址

导航目录

查看导航
丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:数据结构笔记总结(3.2)在链表中添加元素
喜欢 (0)
[247507792@qq.com]
分享 (0)
Geekerstar
关于作者:
本站技术支持

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00