单向链表（java实现）

线性表的链式存储和顺序存储的区别在于：顺序存储能够指定索引随机的读取该位置的元素，但在随机插入方面不擅长，在表中插入新元素时需要移动大量的已有元素；而链式存储则恰好相反，在插入元素方面，他只要通过调整对应位置的指针即可完成插入而不需要移动元素，在随机读取方面却不擅长，需要通过表头指针依次读取才能找到指定位置的元素；

单向链表的节点基本结构为一个存储数据的属性和一个指向其后继的指针，如下图；

链表节点.png

因此创建如下链表节点类；

/**
 * node list class.
 * @param <T> node element data type
 */
class Node<T> {
    T data;
    Node<T> next;
}

而对于链表本身是将节点通过指针连接起来，其自身有size属性表示链表中当前元素个数 和固定的head节点（head节点数据域为空）其后继指针指向链表第一个元素；单链表最后一个元素后继指向null，而循环链表最后一个元素的tail指向head；

单链表.png
单项循环链表.png

java实现如下；

public class NodeList<T extends Comparable> {
    private int size;
    private final Node<T> head;
    //private Node<T> tail;

    public NodeList() {
        size = 0;
        head = new Node<>();
        //tail = head;
    }

    @SafeVarargs
    public NodeList(T... dataPoints) {
        this();
        for (T data : dataPoints) {
            insertAtLast(data);
        }
    }

    public void insertAtLast(T data) {
        Node<T> temp = new Node<>();
        temp.data = data;
        Node<T> tail = head;
        while(tail.next != null) {
            tail = tail.next;
        }
        tail.next = temp;
        //tail = temp;
        size++;
    }

    public Node<T> locate(T data) {
        Node<T> result;
        result = head;
        while (result.next != null) {
            if (result.next.data == data) {
                break;
            }
            result = result.next;
        }
        return result.next;
    }

    public void insert(T data, Node<T> node) {
        if (node.next == null) {
            insertAtLast(data);
            return;
        }
        Node<T> temp = new Node<>();
        temp.data = data;
        temp.next = node.next;
        node.next = temp;
        size++;
    }

    public void insertAt(T data, int index) {
        T dataAtIndex = getData(index);
        Node<T> node = locate(dataAtIndex);
        insert(data, node);
    }

    public void deleteAt(int index) {
        if (index < 1 || index > size) {
            throw new IndexOutOfBoundsException("index should between 1 to " + size);
        }

        int position = 1;
        Node<T> current = head;
        while (current != null && position < index) {
            current = current.next;
            position++;
        }
        if (current != null) {
            current.next = current.next.next;
            size--;
        }
    }

    public T getData(int index) {
        if (index < 1 || index > size) {
            throw new IndexOutOfBoundsException("index should between 1 to " + size);
        }
        T data = null;
        int i = 1;
        Node<T> current = head.next;
        while (current != null) {
            if (i < index) {
                current = current.next;
                i++;
            }
            if (i == index) {
                data = current.data;
                break;
            }
        }
        return data;
    }

    public int getSize() {
        return size;
    }

    public NodeList<T> merge(NodeList<T> lb) {
        NodeList<T> la = this;
        NodeList<T> lc = new NodeList<>();
        Node<T> pa = la.head.next;
        Node<T> pb = lb.head.next;
        Node<T> pc = lc.head;

        while (pa.next != null && pb.next != null) {
            if (pa.data.equals(pb.data)) {
                pc.next = pa;
                pc = pa;
                pa = pa.next;
                pb = pb.next;
            } else if (pa.data.compareTo(pb.data) < 0) {
                pc.next = pa;
                pc = pa;
                pa = pa.next;
            } else {
                pc.next = pb;
                pc = pb;
                pb = pb.next;
            }
        }

        if (pa.next != null) {
            pc.next = pa;
        }

        if (pb.next != null) {
            pc.next = pb;
        }

        Node<T> current = lc.head;
        while (current.next != null) {
            lc.size++;
            current = current.next;
        }
        return lc;
    }
}