線性表的鏈?zhǔn)酱鎯?chǔ)和順序存儲(chǔ)的區(qū)別在于：順序存儲(chǔ)能夠指定索引隨機(jī)的讀取該位置的元素，但在隨機(jī)插入方面不擅長谷市，在表中插入新元素時(shí)需要移動(dòng)大量的已有元素烛占；而鏈?zhǔn)酱鎯?chǔ)則恰好相反，在插入元素方面作谚，他只要通過調(diào)整對(duì)應(yīng)位置的指針即可完成插入而不需要移動(dòng)元素，在隨機(jī)讀取方面卻不擅長庵芭，需要通過表頭指針依次讀取才能找到指定位置的元素妹懒；

單向鏈表的節(jié)點(diǎn)基本結(jié)構(gòu)為一個(gè)存儲(chǔ)數(shù)據(jù)的屬性和一個(gè)指向其后繼的指針，如下圖双吆；

鏈表節(jié)點(diǎn).png

因此創(chuàng)建如下鏈表節(jié)點(diǎn)類眨唬；

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

而對(duì)于鏈表本身是將節(jié)點(diǎn)通過指針連接起來，其自身有size屬性表示鏈表中當(dāng)前元素個(gè)數(shù) 和固定的head節(jié)點(diǎn)（head節(jié)點(diǎn)數(shù)據(jù)域?yàn)榭眨┢浜罄^指針指向鏈表第一個(gè)元素好乐；單鏈表最后一個(gè)元素后繼指向null匾竿，而循環(huán)鏈表最后一個(gè)元素的tail指向head；

單鏈表.png

單項(xiàng)循環(huán)鏈表.png

java實(shí)現(xiàn)如下蔚万；

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;
    }
}