我的一个朋友过来面试引发我要说的一个小话题

概述 在很多家公司面试，也包括在携程，大多都会被问到一些算法的问题，其中机票事业部的面试，基本上算是算法问题的重灾区，没办法，有几个领导喜欢用数据结构来考人家，其中包括一些常见数据结构的复杂度以及手写一些算法，比如快排，单链表等等，前几天我一个推荐过来的朋友膝盖就被中了一箭。题目就不方便具体说了，第一小问就是用非递归来构建一个单链表，我们知道构建单链表可以说是学数据结构的基本功，一说到用链式结构，它跟递归又有了千丝万缕的联系，很多链式的问题，我们用递归就可以轻轻松松的解决，几乎不需要动一下脑子，但是如果用非递归的话，那就稍微比递归要复杂一点了，起码会多考一个引用类型内存分配的问题。     后来QQ上我就用递归和非递归的形式构建单链表回复了他，先给了一个递归的版本，这个没问题，可以消化，然后给了一个非递归的版本，看了之后就扛不住了。 一：递归版本1 class LinkList2 {3 public class LinkNode4 {5 public int data;67 public LinkNode next;8 }910 private LinkNode head;1112 public void Add(int data)13 {14 if (head == null)15 {16 head = new LinkNode() { data = data };17 }18 else19 {20 Add(head, data);21 }22 }2324 public void Add(LinkNode node, int data)25 {26 if (node.next == null)27 {28 node.next = new LinkNode() { data = data };29 return;30 }3132 Add(node.next, data);33 }34 }二：非递归版本1 class LinkList2 {3 public class LinkNode4 {5 public int data;67 public LinkNode next;8 }910 private LinkNode head;1112 public void Add(int data)13 {14 LinkNode node = new LinkNode() { data = data };1516 if (head == null)17 {18 head = node;19 }20 else21 {22 LinkNode temp = head;2324 while (temp.next != null)25 {26 temp = temp.next;27 }2829 temp.next = node;30 }31 }32 }这个非递归不理解的地方在于临时变量temp，提出的问题就是为什么：“temp.next=node” 之后，head的值发生了改变？我想之所以不能理解，绝逼是对引用类型的内存分配不了解，而这个非递归版本恰恰就是用引用类型这个内存分配技巧来实现 ”非递归构建单链表“。。。为了不让别人踩上这个坑，我还是大概说一下流程，大概是这样的，当我们在new一个引用类型的时候，CLR就要计算实例字段和所有基类上的实例字段的大小，然后再在堆上分配合理的内存块，最后把堆上的内存块的首地址保存在栈上面。 为了方便理解，现在假如LinkList里面有三个结点：instance1 -> instance2 -> instance3, 第一句：1 LinkNode temp = head; 这个句子不难理解吧，把head的地址赋给temp，那么栈上temp的地址也就是head的地址，head的地址就是指向instacnce1内存块地址。 第二句： 从这句while中可以看到，一直在找instance的next，可以看出之后把instance2的内存地址给了temp，再next之后就把instance3的内存地址给            了temp，然后就发现instance3的next为null，然后就跳出循环。1 while (temp.next != null)2 {3 temp = temp.next;4 }第三句：从上一句可以看到，instance3的next已经为null了，这时候就把新构建的结点：LinkNode node = new LinkNode() { data = data };赋           给temp的next指针上来继续构建链表。1 temp.next = node;可以看到这时候instance4就构造到了instance3之后，同时temp.next已经是保存instance4的内存地址，这一些 *** 作对head来说都是透明的，它也不管后面怎么 *** 作，当你遍历head的时候会惊奇的发现居然我的链表中多了一个instance4，这个也就是朋友疑惑的地方，如果看到这个内存分配图的话，也许会豁然开朗，当然这篇博文没什么技术含量，也是自己一时有感而发。 

　　在很多家公司面试，也包括在携程，大多都会被问到一些算法的问题，其中机票事业部的面试，基本上算是算法问题的重灾区，没办法，有几个领导喜欢

用数据结构来考人家，其中包括一些常见数据结构的复杂度以及手写一些算法，比如快排，单链表等等，前几天我一个推荐过来的朋友膝盖就被中了一箭。

　　题目就不方便具体说了，第一小问就是用非递归来构建一个单链表，我们知道构建单链表可以说是学数据结构的基本功，一说到用链式结构，它跟递归

又有了千丝万缕的联系，很多链式的问题，我们用递归就可以轻轻松松的解决，几乎不需要动一下脑子，但是如果用非递归的话，那就稍微比递归要复杂一点

了，起码会多考一个引用类型内存分配的问题。

     后来QQ上我就用递归和非递归的形式构建单链表回复了他，先给了一个递归的版本，这个没问题，可以消化，然后给了一个非递归的版本，看了之后就扛

不住了。

一：递归版本

Add( (head == head = linkNode() { data = Add(linkNode node, (node.next == node.next = linkNode() { data = }

二：非递归版本

Add( linkNode node = linkNode() { data = (head == head = linkNode temp = (temp.next != temp = }

这个非递归不理解的地方在于临时变量temp，提出的问题就是为什么：“temp.next=node” 之后，head的值发生了改变？我想之所以不能理解，绝逼是对

引用类型的内存分配不了解，而这个非递归版本恰恰就是用引用类型这个内存分配技巧来实现 ”非递归构建单链表“。。。为了不让别人踩上这个坑，我还是大

概说一下流程，大概是这样的，当我们在new一个引用类型的时候，CLR就要计算实例字段和所有基类上的实例字段的大小，然后再在堆上分配合理的内存块，

最后把堆上的内存块的首地址保存在栈上面。

为了方便理解，现在假如linkList里面有三个结点：instance1 -> instance2 -> instance3, 

第一句：

linkNode temp = head;

这个句子不难理解吧，把head的地址赋给temp，那么栈上temp的地址也就是head的地址，head的地址就是指向instacnce1内存块地址。

第二句： 从这句while中可以看到，一直在找instance的next，可以看出之后把instance2的内存地址给了temp，再next之后就把instance3的内存地址给

            了temp，然后就发现instance3的next为null，然后就跳出循环。

(temp.next != temp = }

第三句：从上一句可以看到，instance3的next已经为null了，这时候就把新构建的结点：linkNode node = new linkNode() { data = data };赋

           给temp的next指针上来继续构建链表。

temp.next = node;

可以看到这时候instance4就构造到了instance3之后，同时temp.next已经是保存instance4的内存地址，这一些 *** 作对head来说都是透明的，它也不管

后面怎么 *** 作，当你遍历head的时候会惊奇的发现居然我的链表中多了一个instance4，这个也就是朋友疑惑的地方，如果看到这个内存分配图的话，

也许会豁然开朗，当然这篇博文没什么技术含量，也是自己一时有感而发。

总结

以上是内存溢出为你收集整理的我的一个朋友过来面试引发我要说的一个小话题全部内容，希望文章能够帮你解决我的一个朋友过来面试引发我要说的一个小话题所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/1264087.html