链表和数组一样也是线性表的一种。和数组不同，它不需要再内存中开辟连续的空间。
链表通过指针将一组零散的内存块连接在一起。我们把内存块称为链表的“结点”（是节点还是结点，结点连接起来打个结所以叫“结点”？开个玩笑），也就是说这些结点可以在内存的任意地方，只要有其他的结点的指针指向这个位置就可以。
链表又分为单向链表，双向链表，循环链表
单向链表
循环链表：最后一个节点指向第一个结点
双向链表：比单向链表多了一个前驱指针，指向前面一个结点
从上面的结构和内存中的储存结构来看，就可以发现链表相比数组来说，随机查询效率是O(n),只有从头结点开始查找；但是它的插入修改效率比数组高，找到位置之后只需要修改下指针指向，而不需要进行后续元素的迁移。理论上来说是无限容量，不像数组满了还需要扩容，扩容还要重新申请内存，然后迁移数据，链表只需要在内存找个一小块空地，放好数据，让前面那个指向这里就是了。
我们也可以看到双向链表比单向链表更灵活，因为通过一个结点可以找到前后两个结点。但是多了个指针所占空间肯定比单向链表大。
Java中LinkedList就是一个双向链表。
简单实现一个单向链表
package com.nijunyang.algorithm.link; /** * Description: * Created by nijunyang on 2020/3/31 22:09 */ public class MyLinkedList<E> { private Node<E> head; private int size = 0; /** * 头部插入O(1) * @param data */ public void insertHead(E data){ Node newNode = new Node(data); newNode.next = head; head = newNode; size++; } public void insert(E data,int position){ if(position == 0) { insertHead(data); }else{ Node cur = head; for(int i = 1; i < position ; i++){ cur = cur.next; //一直往后遍历 } Node newNode = new Node(data); // newNode.next = cur.next; //新加的点指向后面 保证不断链 cur.next = newNode; //把当前的点指向新加的点 size++; } } public void deleteHead(){ head = head.next; size--; } public void delete(int position){ if(position == 0) { deleteHead(); }else{ Node cur = head; for(int i = 1; i < position ; i ++){ cur = cur.next; //找到删除位置的前一个结点 } cur.next = cur.next.next; //cur.next 表示的是删除的点，后一个next就是我们要指向的 size--; } } public int size( ){ return size; } public String toString( ){ if (size == 0) { return "[]"; } StringBuilder sb = new StringBuilder(); sb.append('['); Node<E> node = head; sb.append(node.value); int counter = 0; for (;;) { if (++counter == size) { break; } sb.append(","); node = node.next; sb.append(node.value); } sb.append(']'); return sb.toString(); } public static void main(String[] args) { MyLinkedList myList = new MyLinkedList(); myList.insertHead(5); System.out.println(myList); myList.insertHead(7); System.out.println(myList); myList.insertHead(10); System.out.println(myList); myList.delete(0); System.out.println(myList); myList.deleteHead(); System.out.println(myList); myList.insert(11, 1); System.out.println(myList); } private static class Node<E>{ E value; //值 Node<E> next; //下一个的指针 public Node() { } public Node(E value) { this.value = value; } } }