概括

• 一种物理存储上非连续、非顺序的存储结构
• 由一系列节点组成，可以再运行时动态生成
• 每个节点包括两个部分：数据域；指针域

特点

• 数据存储不要求连续空间，不限制容量
• 数据的逻辑顺序通过指针链接次序实现
• 从链表头部依次访问后面的节点
• 在链表表头插入数据的时间复杂度是O(1)

优缺点

1. 插入删除数据速度快

2. 查询数据效率低

   实现

   链表实现

   public class LinkedDemo {
    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.insert(3, 0);
        myLinkedList.insert(7, 1);
        myLinkedList.insert(9, 2);
        myLinkedList.insert(5, 3);
        myLinkedList.insert(6, 1);
        myLinkedList.remove(0);
        myLinkedList.print();
    }
    public static class MyLinkedList {
        public Node head;
        public Node last;
        public int size;
        public void insert(int data, int index) {
            if (index < 0 || index > size) {
                throw new IndexOutOfBoundsException("超出链表节点范围");
            }
            Node n = new Node(data);
            if (size == 0) {
                // 插入第一个值
                head = n;
                last = n;
            } else if (index == 0) {
                // 开头插入
                n.next = head;
                head = n;
            } else if (index == size) {
                // 结尾插入
                last.next = n;
                last = n;
            } else {
                // 中间插入
                Node node = get(index - 1);
                n.next = node.next;
                node.next = n;
            }
            size++;
        }
        public Node remove(int index) {
            if (index < 0 || index >= size) {
                throw new IndexOutOfBoundsException("超出链表节点范围");
            }
            Node remove;
            if (index == 0) {
                remove = head;
                head = head.next;
            } else if (index == size - 1) {
                last = get(size - 1);
                remove = last.next;
                last.next = null;
            } else {
                Node node = get(index - 1);
                Node next = node.next;
                node.next = next.next;
                remove = next;
            }
            size--;
            return remove;
        }
        public Node get(int index) {
            if (index < 0 || index >= size) {
                throw new IndexOutOfBoundsException("超出链表节点范围");
            }
            Node n = head;
            for (int i = 0; i < index; i++) {
                n = n.next;
            }
            return n;
        }
        public void print() {
            Node node = head;
            while (node != null) {
                System.out.println(node.id);
                node = node.next;
            }
        }
    }
    /**
     * 链表节点
     */
    public static class Node {
        public Node(int id) {
            this.id = id;
        }
        public int id;
        public Node next;
    }
   }