定义
链表通过指针将一组零散的内存块串联在一起。其中，我们把内存块称为链表的“结点”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址。
特点
- 不需要连续的内存空间。
- 有指针引用
- 三种最常见的链表结构：单链表、双向链表和循环链表
图形
链表.jpeg
从单链表图中，可以发现，有两个结点是比较特殊的，它们分别是第一个结点和最后一个结点。我们一般把第一个结点叫作头结点，把最后一个结点叫作尾结点。
其中，头结点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表。而尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址NULL，表示这是链表上最后一个结点。
- 双向链表：双向链表有两个指针域，一个指向性上一个节点，一个指向下一个节点，头节点的上一个节点为NULL
- 循环链表：循环链表是一种特殊的单链表。实际上，循环链表也很简单。它跟单链表唯一的区别就在尾结点。环链表的尾结点指针是指向链表的头结点。
数组和链表的区别
- 数组结构使用的是连续的内存空间，可以借助cpu缓存的机制，预读数组中的数据
- 链表在内存中并不是连续存储，所以对CPU缓存不友好，没办法有效预读。
- 数组的缺点是大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配给它，导致“内存不足（out of memory）”。如果声明的数组过小，则可能出现不够用的情况。
- 动态扩容：数组需再申请一个更大的内存空间，把原数组拷贝进去，非常费时。链表本身没有大小的限制，天然地支持动态扩容。
- 时间复杂度：数组的访问为O(1),修改为O(n);链表的访问为O(n),修改为O(1)
这里也不是绝对的，如果数组和链表都是在尾部或者头部进行操作，那数组和链表的访问和修改都是O(1)，如栈和队列
手写一个LinkedList
public class MyLinkedList<E> implements MyList<E> { private int size; private Node<E> first; private Node<E> last; @Override public int size() { return size; } @Override public void add(E e) { Node<E> newNode = new Node<>(null, e, null); if (first == null) { first = newNode; last = newNode; size++; return; } last.next = newNode; newNode.pre = last; last = newNode; size++; } @Override public void add(E e, int index) { if (index < 0 || index > size) throw new IndexOutOfBoundsException(); Node<E> newNode = new Node<>(null, e, null); if (index == size) {//加在末尾 add(e); return; } Node<E> cur = node(index); newNode.next = cur; if (cur.pre == null) {//头 cur.pre = newNode; first = newNode; } else { newNode.pre = cur.pre; cur.pre.next = newNode; cur.pre = newNode; } size++; } @Override public void remove(int index) { if (index < 0 || index > size) throw new IndexOutOfBoundsException(); if (index == size) { last.pre.next = null; last = last.pre; size--; return; } Node<E> cur = node(index); if (cur.pre == null) { cur.next.pre = null; first = cur.next; } else { cur.pre.next = cur.next; cur.next.pre = cur.pre; } size--; } private Node<E> node(int index){ Node<E> cur = null; if (index < (size >> 1)) {//插入位置小于链表的一半 //从前遍历 cur = first; for (int i = 0; i < index; i++) { cur = cur.next; }//index=3 插入在第四个位置 cur为第4个链表元素 } else { //从后遍历 cur = last; for (int i = size - 1; i > index; i--) { cur = cur.pre; }//index=3 插入在第四个位置 cur为第4个链表元素 size =5 last.index=4 } return cur; } @Override public void remove(E e) { remove(indexOf(e)); } @SuppressWarnings("unchecked") @Override public E get(int index) { return node(index).element; } @Override public Iterator<E> iterator() { return null; } @Override public int indexOf(E e) { Node<E> cur = first; for (int i = 0 ;i<size;i++){ if(e.equals(cur.element)){ return i; } cur = cur.next; } return -1; } private class Node<E> { private E element; private Node<E> pre; private Node<E> next; public Node(Node<E> pre, E element, Node<E> next) { this.pre = pre; this.element = element; this.next = next; } }
