程序员-动画:面试如何轻松手写链表?-书荒源码

写在前边

暑假参加的第一个公司的就让我手写一个双向链表,并完成插入数据和删除数据的操作。当时我很蒙蔽,懵逼的不是思路,而是手写,虽然写出来了,但是很多边界条件和代码规范自我感觉不好,所以有了这些细心的总结。那么今天的主题就是徒手写链表,应聘者该如何下手?

我们通常写链表准备应聘的时候,通常背加上理解,但是过了几天又让你写。就会陌生了,虽然有点思路。还是模模糊糊,小鹿也有这个记性的“毛病”,“有毛病”就要治,怎么治?我们必须在脑海里形成一套可行的步骤和方法,在遇到手写就不用手忙脚乱,而是稳稳当当,从头到尾写出一个漂亮的链表结构及操作。

一、熟悉结构

首先我们要知道链表的结构以及每个节点的结构,这是我们手写链表的第一步,也是学习链表的第一步。我们知道,每个链表时这样表示的:

程序员-动画:面试如何轻松手写链表?-书荒源码

那每个节点结构是由数据域和指针域组成,数据域是存放数据的,而指针域存放下一结点的地址。

程序员-动画:面试如何轻松手写链表?-书荒源码

我们可以通过数据域访问到我们要的数据,而通过指针域访问到当前结点以后的结点,那么将这些结点串起来,就是一个链表。

那么用代码怎么来表示呢?

我们通常会用到函数,我们如果将一个函数抽象成一个结点,那么我们给函数添加两个属性,一个属性是存放数据的属性data,另一个属性是存放指向下一个结点的指针属性next。

你可能会问,如果我们有成千上万个结点,要定义成千上万个函数?有一个函数叫做构造函数,想必大家都听说过,声明一个构造函数就可以创造出成千上万个结点实例。

function Node(data){

    this.data = data;

    this.next = null;

}

还有一个方法就是使用类的概念,在JavaScript中,类的概念在ES6才出现,使用 Class 来声明一个类,我们可以为类添加两个属性,同上,一样可以创造出多个结点实例。

class Node{

    constructor(data){

        this.data = data;

        this.next = null;

    }

}

二、理清思路

如果你把链表的结构搞得明明白白了,恭喜你,成功的进入第二关,但是你只超越了百分之20的人,继续加油。

既然链表的结构弄明白了,那么我们开始理思路,我们就先拿最简单的单链表开刀,我们要完成两个操作,插入数据和删除数据。

如果我想插入数据,你可能会问,往哪里插呢?有几种插入的方法?

开始想,插入到单链表的头部算一种。

程序员-动画:面试如何轻松手写链表?-书荒源码

然后插入到单链表的中间算一种。

程序员-动画:面试如何轻松手写链表?-书荒源码

插入到单链表尾部又算一种。

程序员-动画:面试如何轻松手写链表?-书荒源码

所有可能的情况就三种。那么删除呢?想必你也想到了,也一共三种,删除头部、删除中间部分、删除尾部。

如果你觉的现在可以写代码了,那你就错了,虽然我们的思路非常清晰,但是面试官仅仅考我们思路吗?其实这一关你只打败了百分之50%的人,最重点、最主要的是在下一个部分,边界条件。

三、边界条件

边界条件是这五个步骤最容易犯错的一部分,因为通常考虑的不全面,导致了最后的面试未通过。如果想做好这一部分,也不难,跟着小鹿的方法走。

1、输入边界

首先我们先考虑用户输入的参数,比如传入一个链表,我们首先要判断链表是否为空,如果为空我们就不能让它执行下边的程序。再比如插入一个结点到指定结点的后边,那么你也要判断输入的结点是否为空,而且还要判断该结点是否存在该链表中。对于这些输入值的判断,小鹿给他同一起个名字叫做输入边界。

2、特殊边界

特殊边界考虑到一些特殊情况,比如插入数据,我们插入数据一般考虑到插入尾部,但是突然面试官插入到头部,插入尾部的代码并不适用于插入到头部,所以呢需要考虑这种情况,删除节点也是同样思考。其实特殊边界最主要考虑到一些逻辑上的特殊情况,考察应聘者的考虑的是否全面。小鹿给他起个名字叫做特殊边界。

四、手写代码

1、定义结点

程序员-动画:面试如何轻松手写链表?-书荒源码

class Node{

    constructor(data){

        this.data = data;

        this.next = null;

    }

}

2、增加结点

咱们就以单链表中部添加数据为例子,分解成每个步骤,每个步骤对应代码如下:

2.1 保存临时地址(4结点的地址),需要进行遍历查找到3结点,也就是下列代码的currentNode 结点。

程序员-动画:面试如何轻松手写链表?-书荒源码

//先查找该元素

let currentNode = this.findByValue(element);

// 保存 3 结点的下一结点地址(4 结点的地址)

let pre = currentNode.next

2.2 创建新结点,将新结点(5结点)的指针指向下一结点指针(4结点地址,已经在上一步骤保存下来了)

程序员-动画:面试如何轻松手写链表?-书荒源码

let newNode = new Node(value);

newNode.next = pre;

2.3 将3 的结点地址指向新结点(5结点)

程序员-动画:面试如何轻松手写链表?-书荒源码

currentNode.next = newNode;

以上步骤分析完毕,剩下的两个在头部插入和在尾部插入同样的分析方式,将这两个作为练习题,课下自己试一试这个步骤。

2.4 删除节点

删除节点也分为三种,头部、中部、尾部,咱们就删除中间结点为例进行删除,我们详细看步骤操作。

我们先看删除的全部动画,然后再分步拆分。

程序员-动画:面试如何轻松手写链表?-书荒源码

