Java数据结构与算法——链表（面试）

keke 发布于2019-08-16 11:08 / 1001人阅读

摘要：前言数据结构与算法专题会不定时更新，欢迎各位读者监督。指针反转实现链表反转代码反转链表获取当前下下个元素测试代码部分用到了上篇文章数据结构与算法链表的代码段，请移步获取。

声明：码字不易，转载请注明出处，欢迎文章下方讨论交流。

前言：Java数据结构与算法专题会不定时更新，欢迎各位读者监督。本文是上篇文章Java数据结构与算法——链表的扩展篇，介绍链表的特点，使用场景、链表的性能分析以及一道经典的链表面试题——链的反转问题

1.链表的特点

1）物理空间不连续，开销大

链表由于其特殊的存储结构，其物理存储空间不连续，因此需要额外的信息（指针）标记下一节点的地址，优点是可利用操作系统的动态内存管理，缺点除存储数据本身之外需要额外的开销存放指针。

2）运行时可以动态添加

和数组不同，链表可以动态的添加元素和删除元素，弥补了数组的缺陷

3）查找慢，增删快

很显然，查找需要遍历，最差的情况如果查找最后一个，则比较低效特别是链表比较长的时候。链表的增删只需要操作指针即可，相比数组比较高效

2.链表的适用场景

增删频繁的场合（随着计算机技术的发展，空间已经不再是主要矛盾，时间效率才是）
如果同时存在即增删又查找的场合，一般链表会配合散列表、栈、队列一起使用。

3.链表性能分析

链表的插入分为头插入、尾插入、中间插入,头和尾的时间复杂度尾O(1),而中间插入需要遍历，所以时间复杂度尾O(L)，L为链表长度。

同样删除也分为头删除、尾删除、中间删除，头删除的时间复杂度是O(1)，中间删除和尾删除由于需要遍历链表，所以时间复杂度为O(L)，L为链表长度。

链表的查找，由于需要遍历，所以时间复杂度为O(L)，L为链表长度。

4. 一道面试题——如何实现链表反转

这是一道面试中经常出现的题，一般在面试中要求尽量不用额外的空间实现。方法有很多，比如遍历链表，然后依次使用头插入的方式。还有一种方法，就是把链表的每个指针反转。

4.1 指针反转实现链表反转代码

    /**
     * 反转链表
     */
    public void lindRevese(){
        Node temp = first;
        last = temp;
        Node next = first.getNext();
        for (int i = 0; i < size-1; i++) {
            Node nextNext = next.getNext(); //获取当前下下个元素
            next.setNext(temp);
            temp = next;
            next = nextNext;
        }
        last.setNext(null);
        first = temp;
    }

4.2 测试

public class LinkReverse {
    public static void main(String[] args) {
        Link link = new Link();
        link.add(0,1); //1
        link.add(1,2); //1->2
        link.add(2,3); //1->2->3
        link.add(3,4); //1->2->3->4
        link.add(4,5); //1->2->3->4->5
        link.printLink();//1->2->3->4->5
        link.lindRevese();
        link.printLink();//5->4->3->2->1
    }    
}

代码部分用到了上篇文章Java数据结构与算法——链表的代码段，请移步获取。

码字不易，如对您有帮助，欢迎点赞收藏打赏^_^

GPU云服务器云服务器链表算法机器算法与java 链表排序算法 java链表数据结构

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/71038.html

数据结构 - 收藏集 - 掘金

面试旧敌之红黑树（直白介绍深入理解） - Android - 掘金读完本文你将了解到：什么是红黑树黑色高度红黑树的 5 个特性红黑树的左旋右旋指定节点 x 的左旋右图转成左图指定节点 y 的右旋左图转成右图红黑树的平衡插入二叉查找树的插入插入后调整红黑树结构调整思想插入染红后... java 多线程同步以及线程间通信详解 & 消费者生产者模式 & 死锁 & Thread...

leeon 2019-08-16 10:32 评论0 收藏0
Java数据结构与算法——链表

摘要：前言数据结构与算法专题会不定时更新，欢迎各位读者监督。本文介绍另一种数据结构链表，包括链表的特点特点链表的创建删除插入和输出，文末给出代码和一道常见的关于链表的面试题。声明：码字不易，转载请注明出处，欢迎文章下方讨论交流。前言：Java数据结构与算法专题会不定时更新，欢迎各位读者监督。本文介绍另一种数据结构——链表，包括链表的特点特点、链表的创建、删除、插入和输出，文末给出java...

CKJOKER 2019-08-16 11:08 评论0 收藏0
这几道Java集合框架面试题在面试中几乎必问

摘要：若遇到哈希冲突，则将冲突的值加到链表中即可。之后相比于之前的版本，之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值默认为时，将链表转化为红黑树，以减少搜索时间。有序，唯一红黑树自平衡的排序二叉树。本文是最最最常见Java面试题总结系列第三周的文章。主要内容： Arraylist 与 LinkedList 异同 ArrayList 与 Vector 区别 HashMap的底层...

bigdevil_s 2019-08-19 11:01 评论0 收藏0