从jvm的角度考虑链表是如和存储的，并手写Java单向链表的，问题难在节点和头节点的对象引用

我们都希望手写一个链表算法，但链表的算法有点复杂，尤其是节点的问题，网上也有很多关于链表的操作，但往往是只写出了链表，没有从jvm的角度考虑链表是如和存储的，因而，我今天就我写的链表和大家分享。

1、一个简单的例子

在这个例子中，实用当前类作为自己的属性，就相当于链表当中的节点。

package com.myproject.linklist;

import lombok.Getter;
import lombok.NoArgsConstructor;

/**
 * Created By zby on 16:45 2018/9/6 0006
 * <p>
 *  
 * @author 祝宝亚
 *  
 * 这只是一个测试的类，用来说明链表是如何执行，
 * 所谓的链表，就是在该类中定义一个本身属性
 * 当我们用getNode调用，返回的还是该类的对象
 * 然后，再接着一直调用下去，因而，会有链表的
 * 头指针和next的存储数据
 */
@NoArgsConstructor
public class Node<T> {

    /**
     * 定义一个本身的属性
     */
    private Node<T> next;

    /**
     * 数据
     */
    @Getter
    public T data;

    public Node(T data) {
        this.data = data;
    }

    /**
     * 设置当前对象引用该类其他对象的引用
     *
     * @param node
     */
    public void setNext(Node<T> node) {
        this.next = node;
    }

    /**
     * 返回当前对象引用
     *
     * @return
     */
    public Node<T> getNext() {
        return next;
    }
}

我们在来个测试的类

public class NodeTest {

    @Test
    public void testNode(){
        Node head=new Node("head");  //相当于头指针
        Node node1=new Node("数据1");
        Node node2=new Node("数据2");
        Node node3=new Node("数据3");

        head.setNext(node1);  //node1指向下一个引用
        node1.setNext(node2); //node2指向下一个引用
        node2.setNext(node3); //node3指向下一个引用

        System.out.println(head.getNext().getNext());
        System.out.println(node1.getNext());
    }
 }
output:
	com.myproject.linklist.Node@28c97a5
	com.myproject.linklist.Node@28c97a5

你会发现输出的是同一个对象，为什么会输出同一个对象呢，在我的Node类中，有一个这样的方法， public void setNext(Node node) { this.next = node;}当前对象指向新对象的引用，存储是新对象的引用地址。于是，输出各个对象的地址：

 System.out.println("head的内存地址--> "+head);
 System.out.println("node1的内存地址-->"+node1);
 System.out.println("node2的内存地址-->"+node2);
 System.out.println("node3的内存地址-->"+node3);

output:
	head的内存地址--> com.myproject.linklist.Node@28c97a5
	node1的内存地址-->com.myproject.linklist.Node@6659c656
	node2的内存地址-->com.myproject.linklist.Node@6d5380c2
	node3的内存地址-->com.myproject.linklist.Node@45ff54e6

你会发现head.getNext().getNext()和node1.getNext()输出的都是node2的地址，我们来分析一下其内存地址：

1. 当程序执行到Node head=new Node(“head”);时，jvm会去查找是否有Node这个类，如果没有即把它的字节码加进来，如果有，我们即在堆中声明Node对象，该对象只存储属性。因为方法是所有堆共享的。又在栈中开辟一个地址，存储该对象在内存中的首地址。为什么是首地址？因为该对象的的属性存储不同的地址，我们存储该对象的首地址呢，即可通过引用变量来找到该对象。于是，node1，node2，node3便存储各个对象的首地址。
2. 当执行到 head.setNext(node1); 这里时，我们看代码如何改变public void setNext(node1) { head.next = node1; }head.next指向node1的首地址，也就是，存储node1的首地址。而node1的首地址就是new Node(“数据1”)。其他也是如此
3. 当setNode方法结束之后，引用变量就失去了意义，在堆内部就形成了一个链，链的节点就是通过next的存储下一个节点对象的地址，这就是单向链表的雏型。堆通过next存储的下一个对象的首地址，来寻找下一个对象。
4. 如果形成真正的单向链表，最重要的是当前对象的next属性如何指向下一个对象的首地址，这就需要一个临时引用变量，也就是我们常说的头结点，即head属性，类型是Node。
5. 我们在链表内编写一个Node内部类，有两个属性，一个是data属性，类型是泛型；一个next，类型是Node，表示下一个节点。如果是双向链表，还有一个previous，表示上一个节点。

因而，根据流程图，我们来写链表类

链表类

package com.myproject.linklist;

import java.io.Serializable;
import java.util.Arrays;

/**
 * Created By zby on 9:05 2018/9/7 0007
 * 
 * 设计链表,里面有一个内部类，设置节点，指定新的node引用
 * 将数据封装到node对象中。
 */
public class LinkedList<E> implements Serializable {

    /**
     * 链接链接大大小
     */
    private int size;

    public int getSize() {
        return size;
    }

    /**
     * 头结点
     */
    private Node head;

    /**
     * 节点的内部类，为什么要用这个内部类，
     * 因为外部类可以访问内部类的属性
     *
     * @param <E>
     */
    class Node<E> {
        /**
         * 当前对象的内部属性，指向下一个node对象，
         * 即存储下一个节点的引用地址
         */
        private Node next;

        /**
         * 存储的具体的数据
         */
        private E data;

        public Node(E data) {
            this.data = data;
        }
    }

     /**
     * 在head之后插入新界点
     *
     * @param data
     * @return
     */
    public E addAfterHead(E data) {
        isEmpty(data);
        Node node=new Node(data);
        if (head != null){
            //如果head不等于null,那么就存储当前节点对象的首地址
            head.next=node;
        }
        //包括为头结点为null的情况，头结点存储当前对象的首地址
        head=node;
        size++;
        return data;
    }

我们来做个测试类：

public class LinkedListTest {

    @Test
    public void testAddHead() {
        LinkedList<String> linkedList = new LinkedList<>();

        System.out.println(linkedList.addAfterHead("祝宝亚1"));
        System.out.println(linkedList.addAfterHead("祝宝亚2"));
        System.out.println(linkedList.addAfterHead("祝宝亚3"));
    }
}