数据分散的存储在物理空间中，通过一根线保存着它们之间的逻辑关系，这种存储结构称为链式存储结构
    实际上，就是每一个结点存放一个元素和一个指向下一个结点的引用（C语言里面是指针，Java中就是对象的引用，代表下一个结点对象）

    image.png
    利用这种思想，我们再来尝试实现上面的抽象类，从实际的代码中感受！

    比较：顺序表和链表的优异？

    顺序表优缺点：

    • 访问速度快，随机访问性能高
    • 插入和删除的效率低下，极端情况下需要变更整个表
    • 不易扩充，需要复制并重新创建数组

    链表优缺点：

    • 插入和删除效率高，只需要改变连接点的指向即可
    • 动态扩充容量，无需担心容量问题
    • 访问元素需要依次寻找，随机访问元素效率低下

    链表只能指向后面，能不能指向前面呢？双向链表！

    栈和队列实际上就是对线性表加以约束的一种数据结构，如果前面的线性表的掌握已经ok，那么栈和队列就非常轻松了！
    手动实现一个int链表

    1. package com.linkedlist;
    3. public class Node {
    4.   private int data;// 结点数据
    5.   private Node next;// 下一个结点
    7.   public Node(int data) {
    8.     this.data = data;
    9.   }
    11.   public int getData() {
    12.     return data;
    13.   }
    15.   public void setData(int data) {
    16.     this.data = data;
    17.   }
    19.   public Node getNext() {
    20.     return next;
    21.   }
    23.   public void setNext(Node next) {
    24.     this.next = next;
    25.   }
    26. }
    1. package com.linkedlist;
    3. import java.util.Hashtable;
    5. public class LinkedListOperator {
    6.   private Node head = null;// 头结点
    8.   // 在链表的末尾增加一个结点
    9.   private void addNode(int data) {
    10.     Node newNode = new Node(data);
    11.     if (head == null) {
    12.       head = newNode;
    13.       return;
    14.     }
    15.     Node temp = head;
    16.     while (temp.getNext() != null) {
    17.       temp = temp.getNext();
    18.     }
    19.     temp.setNext(newNode);
    20.   }
    22.   // 打印链表结点
    23.   private void printLink() {
    24.     Node curNode = head;
    25.     while (curNode != null) {
    26.       System.out.println(curNode.getData());
    27.       curNode = curNode.getNext();
    28.     }
    29.     System.out.println("===========");
    30.   }
    32.   // 求链表长度
    33.   private int getLength() {
    34.     int len = 0;
    35.     Node curNode = head;
    36.     while (curNode != null) {
    37.       len++;
    38.       curNode = curNode.getNext();
    39.     }
    40.     return len;
    41.   }
    43.   // 删除某一个结点
    44.   private boolean delNode(int index) {
    45.     if (index < 1) {
    46.       return false;
    47.     }
    48.     if (index == 1) {
    49.       head = head.getNext();
    50.       return true;
    51.     }
    52.     Node preNode = head;
    53.     Node curNode = head.getNext();
    54.     int n = 1;
    55.     while (curNode.getNext() != null) {
    56.       if (n == index) {
    57.         preNode.setData(curNode.getData());
    58.         preNode.setNext(curNode.getNext());
    59.         return true;
    60.       }
    61.       preNode = preNode.getNext();
    62.       curNode = curNode.getNext();
    63.       n++;
    64.     }
    65.     if (curNode.getNext() == null) {
    66.       preNode.setNext(null);
    67.     }
    68.     return false;
    69.   }
    71.   // 链表排序:选择排序法,从小到大
    72.   private void sortList() {
    73.     Node curNode = head;
    74.     while (curNode != null) {
    75.       Node nextNode = curNode.getNext();
    76.       while (nextNode != null) {
    77.         if (curNode.getData() > nextNode.getData()) {
    78.           int temp = curNode.getData();
    79.           curNode.setData(nextNode.getData());
    80.           nextNode.setData(temp);
    81.         }
    82.         nextNode = nextNode.getNext();
    83.       }
    84.       curNode = curNode.getNext();
    85.     }
    86.   }
    88.   // 去掉重复元素
    89.   private void distinctLink() {
    90.     Hashtable<Integer, Integer> map = new Hashtable<Integer, Integer>();
    91.     Node curNode = head;
    92.     Node preNode = null;
    93.     while (curNode != null) {
    94.       if (map.containsKey(curNode.getData())) {
    95.         preNode.setData(curNode.getData());
    96.         preNode.setNext(curNode.getNext());
    97.       } else {
    98.         map.put(curNode.getData(), 1);
    99.         preNode = curNode;
    100.       }
    101.       curNode = curNode.getNext();
    102.     }
    103.   }
    105.   // 返回倒数第k个结点,定义两个指针,第一个指针向前移动K-1次,之后两个指针同时前进,
    106.   // 当第一个指针到达末尾时,第二个指针所在的位置即为倒数第k个结点
    107.   private Node getReverNode(int k) {
    108.     if (k < 1) {
    109.       return null;
    110.     }
    111.     Node first = head;
    112.     Node second = head;
    113.     for (int i = 0; i < k - 1; i++) {
    114.       first = first.getNext();
    115.     }
    116.     while (first.getNext() != null) {
    117.       first = first.getNext();
    118.       second = second.getNext();
    119.     }
    120.     return second;
    121.   }
    123.   // 反转链表
    124.   private void reserveLink() {
    125.     Node preNode = null;
    126.     Node curNode = head;
    127.     Node tempNode = null;
    128.     while (curNode != null) {
    129.       tempNode = curNode.getNext();
    130.       curNode.setNext(preNode);
    131.       preNode = curNode;
    132.       curNode = tempNode;
    133.     }
    134.     head = preNode;
    135.   }
    137.   // 寻找链表的中间结点
    138.   private Node getMiddleNode() {
    139.     Node slowNode = head;
    140.     Node quickNode = head;
    141.     while (slowNode.getNext() != null && quickNode.getNext() != null) {
    142.       slowNode = slowNode.getNext();
    143.       quickNode = quickNode.getNext().getNext();
    144.     }
    145.     return slowNode;
    146.   }
    148.   // 判断链表是否有环
    149.   private boolean isRinged() {
    150.     if (head == null) {
    151.       return false;
    152.     }
    153.     Node slowNode = head;
    154.     Node quickNode = head;
    155.     while (slowNode.getNext() != null && quickNode.getNext() != null) {
    156.       slowNode = slowNode.getNext();
    157.       quickNode = quickNode.getNext().getNext();
    158.       if (slowNode.getData() == quickNode.getData()) {
    159.         return true;
    160.       }
    161.     }
    162.     return false;
    163.   }
    165.   // 删除指定结点
    166.   private boolean delNode(Node node) {
    167.     if (node.getNext() == null) {
    168.       return false;// 在不知道头结点的情况下,没法删除单链表的尾结点
    169.     }
    170.     node.setData(node.getNext().getData());
    171.     node.setNext(node.getNext().getNext());
    172.     return true;
    174.   }
    176.   // 判断两个链表是否相交:相交的链表的尾结点相同
    177.   private boolean isCross(Node n1, Node n2) {
    178.     while (n1.getNext() != null) {
    179.       n1 = n1.getNext();
    180.     }
    181.     while (n2.getNext() != null) {
    182.       n2 = n2.getNext();
    183.     }
    184.     if (n1.getData() == n2.getData()) {
    185.       return true;
    186.     }
    187.     return false;
    188.   }
    190.   // 求相交链表的起始点
    191.   private Node getFirstCrossNode(LinkedListOperator l1, LinkedListOperator l2) {
    192.     int len = l1.getLength() - l2.getLength();
    193.     Node n1 = l1.head;
    194.     Node n2 = l2.head;
    195.     if (len > 0) {
    196.       for (int i = 0; i < len; i++) {
    197.         n1 = n1.getNext();
    198.       }
    199.     } else {
    200.       for (int i = 0; i < len; i++) {
    201.         n2 = n2.getNext();
    202.       }
    203.     }
    204.     while (n1.getData() != n2.getData()) {
    205.       n1 = n1.getNext();
    206.       n2 = n2.getNext();
    207.     }
    208.     return n1;
    209.   }
    211.   public static void main(String[] args) {
    212.     LinkedListOperator llo = new LinkedListOperator();
    213.     llo.addNode(10);
    214.     llo.addNode(4);
    215.     llo.addNode(6);
    216.     llo.addNode(8);
    217.     llo.printLink();
    218.     // llo.delNode(4);
    219.     // llo.sortList();
    220.     // llo.distinctLink();
    221.     // System.out.println(llo.getReverNode(3).getData());
    222.     // llo.reserveLink();
    223.     // System.out.println(llo.getMiddleNode().getData());
    224.     // System.out.println(llo.isRinged());
    225.     llo.delNode(llo.head.getNext().getNext());
    226.     llo.printLink();
    227.   }
    228. }