单链表

数组的局限：

（1）若改变数组的大小，就需要创建一个新数组并从原数组中拷贝所有数据至新数组。

（2）数组元素在内存中依次连续存储，插入新数据项要移动数组中其他数据。

 

链式结构：是存储数据和指向其他节点的链指针的节点的集合。

 

单链表：如果一个节点仅仅包含指向其后继的链指针，则该表称为“单链表”。

 

代码参考：

public class IntNode {
    int info;
    IntNode next;
    public IntNode(int info) {
        this(info, null);
    }
    public IntNode(int info, IntNode intNode) {
        this.info = info;
        this.next = intNode;
    }

    public static void main(String[] args) {
        IntNode p = new IntNode(10);
        p.next = new IntNode(8);
        p.next.next = new IntNode(50);
    }
}

public class IntSLList {
    private IntNode head, tail;
    public IntSLList() {
        head = tail = null;
    }
    public boolean isEmpty() {
        return head == null;
    }
    public void addToHead(int el) {
        head = new IntNode(el, head);
        if (tail == null)
            tail = head;
    }
    public void addToTail(int el) {
        if (!isEmpty()) {
            tail.next = new IntNode(el);
            tail = tail.next;
        } else
            head = tail = new IntNode(el);
    }
    public int deleteFromHead() {
        int el = head.info;
        if (head == tail)
            head = tail = null;
        else
            head = head.next;
        return el;
    }
    public int delteFromTail() {
        int el = tail.info;
        if (head == tail)
            head = tail = null;
        else {
            IntNode temp;
            for (temp = head; temp.next != tail; temp = temp.next);
            tail = temp;
            tail.next = null;
        }
        return el;
    }
    public void printAll() {
        for (IntNode temp = head; temp != null; temp = temp.next)
            System.out.println(temp.info);
    }
    public boolean isInList(int el) {
        IntNode temp;
        for (temp = head; temp!= null && temp.info != el; temp = temp.next);
        return temp != null;
    }
    public void delete(int el) {
        if (!isEmpty()) {
            if (head == tail && el == head.info)
                head = tail = null;
            else if (el == head.info)
                head = head.next;
            else {
                IntNode pred, temp;
                for (pred = head, temp = head.next;temp != null && temp.info != el; pred = temp.next, temp = temp.next);
                if (temp != null) {
                    pred.next = temp.next;
                    if (temp == tail)
                        tail = pred;
                }
            }
        }
    }
}