昨天参加中兴笔试，被一个单项链表的编程题给弄崩了。于是这几天开始学习Java与数据结构之间的知识。上过数据结构的课程，当时使用C++演示的，导致了我一直觉得Java和数据结构之间的关系不是很大。直到今天，看了《Java数据结构与算法》，才如梦方醒。恩，要好好学习。下面贴一下我的代码：

package datastructure;
/**
 * Java 数据结构-单向链表
 * @author aaaafei
 *
 */
class Link{
    /**
     * 链表节点
     */
    int value;
    Link next;
    
    public Link(){
        
    }
    public Link(int value) {
        this.value = value;
    }
    
    public void display() {
        if(this != null){
            System.out.println("{value:" + this.value + "}");
        }
    }
}

class LinkList{
    /**
     * 链表
     */
    private Link first;
    
    public boolean isEmpty(){
        if(first == null){
            System.out.println("Null LinkList");
            return true;
        }else{
            return false;
        }
    }
    public void display(){
        Link node = this.first;
        if(!isEmpty()){
            System.out.print("{value:");
            while(node.next != null){
                System.out.print(node.value +"->");
                node = node.next;
            }
            System.out.println(node.value + "}");
        }    
    }
    public void insertFirst(int value){
        Link node = new Link(value);
        node.next = first;
        first = node;
    }
    public Link find(int value){
        Link node = this.first;
        if(!isEmpty()){
            while(node.value != value){
                if(node.next == null){
                    return null;
                }else{
                    node = node.next;
                }
            }
            return node;
        }
        System.out.println("Not Found");
        return null;
    }
    public void delete(int value){
        Link node = this.first;
        Link previous = this.first;
        if(!isEmpty()){
            while(node.value != value){
                if(node.next != null){
                    previous = node;
                    node = node.next;
                }
            }
            if(node == first){
                first = first.next;
            }else{
                previous.next = node.next;
            }
        }
    }
}

public class LinkNodeApp {

    public static void main(String args[]){
        LinkList linklist = new LinkList();
//        linklist.display();
        linklist.insertFirst(1);
        linklist.insertFirst(2);
        linklist.insertFirst(3);
        linklist.insertFirst(4);
        linklist.insertFirst(5);
        linklist.display();
        linklist.delete(3);
        linklist.display();
    }
}

这里先主要讲下基本组成部分，第一部分是构建链表中单个节点的结构，这里在一个节点中值放了一个值。第二部分是构建链表，并且在这个类中完成新增、查找和删除功能。第三部分是测试用的，用来测试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中的写法。