文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

java单链表使用总结

2024-04-02 19:55

关注

链表的概念:

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列节点(链表中的每一个元素称为节点)组成,节点可以在运行时动态生成。每个节点包含两个部分:一个是存储数据元素的数据域,另一个是存储下一个节点地址的指针域。相对于线性表顺序结构,操作复杂。由于不必按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

链表的优势

不需要知道数据的大小,可以充分利用计算机内存空间,实现灵活的内存动态管理
链表允许插入和移除表上任意位置上的节点(但是不允许随机存取)

链表的缺点

不能像数组一样随机读取
增加了空间的开销(增加了节点的指针域)

代码实现

定义一个节点类

public class ListNode {//定义节点类
    int val;
    ListNode next;
 
    ListNode(int x) {
        val = x;
    }
 
    //将数组的值赋给链表
    public ListNode getList(int[] sums) {
        ListNode dummyHead = new ListNode(0);
        ListNode curr = dummyHead;
        for (int i = 0; i < sums.length; i++) {
            curr.next = new ListNode(sums[i]);
            curr = curr.next;
        }
        return dummyHead.next;
    }
 
    //将链表的值赋给list并打印
    public void showList(ListNode listNode) {
        List list = new ArrayList();
        while (listNode != null) {
            list.add(listNode.val);
            listNode = listNode.next;
        }
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
    }
 
    
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode p = l1, q = l2, curr = dummyHead;
        int carry = 0;
        while (p != null || q != null) {
            int x = (p != null) ? p.val : 0;
            int y = (q != null) ? q.val : 0;
            int sum = carry + x + y;
            carry = sum / 10;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
            if (p != null) p = p.next;
            if (q != null) q = q.next;
        }
        if (carry > 0) {
            curr.next = new ListNode(carry);
        }
        return dummyHead.next;
    }
}

测试方法

public class main {
    public static void main(String[] args) {
        int a[] = {2, 4, 3};
        int b[] = {5, 6, 4};
        ListNode curr=new ListNode(0);
        ListNode l1=curr.getList(a);
//        curr.showList(l1);
        ListNode l2=curr.getList(b);
//        curr.showList(l2);
        ListNode l3=curr.addTwoNumbers(l1,l2);
        curr.showList(l3);
    }
 
 
}

输入[2,4,3],[5,6,4]

输出[7,0,8]

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持编程网。

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