编程导航算法第一关 |链表的基础

这篇具有很好参考价值的文章主要介绍了编程导航算法第一关 |链表的基础。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

今天也是算法通关村刚开始,学习了链表。

首先,链表是一种最基本的结构,我们通常在收到一个链表的时候只有一个指向链表头的指针head,因为链表就是通过头指针来寻找其他结点的。

链表中的每个结点都存在它的数据和指向下一个节点的指针。

在遍历链表中,我们只需要在while循环中让它一直next就可以了,代码如下。

public static int getLength(Node head) {
    int length = 0;
    Node node = head;
    while (node != null) {
        length++;
        node = node.next;
    }
    return length;
}

在插入链表时,三种情况,表头插入,中间插入,结尾插入。

1. 表头插入,由于我们是通过头指针来寻找其他结点的,所以我们只需要将头结点改为新结点就可以了,head = nodeInsert;

2. 中间插入,我们需要在目标节点的前一个位置停下来,这里定义为cur,需要让cur.next=新结点,再让new.next=cur.next,这样就让cur结点的下一个结点是新结点,新结点下一个结点为原来cur.next,这样就实现了插入;

3.结尾插入,只要将尾结点指向新结点就可以了。

public static Node insertNode(Node head, Node nodeInsert, int position) {
    // 需要判空,否则后面可能会有空指针异常
    if (head == null) {
        return nodeInsert;
    }
    //越界判断
    int size = getLength(head);
    if (position > size + 1 || position < 1) {
        System.out.println("位置参数越界");
        return head;
    }

    //在链表开头插入
    if (position == 1) {
        nodeInsert.next = head;
		//return nodeInsert;
        //上面return还可以这么写:
        head = nodeInsert;
        return head;
    }

    Node pNode = head;
    int count = 1;
    while (count < position - 1) {
        pNode = pNode.next;
        count++;
    }
    nodeInsert.next = pNode.next;
    pNode.next = nodeInsert;

    return head;
}

链表删除,同样是三种情况,考虑表头,中间,表尾

1. 删除表头结点,只要执行head=head.next就行了

2. 删除中间结点,找到位置后,将cur.next指针的值更新为cur.next.next就可以解决

3. 删除表尾结点,只需要让表尾结点的前驱节点的next=null就可以了

public static Node deleteNode(Node head, int position) {
    if (head == null) {
        return null;
    }
    int size = getLength(head);
    if (position > size || position <= 0) {
        System.out.println("输入的参数有误");
        return head;
    }

    if (position == 1) {
        // head.next就是链表的新head
        return head.next;
    }
    Node preNode = head;
    int count = 1;
    while (count < position) {
        preNode = preNode.next;
        count++;
        Node curNode = preNode.next;
        preNode.next = curNode.next;
    }
    return head;
}

其实,我觉得链表就是通过表头就可以想查哪个结点就查哪个结点,不管是要对链表中的结点增删改查,都需要通过头结点来next。

双向链表

每个结点都是有数据域,指向前一个结点的指针,指向后一个结点的指针,这样的话移动元素会更方便。但是相对来说,代码也就更多了,更复杂,但是道理都是一样的。

在链表中间插入的时候,这里定义cur为要插入结点位置的前一个结点,需要先将当前结点的下一个结点的前一个结点等于新加入的结点,再让新结点的下一个结点设为现在cur的下一个结点,这样就完成了第一步,让新结点和要插入位置后边的结点联系起来了,然后让cur的下一个结点设为新插入的节点,再让当前节点的前一个结点设为cur,这样就让新加入的节点和cur结点联系起来了。关键代码为:文章来源地址https://www.toymoban.com/news/detail-610409.html

//某个结点的后部插入
public void insertAfter(int key, int data) {
    DoubleNode newDoubleNode = new DoubleNode(data);
    DoubleNode current = first;
    while ((current != null) && (current.data != key)) {
        current = current.next;
    }
    //若当前结点current为空
    if (current == null) {      
         //current为null有两种情况 一种是链表为空,一种是找不到key值
        if (isEmpty()) {       //1、链表为空       
            //则插入第一个结点(其实可以调用其它的Insert方法)
            first = newDoubleNode;       
            //first和last均指向该结点(第一个结点)
            last = newDoubleNode;                    
        } else {
            //2、找不到key值
            last.next = newDoubleNode;        
            newDoubleNode.prev = last;    //则在链表尾部插入一个新的结点
            last = newDoubleNode;
        }
    } else {      //第三种情况,找到了key值,分两种情况
        if (current == last) {        
            //1、key值与最后结点的data相等
            newDoubleNode.next = null;       
            //由于newNode将是最后一个结点,则将last指向newNode
            last = newDoubleNode;                    
        } else {
            //2、两结点中间插入
            newDoubleNode.next = current.next; 
            current.next.prev = newDoubleNode;    
        }                                        
        current.next = newDoubleNode;       //将当前结点的next域指向newNode
        newDoubleNode.prev = current;       //将新结点的previous域指向current
    }
}

