写在前面
在日常开发中，一般在对于 List 的场景，基本上都是通过 ArrayList 去封装数据的，而对于链表 LinkedList 相对来说用的比较少。对我而言，好像 ArrayList 熟练度高一些，所以基本上也很少用 LinkedList，也就是在面试的时候去背过八股文。
链表：数据分散的存储在物理空间中，通过一根线保存着它们之间的逻辑关系，这种存储结构称为链式存储结构，简称链表。
链表的前驱和后继
数据结构中，一组数据中的每个个体被称为“数据元素”（简称“元素”）。另外，对于具有“一对一”逻辑关系的数据，我们一直在用“某一元素的左侧（前边）或右侧（后边）”这样不专业的词，其实线性表中有更准确的术语：
单链表
概念：单链表，用于存储逻辑关系为 "一对一" 的数据。与顺序表不同，链表不限制数据的物理存储状态，换句话说，使用链表存储的数据元素，其物理存储位置是随机的。HashMap 在 1.7 就是通过单链表来解决 hash 冲突的。
节点
在上图中无法提现出元素之间的逻辑关系，对此，链表的解决方案是，每个数据元素在存储时都配备一个指针，用于指向自己的直接后继元素。表示一个节点如下：
//节点信息class Node { E data; Node next;
public Node(E element, Node next) { this.data = element; this.next = next; }
public Node(E data) { this.data = data; }}
复制代码
因此，在链表中，每个数据的存储有以下 2 部分组成
数据本身，其所在的区域叫做数据域
指向后继元素的指针，叫指针域
上图所示的结构在链表中称为节点。也就是说，链表实际存储的是一个一个的节点，真正的数据元素包含在这些节点中
单链表---增
/** * 头部添加节点 * * @param e */ public void add(E e) { //头结点 Node cur = new Node(e, list); list = cur; size++; }
/** * 指定位置添加节点 * * @param index * @param e 0 1 2 3 4 */ public void add(int index, E e) { //越界检查 checkElementIndex(index); Node preNode = list; for (int i = 0; i < index - 1; i++) { //找到插入位置的前一个节点 preNode = preNode.next; } Node node = new Node(e); node.next = preNode.next; preNode.next = node; size++; }
复制代码
单链表---删
/** * 删除头部节点 */public void remove() { if (list != null) { Node node = list; list = node.next; //GC node.next = null; size--; }}
/** * 删除指定位置节点 * 1 2 3 4 5 * 0 1 2 3 4 * * @param index */public void remove(int index) { checkElementIndex(index); Node preNode = list; for (int i = 0; i < index - 1; i++) { //找到指定位置元素的前一个节点 preNode = preNode.next; } //指定位置的节点 Node next = preNode.next; preNode.next = next.next; //GC next = null; size--;}
/** * 删除最后一个节点 */public void removeLast() { if (list != null) { //当前节点 Node cur = list; //最后一个节点的前一个节点 Node preNode = list; while (cur.next != null) { preNode = cur; cur = cur.next; } preNode = null;//此时cur已经为null size--; }}
复制代码
单链表---改
/** * 修改指定索引的元素 * * @param index * @param e */public void set(int index, E e) { checkElementIndex(index); Node cur = list; for (int i = 0; i < index; i++) { cur = cur.next; } cur.data = e;}
复制代码
单链表---查
/** * 获取头部节点 */ public E get() { if (list != null) { return list.data; } else { return null; } }
/** * 获取指定位置的元素 * * @param index * @return */ public E get(int index) { checkElementIndex(index); Node cur = list; for (int i = 0; i < index; i++) { cur = cur.next; } return cur.data; }
复制代码
完整代码
/** * 单链表 * */public class SingleLinkedList<E> {
int size = 0;
/** * 指向第一个节点的指针 */ Node list;
/** * 头部添加节点 * * @param e */ public void add(E e) { //头结点 Node cur = new Node(e, list); list = cur; size++; }
/** * 指定位置添加节点 * * @param index * @param e 0 1 2 3 4 */ public void add(int index, E e) { checkElementIndex(index); Node preNode = list; for (int i = 0; i < index - 1; i++) { //找到插入位置的前一个节点 preNode = preNode.next; } Node node = new Node(e); node.next = preNode.next; preNode.next = node; size++; }
/** * 删除头部节点 */ public void remove() { if (list != null) { Node node = list; list = node.next; //GC node.next = null; size--; } }
/** * 删除指定位置节点 * 1 2 3 4 5 * 0 1 2 3 4 * * @param index */ public void remove(int index) { checkElementIndex(index); Node preNode = list; for (int i = 0; i < index - 1; i++) { //找到指定位置元素的前一个节点 preNode = preNode.next; } //指定位置的节点 Node next = preNode.next; preNode.next = next.next; //GC next = null; size--; }
/** * 删除最后一个节点 */ public void removeLast() { if (list != null) { //当前节点 Node cur = list; //最后一个节点的前一个节点 Node preNode = list; while (cur.next != null) { preNode = cur; cur = cur.next; } preNode = null;//此时cur已经为null size--; } }
/** * 修改指定索引的元素 * * @param index * @param e */ public void set(int index, E e) { checkElementIndex(index); Node cur = list; for (int i = 0; i < index; i++) { cur = cur.next; } cur.data = e; }
/** * 获取头部节点 */ public E get() { if (list != null) { return list.data; } else { return null; } }
/** * 获取指定位置的元素 * * @param index * @return */ public E get(int index) { checkElementIndex(index); Node cur = list; for (int i = 0; i < index; i++) { cur = cur.next; } return cur.data; }
class Node { E data; Node next;
public Node(E element, Node next) { this.data = element; this.next = next; }
public Node(E data) { this.data = data; }
public Node() { }
@Override public String toString() { return "Node{" + "data=" + data + ", next=" + next + '}'; } }
/** * 判断参数是否为现有元素的索引 即边界 * * @param index */ private void checkElementIndex(int index) { if (!(index >= 0 && index < size)) throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); }
@Override public String toString() { Node node = list; for (int i = 0; i < size; i++) { System.out.print(node.data + " "); node = node.next; } return super.toString(); }
public static void main(String[] args) { SingleLinkedList<Integer> list = new SingleLinkedList<>(); list.add(5); list.add(4); list.add(3); list.add(2); list.add(1); list.toString(); System.out.println(); list.add(2, 5); list.toString(); list.removeLast(); System.out.println(); list.toString(); list.set(1, 1); System.out.println(); list.toString(); System.out.println(); System.out.println(list.get()); }}
复制代码
双链表 LinkedList 源码分析
双链表，指各节点之间的逻辑关系是双向的。
节点
因此，在双向链表中各节点包含以下 3 部分信息
指针域：用于指向当前节点的直接前驱节点；
数据域：用于存储数据元素。
指针域：用于指向当前节点的直接后继节点；
private static class Node<E> { E item; Node<E> next; Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; }}
复制代码
如果理解了单链表，双项链表其实也没有太多的差别，主要在于限制条件。不仅仅是双向链表，还有很多分类，比如静态链表，动态链表，循环链表等等。这里可以就增删给出对应的过程，源码可以自己去研究研究。
类的继承关系
双链表---增
public void add(int index, E element) { checkPositionIndex(index); //如果索引和size相等直接尾部插入 if (index == size) linkLast(element); else linkBefore(element, node(index));}
/** * first 指向第一个节点的指针 * @param e 要插入的元素 * @param succ index位置的节点 * a1 a3 * 在a3索引出插入新的元素 a2 * a1 a2 a3 */void linkBefore(E e, Node<E> succ) { // succ：原a3的前置节点a1 final Node<E> pred = succ.prev; //pred(a1) e(a2) succ(a3)形成新的节点 //即把e(a2)prev指向pred(a1)节点，把e(a2)next指向succ(a3)节点 final Node<E> newNode = new Node<>(pred, e, succ); //把succ(a3)的prev指向新的节点newNode succ.prev = newNode; //pred为空代表newNode为首节点 if (pred == null) first = newNode; else //a1的next节点由a3变为a2 pred.next = newNode; size++; modCount++;}
复制代码
双链表---删
public E remove(int index) { checkElementIndex(index); return unlink(node(index)); }
/** * Unlinks non-null node x. */ E unlink(Node<E> x) { // assert x != null; //获取该节点的值 final E element = x.item; //获取该节点的next节点 final Node<E> next = x.next; //获取该节点的prev节点 final Node<E> prev = x.prev; //把该节点的前节点的next指向该节点的next节点，并清除该节点的prev指向 if (prev == null) { first = next; } else { prev.next = next; x.prev = null; } //把该节点的next节点的prev指向该节点的prev节点，并清除该节点的next指向 if (next == null) { last = prev; } else { next.prev = prev; x.next = null; } x.item = null;//gc清除 size--; modCount++; return element; }
复制代码
总结
前面讲过ArrayList源码分析及扩容机制,如果你看了应该知道不管是用 ArrayList 还是 LinkedList 主要是看场景，LinkedList 增删快，因为只用调整指向即可，对于 ArrayList 而言却要移动整个数组，但是如果说是在尾部插入的话，使用两者都可以。而查找和修改却要 ArrayList 只需要知道下标即可，而对于 LinkedList 却要通过循环查找。
对于 LinkendList，其中还有很多方法，例如 addFirst，addLast，remove 等，如果你学会了单链表，其实双链表也是一样的，主要在于思维。
参考
拓展延伸
文章首发：为什么在开发中老是用ArrayList而很少用LinkedList
公众号：Javatv
评论