昨天参加中兴笔试，被一个单项链表的编程题给弄崩了。于是这几天开始学习Java与数据结构之间的知识。上过数据结构的课程，当时使用C++演示的，导致了我一直觉得Java和数据结构之间的关系不是很大。直到今天，看了《Java数据结构与算法》，才如梦方醒。恩，要好好学习。下面贴一下我的代码：
1package datastructure; 2/** 3 * Java 数据结构-单向链表 4 * @author aaaafei 5 * 6 */ 7class Link{ 8 /** 9 * 链表节点 10 */ 11 int value; 12 Link next; 13 14 public Link(){ 15 16 } 17 public Link(int value) { 18 this.value = value; 19 } 20 21 public void display() { 22 if(this != null){ 23 System.out.println("{value:" + this.value + "}"); 24 } 25 } 26} 27 28class LinkList{ 29 /** 30 * 链表 31 */ 32 private Link first; 33 34 public boolean isEmpty(){ 35 if(first == null){ 36 System.out.println("Null LinkList"); 37 return true; 38 }else{ 39 return false; 40 } 41 } 42 public void display(){ 43 Link node = this.first; 44 if(!isEmpty()){ 45 System.out.print("{value:"); 46 while(node.next != null){ 47 System.out.print(node.value +"->"); 48 node = node.next; 49 } 50 System.out.println(node.value + "}"); 51 } 52 } 53 public void insertFirst(int value){ 54 Link node = new Link(value); 55 node.next = first; 56 first = node; 57 } 58 public Link find(int value){ 59 Link node = this.first; 60 if(!isEmpty()){ 61 while(node.value != value){ 62 if(node.next == null){ 63 return null; 64 }else{ 65 node = node.next; 66 } 67 } 68 return node; 69 } 70 System.out.println("Not Found"); 71 return null; 72 } 73 public void delete(int value){ 74 Link node = this.first; 75 Link previous = this.first; 76 if(!isEmpty()){ 77 while(node.value != value){ 78 if(node.next != null){ 79 previous = node; 80 node = node.next; 81 } 82 } 83 if(node == first){ 84 first = first.next; 85 }else{ 86 previous.next = node.next; 87 } 88 } 89 } 90} 91 92public class LinkNodeApp { 93 94 public static void main(String args[]){ 95 LinkList linklist = new LinkList(); 96// linklist.display(); 97 linklist.insertFirst(1); 98 linklist.insertFirst(2); 99 linklist.insertFirst(3); 100 linklist.insertFirst(4); 101 linklist.insertFirst(5); 102 linklist.display(); 103 linklist.delete(3); 104 linklist.display(); 105 } 106}
这里先主要讲下基本组成部分，第一部分是构建链表中单个节点的结构，这里在一个节点中值放了一个值。第二部分是构建链表，并且在这个类中完成新增、查找和删除功能。第三部分是测试用的，用来测试LinkList中的方法效果。代码不复杂，接下来我想在继续说下我在写的过程中遇到的几个问题：
（1）.链表新增时，都是将新来的数据插入链表的头部，比如第一个新增的数为1，第二个为2，那么链表就是由2指向1，就是2→1.如果依次新增1,2,3,4,5.那么指向关系就是5→4→3→2→1.
（2）我在进行查找时，遍历链表，一开始是用的向display方法中的遍历思路来进行遍历，在查看了那本经典之作后，才改为这种方式，确实这种方式更加直观，直接判断当前的节点的值是否相等，在判断是否为最后一个节点；而不是判断当前是否还有下个节点，在判断当前节点值是否相等。这样确实更巧妙。
（3）最后一个是我想重点阐述的部分。那就是在删除方法中，一开始我一直不理解，全程都没有对first对象进行操作，为什么就会删除成功呢。想了之后，意识到应该是Java中对象引用以及对象赋值的知识点，这部分不少教材都说的不是很清楚，我也说下我现在的理解，如有不对，请大家指正。
第一，上文中说的first对象，这种说法就是错误的。因为first只是一个对象引用变量，它不是一个对象，而是指向一个对象的值。那么什么是对象呢。举个例子，Link node; node = new Link(); 这两句中，node是对象引用值，这是刚创建出来，它是null，也就是没有指向任何一个对象。new表明在堆空间中开辟存储区域，存储对象实体，Link表明是Link类型的实体，()表明调用Link类的构造方法。=符号的含义就是将node指向堆空间中的对象实体。例如在写一句，Link node2 = node；表明新建一个对象引用的值，指向和node相同，那么现在就是说有两个对象引用指向同一个实体。图不是很准确，毕竟链表在内存中并不是连续的。
那么就用这个知识点来看下display方法，方法体中创建一个新的对象引用值，共同指向一个对象实体，其中first的指向一直没有变，而node的指向却是在一格一格的向后跳。图不是很准确，毕竟链表在内存中并不是连续的。所以，因为first一直指向着，所以这个内存实体一直存在，并没有被JVM当做垃圾给回收了。
第二，用这个知识点来看delete方法，同样有下面的图：
一开始，first、node和previous都是同一个指向，接下来，三者有了不同的指向，接着发现了要删除的元素了，previous.next = node.next，表达了这样的含义，将previous指向的节点的next值变为node指向的节点的next值，而这时first依然指向第一个节点，但是之后的节点的内容已经被改变了。这时，node指向那个节点就已经被舍弃了，随着node生命周期的结束，其指向的对象实体，就被JVM当做垃圾了。
因此，正是对象引用的特点，才有了delete中的写法。