1.链表的原理

1.1链表的示意图

元素：真实存于线性表中的内容，是我们一般核心关注的内容。
结点（node）；为了组织链表而引入的一个结构，除了保存我们的元素之外，还会保存指向下一个结点的引用。

1.2链表的表现形式

public class Node {
    public int val;
    public Node next;
    
    public Node(int val){
        this.val=val;
    }
}

链表：最终的线性表，表示逻辑上的[1 3 2 6]
目前，我们通过链表的头节点，来代替一整条链表。

//head是一条链表的头结点；通过head我们可以找到找到所有的结点；所以用头节点来代替链表
Node head=...;
//某链表的头节点是null；表示头节点不存在，进一步可以表示一条没有头节点的链表，也就是一条空链表。
Node head=null;

1.3结点的分类

当前结点（current/cur)：表示链表中某个结点
前驱节点(previous/prev):表示链表中的某个结点的前一个结点；头节点没有前驱节点。
后继节点（next）：表示链表中的某个结点的后一个结点；尾结点没有后继节点。

2.链表的代码表示

2.1链表的结点定义

public class Node {
    public int val;
    public Node next;

    public Node(int val){
        this.val=val;
        this.next=null;
    }
    
    @Override
    public String toString(){
        return "Node{"+val+"}";
    }
}

2.2链表的手工创建

2.2.1创建一个[1 3 5 6]的链表

public class myListNode {
    public static Node createList(){
        Node a=new Node(1);
        Node b=new Node(3);
        Node c=new Node(5);
        Node d=new Node(6);
        
        a.next=b;
        b.next=c;
        c.next=d;
        d.next=null;
        return a;
    }
}

2.2.2创建一个空链表

Node head=null;

2.3遍历链表

2.3.1链表不知道长度的情况，打印链表的元素

public static void main(String[] args) {
        Node head=createList();
        Node cur=head;
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
    }

2.3.2通过遍历，打印链表的最后一个元素

public static void main(String[] args) {
        Node head=createList();
        Node cur=head;
        while(cur.next!=null){
            cur=cur.next;
        }
        System.out.println(cur.val);
    }

2.3.3打印链表的倒数第二个元素

public static void main(String[] args) {
        Node head=createList();
        Node cur=head;
        while(cur.next.next!=null){
            cur=cur.next;
        }
        System.out.println(cur.val);
    }

2.3.4打印链表的第n个结点（n>链表的长度)

public static void main(String[] args) {
        Node head=createList();
        Scanner scanner=new Scanner(System.in);
        System.out.println("请输入一个小于链表长度的整数");
        int n=scanner.nextInt();
        Node cur=head;
        int i=0;
        for(;i<n;i++){
            cur=cur.next;
        }
        System.out.println(cur.val);
    }

2.3.5计算出链表中元素的个数

public static void main(String[] args) {
        Node head=createList();
        Scanner scanner=new Scanner(System.in);
        System.out.println("请输入一个小于链表长度的整数");
        int n=scanner.nextInt();
        Node cur=head;
        int i=0;
        for(;i<n;i++){
            cur=cur.next;
        }
        System.out.println(cur.val);
    }

2.3.6找到链表中是否包含某个元素

public static boolean isElement(Node head,int x){
        if(head==null){
            return false;
        }
        for(Node cur=head;cur!=null;cur=cur.next){
            if(cur.val==x){
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Node head=createList();
        System.out.println(isElement(head,3));
    }