断开3结点的指针(断开3结点相当于让2结点直接指向4结点)

程序员-动画:面试如何轻松手写链表?-书荒源码

  let currentNode = this.head;

  // 用来记录 3 结点的前一结点

  let preNode = null;

  // 遍历查找 3 结点

  while(currentNode !== null && currentNode.data !== value){

         // 3 结点的前一结点

         preNode = currentNode;

         // 3 结点

         currentNode = currentNode.next;

}

让结点2的指针指向4结点,完成删除。

程序员-动画:面试如何轻松手写链表?-书荒源码

preNode.next = currentNode.next;

1

剩下的删除头结点和删除尾结点同样的步骤,自己动手尝试下。

所有代码实现:

  1/**

  2 * 2019/3/23

  3 * 公众号:「一个不甘平凡的码农」

  4 * @author 小鹿

  5 * 功能:单链表的插入、删除、查找

  6 * 【插入】:插入到指定元素后方

  7 * 1、查找该元素是否存在?

  8 * 2、没有找到返回 -1

  9 * 3、找到进行创建结点并插入链表。

 10 * 

 11 * 【查找】:按值查找/按索引查找

 12 * 1、判断当前结点是否等于null,且是否等于给定值?

 13 * 2、判断是否可以找到该值?

 14 * 3、没有找到返回 -1;

 15 * 4、找到该值返回结点;

 16 * 

 17 * 【删除】:按值删除

 18 * 1、判断是否找到该值?

 19 * 2、找到记录前结点,进行删除;

 20 * 3、找不到直接返回-1;

 21 */

 22//定义结点

 23class Node{

 24    constructor(data){

 25        this.data = data;

 26        this.next = null;

 27    }

 28}

 29

 30//定义链表

 31class LinkList{

 32    constructor(){

 33        //初始化头结点

 34        this.head = new Node('head');

 35    }

 36

 37    //根据 value 查找结点

 38    findByValue = (value) =>{

 39        let currentNode = this.head;

 40        while(currentNode !== null && currentNode.data !== value){

 41            currentNode = currentNode.next;

 42        }

 43        //判断该结点是否找到

 44        console.log(currentNode)

 45        return currentNode === null ? -1 : currentNode;

 46    }

 47

 48    //根据 index 查找结点

 49    findByIndex = (index) =>{

 50        let pos = 0;

 51        let currentNode = this.head;

 52        while(currentNode !== null && pos !== index){

 53            currentNode = currentNode.next;

 54            pos++;

 55        }

 56        //判断是否找到该索引

 57        console.log(currentNode)

 58        return currentNode === null ? -1 : currentNode;

 59    }

 60

 61    //插入元素(指定元素向后插入)

 62    insert = (value,element) =>{

 63        //先查找该元素

 64        let currentNode = this.findByValue(element);

 65        //如果没有找到

 66        if(currentNode == -1){

 67            console.log(“未找到插入位置!”)

 68            return;

 69        }

 70        let newNode = new Node(value);

 71        newNode.next = currentNode.next;

 72        currentNode.next = newNode;

 73    }

 74

 75    //根据值删除结点

 76    delete = (value) =>{

 77        let currentNode = this.head;

 78        let preNode = null;

 79        while(currentNode !== null && currentNode.data !== value){

 80            preNode = currentNode;

 81            currentNode = currentNode.next;

 82        }

 83        if(currentNode == null) return -1; 

 84        preNode.next = currentNode.next;

 85    }

 86

 87     //遍历所有结点

 88    print = () =>{

 89        let currentNode = this.head

 90        //如果结点不为空

 91        while(currentNode !== null){

 92            console.log(currentNode.data)

 93            currentNode = currentNode.next;

 94        }

 95    }

 96}

 97

 98//测试

 99const list = new LinkList()

100list.insert('xiao','head');

101list.insert('lu','xiao');

102list.insert('ni','head');

103list.insert('hellow','head');

104list.print()

105console.log('————-删除元素————')

106list.delete('ni')

107list.delete('xiao')

108list.print()

109console.log('————-按值查找————')

110list.findByValue('lu')

111console.log('————-按索引查找————')

112list.print()

五、测试用例

其实这里的测试用例主要用于判断我们写的程序到底对不对,我们一般都会输入一个自己认为的情况进行测试,这是错误的做法。程序最容易出错的还是边界情况考虑不全面导致的,所以,我们为了能够测试程序的全面性,所以我们要按照以下步骤进行全面性的测试。

1、普通测试

普通测试就是输入一个正常的值,比如单链表中插入数据

2、特殊测试

特殊输入可以参照上边边界条件中的特殊边界进行测试,比如在头部插入数据,在尾部插入数据等特殊情况的测试。

3、输入测试

对于输入测试的内容参考上边边界条件中的输入边界,比如:输入一个空链表测试一下程序能否正常的运行。

六、小结

做一个小结。今天的手写链表主要从五部分下手,从前到后依次为熟悉结构、理清思路、手写代码、测试用例。以后无论手写什么代码,有五步走,对于面试完全没有问题啦。

通过小鹿总结手写链表的方法,不用刻意去背,只要把思路理清楚,边界条件考虑全面,就不用去背,重复的练习。

————————————————

版权声明:本文为CSDN博主「一个不甘平凡的码农」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。

原文链接:https://blog.csdn.net/qq_36903042/article/details/101418889

赞赏支持

做小说我们是认真的,致力于为小说站爱好提供最好的源码模板!为国内前端工作者提供最全面的素材,为个人站长提供最有力的源码.同样的功能,我们价格低,同样的价格,我们功能多、售后好 !货比三家,没有最好只有更好.

程序员-动画:面试如何轻松手写链表?-书荒源码

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 程序员-动画:面试如何轻松手写链表?-书荒源码
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