介绍

线性表是 n 个数据元素的有限序列，最常用的是链式表达，通常也叫作线性链表或者链表。在链表中存储的数据元素也叫作节点，一个节点存储的就是一条数据记录。

单向链表的实现

/**
 * 单链表的节点
 */
public class Node<Data> {
    private Data data;
    private Node<Data> next;
    private int size = 0;
    private Node<Data> firstNode;//头节点
    private Node<Data> lastNode;//尾节点

    public Node(Data data) {
        this.data = data;
        if (firstNode == null) {
            firstNode = new Node<>(data, null);
        }
        size++;
    }

    private Node(Data data, Node<Data> next) {
        this.data = data;
        this.next = next;
    }

    /**
     * 插入元素
     *
     * @param d 数据
     */
    public void addData(Data d) {
        if (firstNode == null) {
            firstNode = new Node<>(d, null);
        } else if (lastNode == null) {
            lastNode = new Node<>(d, null);
            firstNode.next = lastNode;
        } else {
            lastNode.next = new Node<>(d, null);
            lastNode = lastNode.next;
        }
        size++;
    }

    /**
     * 删除元素
     * 单向链表只能从头向尾遍历
     *
     * @param d 数据
     */
    public void deleteData(Data d) {
        if (firstNode == null) {
            return;
        } else {
            if (lastNode == null) {
                if (firstNode.data == d) {
                    firstNode = null;
                }
            } else {
                Node<Data> tmpNode = firstNode;
                while (tmpNode != null) {
                    if (tmpNode.next != null && tmpNode.next.data == d) {
                        tmpNode.next = tmpNode.next.next;
                    }
                    tmpNode = tmpNode.next;
                }
            }
            size--;
        }
    }

    public int getSize() {
        return size;
    }

    public Data getData() {
        return data;
    }

    @Override
    public String toString() {
        Node<Data> tmpNode = firstNode;
        StringBuilder string = new StringBuilder();
        while (tmpNode != null) {
            string.append(tmpNode.data + " ");
            tmpNode = tmpNode.next;
        }
        return string.toString();
    }
  
}

Node类内部定义了要存储的数据Data和指向下一个节点的指针，以及链表头部和尾部指针。

几种算法

案例1、奇数链表中查找到中间的元素和位置。
链表只能通过头指针向后一个一个的去遍历元素，那么如何能够快速的找到奇数链表中查找到中间的元素和位置呢？有两种方法：
方法1 如果知道长度，就按照从头到尾一次遍历计算位置，进行比较。
方法2 如果不知道长度，可以采用快指针和慢指针的方法，关于快慢指针可以自行百度。
这里实现以下快慢指针：

 /**
     * 如果是奇数查找中间元素
     */
    public Node<Data> findMiddle() {
        if (size > 1 && ((size & 1) == 1)) {
            Node<Data> fastPointerNode = firstNode.next.next;
            Node<Data> slowPointerNode = firstNode.next;
            int index = 1;
            while (fastPointerNode!=null&&fastPointerNode.next != null){
                fastPointerNode = fastPointerNode.next.next;
                slowPointerNode = slowPointerNode.next;
                index++;
            }
            System.out.println("中间位置是:"+index);
            return slowPointerNode;
        }
        return null;
    }

案例2：对链表进行反向旋转
为了解决这个问题，我们需要构造三个指针 prev、curr 和 next，对当前结点、以及它之前和之后的结点进行缓存，再完成翻转动作。

    /**
     * 翻转链表
     */
    public void reverseNode(){
        if (size>1) {
            Node<Data> current = firstNode.next;
            Node<Data> previous = firstNode;
            Node<Data> next = null;
            while (current!=null){
                next = current.next;
                current.next = previous;
                if (previous==firstNode) {
                    previous.next=null;
                }
                previous = current;
                current = next;
            }
            firstNode = previous;
        }

    }

这里容易犯一个错误，在第一次循环的时候忘记把previous.next=null;那么就会导致firstNode和下一个节点相互引用，在遍历的时候导致内存溢出。

总结

当数据的个数不确定时，而且经常添加和删除数据时，可以选择链表。
单链表和双向链表的区别是：双向链表可以从两端遍历，单项链表只能用一端遍历。