面试官:请手写一个浅易的单链外
您的位置超橾人人在线免费视频-草莓直播二维码下载手机官网-东方在线影 > 草莓直播二维码下载手机官网 > 阅读资讯文章

面试官:请手写一个浅易的单链外

2022-01-13 14:08:56   来源:http://www.bfangel.com   【

吾现在有点清新了,在面试过程中面试官未必会让吾们手写代码,其实主要是考验行家的基本功,更是始末大多都熟识的周围来考核行家的系统化思想与答对思路。

而数据组织又是编程周围最基本知识,由于编程的世界中必须解决的题目:存储。

接下来笔者会从本身角度,重新最先学习数据组织,并将学习到的内容与行家一首探讨,交流,共同提高。

温馨挑示:本文主要以单链外外为例进走展开,由于单链外的反转、检测环都是常见面试题。

1、链外是什么?具备哪些基本特征?

面试官让吾们手写一个链外,那吾们最先迅速梳理出链外的基本特征。

专门从百度百科上查询了链外的定义:

链外是一栽物理存储单元上非不息、非挨次的存储组织,数据元素的逻辑挨次是始末链外中的指针链接顺序实现的。链外由一系列结点(链外中每一个元素称为结点)构成,结点能够在运走时动态生成。每个结点包括两个片面:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。

基本特征如下:

物理存储非不息、逻辑始末指针实现挨次性,其示例图如下所示:

数据组织分为指针域和数据域

面向对象编程,类不光要定义属性,还必要抽象出走为(手段),思考如下:

报告在面试过程中,只必要基本实现添、删、改、查即可。

2、图解与代码实现

链外的类图如下:

链外的存储组织如下图所示:

接下来将从代码角度来实现一个浅易的链外。

2.1 基础代码

链外的基础数据如下所示:

public class LinkedList<T> {      /** 指针域*/     // 头节点     private DataNode<T> header;     // 从节点     private DataNode<T> tail;      private int size;       /**      * 数据节点      * @param <T>      */     private class DataNode<T> {         public T value;         public DataNode<T> next;          public DataNode(T value) {             this.value = value;         }     } } 
2.2 指定下标插入节点

上面主要是定义基本的数据组织,接下来吾们望一下在链外的中间插入新的数据。

在指定下标处插入节点,该节点行为新节点的前驱节点,暂存它的next指针,谨防该指针会丢失,图示如下:

代码如下所示

public void add(int index, T value) {         if(index >= size) {             throw new ArrayIndexOutOfBoundsException();         }         DataNode<T> node = new DataNode<>(value);         DataNode<T> prev = get(index);          DataNode<T> tmp = prev.next;  // @1         prev.next = node;             // @2         node.next = tmp;              // @3     } 

链外的插入最先找到前驱节点,暂存它的next指针,谨防该指针会丢失,图解如下图所示:

上述三走代码的表明如下:

@1:最先创建一个一时节点,用于暂存前驱节点的next @2:前驱节点的next指针重新指向待插入的节点 @3:新节点的next指针指向原前驱节点的next指针

优化点:其实吾们发现,前驱节点是要暂存,但是否真有必要开辟一个一时节点,其实不必要,直接将其赋值给新节点的next即可。优化代码如下:

node.next = prev.next; prev.next = node; 
2.3 移除指定下标处节点

移除指定下标处节点的示例图:

正如上图所示,要移除下标为2的节点,即图中的第三个节点,核心关键点照样必要找到待删除节点的前驱节点,然后前驱节点的next等于待删除节点的next即可,故实当代码如下:

public T remove(int index) {         if(index >= size) {             throw new ArrayIndexOutOfBoundsException();         }          DataNode<T> pre = get(index - 1 );         DataNode<T> cur = pre.next;          pre.next = cur.next;         // help GC         cur.next = null;          size --;         return cur.value;     } 
2.4 单链外反转

所谓的单链外反转,就是将原链外反序输出效果,其示例图如下:

单链外的反转,必要做的事情是将现在节点的next指针指向前驱节点。

但由于单链外只有next指针,故从头节点最先遍历的过程中,遍历指针进展到的现在节点时,必要能方便的访问到该节点的前驱动。

另外一个核心点就是,在遍历过程中,对现在节点的next指针进走操作(赋值为前驱节点)时必须暂存该节点的next指针,否则next指针丢失,无法遍历到链外的末了。

基于上述思路,链外反转的详细操作流程如下图所示:

基于上述思路,代码编写如下所示:

public void reverse() {         // 从头节点最先遍历         DataNode<T> cur = header;         // 记录现在节点到 prev 前驱节点         DataNode<T> cur_prev = null;         // 暂存现在节点到next指针         DataNode<T> cur_next = null;          // 从现在节点最先遍历,直接到尾部         while(cur != null) {             //反转之前,先暂存有关节点             cur_next = cur.next;             cur.next = cur_prev;             cur_prev = cur;             // 不息遍历下一个节点             cur = cur_next;         }                  //反转 header ,tail         DataNode<T> tmp = header;         header = tail;         tail = tmp;     } 

链外的其他手段实现,基本差不多,从编写代码的过程中,不寝陋出链外的操作,主要是操作各个节点的指针。

3、常见面试题 3.1 链外与数组的不同

链外与数组的不同能够从如下几个方面展开:

内存组织 插入性能 查找性能

3.1.1 内存组织

数组必须申请不息的内存,即物理上不息,例如现在jvm虚拟机现在还剩150M内存,但此时尝试往创建一个100M内存,能够无法分配内存而触发垃圾回收,而链外是逻辑不息,物理上不不息,由于时始末指针进走定位。

3.1.2 插入性能

链外在头、尾节点插入性能极佳,倘若必要在链外的随机位置插入数据,必要先从头节点最先遍历,先找到有关待插入节点的前驱节点,后续的插入操作只必要涉及指针赋值,性能外现佳,而数组的插入由于必要涉及数据的复制、移动,从而带来较大性能消耗。

3.1.3 查找性能

数组最大的上风是随机查找能力,其时间复杂度为O(1),即数组能够按照下外迅速定位到必要查询到数据。而链外只能是从头节点或尾节点最先遍历。

本文转载自微信公多号「中间件有趣圈」,能够始末以下二维码关注。转载本文请有关中间件有趣圈公多号。

【编辑选举】

鸿蒙官方战略配相符共建——HarmonyOS技术社区 吾们一首学习删除链外的节点 聊一聊复制链外的复制 二叉搜索树转换为双向链外 求解“微信群遮盖”的三栽手段:暴力,染色,链外,并查集 数据组织与算法之链外相交,找交点
Tags:面试,官,请,手写,一个,浅易,的,单链外,吾,  
请文明参与讨论,禁止漫骂攻击。 用户名: 密码: 匿名:

合作伙伴/友情链接