到了这里,关于编程导航算法第一关 |链表的基础的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 编程导航算法通关村第1关 | 单链表的基础与构造方法

    什么是链表 不强制要求数据在内存集中存储,可以分散存储在内存中。例如数据{1,8,6,2},在链表的存储状态可能如图示: 只要让每一个元素知道它下一个元素的位置,就可以依次找出各个元素。 那么,链表是如何实现这种存储数据间的关系呢?为每一个元素配置一个指针,

    2024年02月14日
    浏览(34)
  • 编程导航算法通关村 | 链表中环的问题

    在链表中还有一类经典的问题,那就是判断链表中是否有环,如果有环,环的入口如何确定。 用Hash来做会很容易,遍历一遍,把每一个元素都放入map中,有环的话,那我们就一定能匹配到。 这里最重要的问题, 如果快的能到达表尾就不会有环,否则如果存在环,则慢指针一

    2024年02月14日
    浏览(39)
  • 编程导航算法通关村第1关 | 青铜:单链表的增删改查

    链表中的每一个节点包含数据域和指针域 (构造在一个 struct 中),数据变量存储数据,指针变量存储下一个节点的地址。 链表的一个节点只能有一个后继 特点: 链表节点在内存中的位置可以不连续。 思路: 用 struct 包装节点 :成员包括数据和地址 用 class 包装链表 :成员有

    2024年02月13日
    浏览(41)
  • 编程导航算法通关村 |两两交换链表中的节点、单链表加1

    推荐我自己加入的一个编程学习圈子,里面有编程学习路线和原创的项目教程,以及可 1 对 1 和大厂嘉宾交流答疑,也希望能对大家有帮助,扫 ⬇️ 二维码即可加入

    2024年02月16日
    浏览(35)
  • Java 算法篇-链表的经典算法:有序链表去重、合并多个有序链表

    🔥博客主页: 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍         文章目录          1.0 链表的说明          2.0 有序链表去重的实现方式         2.1 有序链表去重(保留重复的节点) - 使用递归来实现         2.2 有序链表去重(保留重复的节点) - 使用双指针

    2024年02月05日
    浏览(46)
  • 算法竞赛基础:C++双向链表的结构和实现(普通链表、List、静态链表)

    本文将会介绍在算法竞赛中双向链表的几种使用方式,适合有一定基础的人阅读。 一般来说,普通的链表结构是这样的: next指针指向下一个链表,这样的结构只能够支持单向查询。 双向链表,顾名思义,就是可以支持双向的访问和查询。 也就是这样的: 这种链表为访问前

    2024年01月24日
    浏览(42)
  • 算法通关村第一关——链表经典问题

    剑指office 52题 LeetCode234题 LeetCode 21 LeetCode 23 LeetCode 1669 LeetCode 876 剑指 Offer 22 LeetCode 61 LeetCode 203 LeetCode 19 LeetCode 83 LeetCode 82

    2024年02月14日
    浏览(42)
  • 算法通关村第一关-链表青铜挑战笔记

    平时我们一般都是用数组,每个数组都会有一个相对应的索引,这样就使得数组能够方便的调用出对应索引得到需要的数据,但是这也造成了一个问题,那就是不好在数组中插入或者删除一个数据,例如 int arr[]={1,2,4,5}如果我想在数组中的2和4中添加一个数据3 那么我们首先就

    2024年02月15日
    浏览(43)
  • 算法通关村第一关——链表青铜挑战笔记

    链表的基本单元就是 节点 ,也就是说链表是由一个一个节点构成的。 而对于节点来说,里面至少会包含一个 指针 和一个 数据元素 ,也就是如下图所示: 其中数据域用来存放数据元素,指针域用来存放指向下一个节点的指针,这样一个一个连接起来的就是链表。如下图所

    2024年02月16日
    浏览(43)
  • 《算法通关村第一关——链表青铜挑战笔记》

    链表中每个结点内部的“生态环境”。 数据域存储元素的值,指针域存放指针。 示例: c语言构造链表 可分为三步 1.创建头指针。 2.创建头结点,使头指针指向头结点。 3.循环创建结点,并使前一个结点指向当前结点。 1.)创建结点。 2.)使前一个结点指向当前结点。 3.)

    2024年02月15日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包