Linked List 简单的链表

今天开始看链表

链表是一种递归型的数据结构，要么为null要么为node的结点的连结，这个 node含有一个泛型的元素和一个指向另一条链表的引用，实现链表并不难

public class Node<T> {
    public T t;
    public Node<T> next;

    public Node() {
        this.t = null;
        this.next = null;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(t);
        for(Node node = next;node!=null; node = node.next){
            res.append("->").append(node.t);
        }
        return res.toString();
    }
}

我们可以构造一个链表了

        Node first = new Node();
        Node second = new Node();
        Node last = new Node();
        first.t = "one";
        second.t = "two";
        last.t = "three";
        first.next = second;
        second.next = last;

此时打印first链表：one->two->three

此时可以在表头插入元素

本质就是定义一个oldFirst存原来的first，在new一个新的Node first，将first.next = oldFirst

 Node oldFirst = first;
 first = new Node();
 first.next = oldFirst;

打印结果为null->one->two->three
删除首元素，我们只要 first = first.next即可，原来的就会成为垃圾，会被JAVA自动回收

同理我们可以在链表尾部添加节点

Node oldLast = last;
last = new Node();
oldLast.next =last;

对于删除链表尾部，我们需要遍历整个链表，然后找到尾元素的前一个元素将其next = null即可