链表

在 Java 中通过代码定义一个链表

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

有的同学可能会问，这不是聊表中的一个节点吗？是的，ListNode 是链表中的一个节点，如果这个节点是链表中的第一个元素，那么这个节点也可以代表这个链表，因为这个链表中的所有的元素都可能从这个节点访问到。
链表有多种类型，ListNode 是一个单链（一个节点只有指向下一个节点的指针 next，最后一个节点的 next 为 null），还有双链（除了 next，还有指向前一个节点的指针 prev），还有循环链表（链表的最后一个元素的 next 指向链表的第一个元素，整个链表构成一个环）。
数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。
链表是通过指针域的指针链接在内存中各个节点。
所以链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。
链表操作的复杂度