类的基本结构

在单向链表中，有头指针header,以及具体的值节点，每个节点知道知道它的下一个元素。

public class SinglyLinkedList {
    /**
     * 头指针
     */
    private Node head = null;

    /**
     * 链表节点类
     * 使用最简单的int类型来进行说明
     * 作为静态内部类的场景
     */
    private static class Node {
        /**
         * 节点值
         */
        int value;

        /**
         * 指向的下一个节点
         */
        Node next;

        /**
         * 构造方法,一般用于创建头指针
         *
         * @param value 节点值
         * @param next  指向的下一个指针
         */
        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }
}

属性说明：

• 类Node,作为链表的单个节点，以内部静态类的方式存在，相当于对外暴露的只有SinglyLinkedList，没有暴露Node，封装的效果更好。
• 头指针header,用于指向第一个值节点。

具体方法

方法1： 添加头元素addFirst

第一个版本，添加头元素的时候，正常情况下，需要考虑链表是否为空的情况。

/**
 * 添加第一个值节点的方法
 *
 * @param value 待添加的内容的值
 */
@Deprecated
public void addFirstHistoryV1(int value) {
    if (head == null) {
        // case1: 链表为空, tip 此时head和next指针都是null(可以合并)
        head = new Node(value, null);
    } else {
        // case2: 链表不为空,将header指针指向的内容，赋值给新创建头节点的next指针，从而实现增加第一个值元素的功能
        head = new Node(value, head);
    }
}

实际上两种情况，可以合并一种写法，如下：

/**
 * 链表添加第一个值节点的方法
 * tip 能同时兼容链表为空和链表不为空的2种情况
 *
 * @param value 待添加的内容的值
 */
public void addFist(int value) {
    head = new Node(value, head);
}

方法2：遍历元素

跟动态数组类似，也是有几种迭代的方法，我们一个一个来说明。

1. 最简单的遍历打印

   /**
    * 遍历链表元素
    */
   public void loopHistoryV1() {
       // 初始位置为head指针指向的内容，即第一个值节点
       Node p = head;
       while (p != null) {
           System.out.println(p.value);
           // 打印一个值节点， 再查找下一个值节点
           p = p.next;
       }
   }
   

2. 使用while循环实现遍历，并执行操作

   /**
    * 使用while循环的内容遍历
    *
    * @param consumer 传递进来的Consumer，用于执行具体操作
    */
   public void loop(Consumer<Integer> consumer) {
       // 初始位置为head指针指向的内容，即第一个值节点
       Node p = head;
       while (p != null) {
           consumer.accept(p.value);
           // 打印一个值节点， 再查找下一个值节点
           p = p.next;
       }
   }
   

3. 使用for循环实现遍历，并执行操作

   /**
    * 使用for循环实现链表内容遍历
    *
    * @param consumer 传递进来的Consumer，用于执行具体操作
    */
   public void forLoop(Consumer<Integer> consumer) {
       for (Node p = head; p != null; p = p.next) {
           consumer.accept(p.value);
       }
   }
   

4. 实现Iterable实现遍历，并执行操作
   第一步：类继承Iterable

   public class SinglyLinkedList implements Iterable<Integer>{}
   

   第二步：实现iterator方法

   /**
    * 实现java.util.Iterator，使用增强for循环进行遍历
    *
    * @return Iterator<Integer>
    */
   @Override
   public Iterator<Integer> iterator() {
       return new Iterator<Integer>() {
           Node node = head;
   
           @Override
           public boolean hasNext() {
               // tip 循环结束的条件是最后一个是null
               return node != null;
           }
   
           @Override
           public Integer next() {
               int value = node.value;
               node = node.next;
               return value;
           }
       };
   }