前言

在日常的数据操作中，链表比数组在内存使用方面，拥有更多优势。所以简单学习了一下链表。
数组：在内存中需要连续空间。
链表：在内存中可以是不连续的空间。

数组优于链表优势

（1）数组内存空间占用的少,因为链表节点会附加上一块或两块下一个节点的信息.但是数组在建立时就固定了.所以也有可能会因为建立的数组过大或不足引起内存上的问题.
（2）数组内的数据可随机访问.但链表不具备随机访问性.这个很容易理解.数组在内存里是连续的空间.比如如果一个数组地址从 100 到 200,且每个元素占用两个字节,那么 100-200 之间的任何一个偶数都是数组元素的地址.可以直接访问.链表在内存地址可能是分散的.所以必须通过上一节点中的信息找能找到下一个节点.
（3）数组查找速度更快，这个也是因为内存地址的连续性的问题.

数组优缺点：

• 优点：使用方便 ，查询效率 比链表高，内存为一连续的区域
• 缺点：大小固定，不适合动态存储，不方便动态添加

链表优于数组的优势

（1）插入与删除的操作快.如果数组的中间插入一个元素,那么这个元素后的所有元素的内存地址都要往后移动.删除的话同理.只有对数组的最后一个元素进行插入删除操作时,才比较快.链表只需要更改有必要更改的节点内的节点信息就够了.并不需要更改节点的内存地址.
（2）内存地址的利用率高.不管你内存里还有多少空间,如果没办法一次性给出数组所需要的空间,那就会提示内存不足,磁盘空间整理的原因之一在这里.而链表可以是分散的空间地址.
（3）链表的扩展性比数组好.因为一个数组建立后所占用的空间大小就是固定的.如果满了就没法扩展.只能新建一个更大空间的数组.而链表不是固定的,可以很方便的扩展.

链表优缺点

• 优点：可动态添加删除 大小可变
  
• 缺点：只能通过顺次指针访问，查询效率低

链表的增删改查，详见 code

public class MyLink {
        Node head = null; // 头节点

        /**
         * 链表中的节点，data代表节点的值，next是指向下一个节点的引用
         *
         * @author zjn
         *
         */
        class Node {
            Node next = null;// 节点的引用，指向下一个节点
            int data;// 节点的对象，即内容

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

        /**
         * 向链表中插入数据
         *
         * @param d
         */
        public void addNode(int d) {
            Node newNode = new Node(d);// 实例化一个节点

            //如果head头节点为空，插入数据到头节点
            if (head == null) {
                head = newNode;
                return;
            }


            Node tmp = head;
            //从head开始遍历，直到找到链表中最后一个节点
            while (tmp.next != null) {
                tmp = tmp.next;
            }
            //插入数据到链表中最后一个节点
            tmp.next = newNode;
        }

        /**
         *
         * @param index:删除第index个节点
         * @return
         */
        public boolean deleteNode(int index) {
            //删除第index个节点，如果index<1或index>length，返回false
            if (index < 1 || index > length()) {
                return false;
            }

            //如果index=1，删除头节点
            if (index == 1) {
                head = head.next;
                return true;
            }

            int i = 2;
            Node preNode = head;  //节点head的引用
            Node curNode = preNode.next; //curNode为preNode的下一个节点

            while (curNode != null) {
                //假设index=2
                //第一次循环，preNode = head.next, preNode.index=2
                //curNode.index=3
                if (1 == index) {
                    head = head.next;
                } else if (i == index) {
                    preNode.next = curNode.next;
                    return true;
                } else {
                    i++;
                    preNode = curNode;
                    curNode = curNode.next;
                }

            }
            return false;
        }

        /**
         *
         * @return 返回节点长度
         */
        public int length() {
            int length = 0;
            Node tmp = head;
            while (tmp != null) {
                length++;
                tmp = tmp.next;
            }
            return length;
        }

        /**
         * 在不知道头指针的情况下删除指定节点
         *
         * @param n
         * @return
         */
        public boolean deleteNode11(Node n) {
            if (n == null || n.next == null) {
                return false;
            }
            int tmp = n.data;
            n.data = n.next.data;
            n.next.data = tmp;
            n.next = n.next.next;
            System.out.println("删除成功！");
            return true;
        }

        //链表遍历
        public void printList() {
            Node tmp = head;
            while (tmp != null) {
                System.out.println(tmp.data);
                tmp = tmp.next;
            }
        }

        public static void main(String[] args) {
            MyLink list = new MyLink();
            list.addNode(5);
            list.addNode(3);
            list.addNode(1);
            list.addNode(2);
            list.addNode(55);
            list.addNode(36);
            System.out.println("linkLength:" + list.length());
            System.out.println("head.data:" + list.head.data);
            list.printList();
            list.deleteNode(3);
            System.out.println("After deleteNode(3):");
            list.printList();
        }
}