Java中的链表
学习了链表的基础知识之后，我们来思考一个问题：Java 中的链表 LinkedList 是属于哪种类型的链表呢？单向链表还是双向链表？
要回答这个问题，首先我们要来看 JDK 中的源码，如下所示：
package java.util; import java.util.function.Consumer; public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable { // 链表大小 transient int size = 0; // 链表头部 transient Node<E> first; // 链表尾部 transient Node<E> last; public LinkedList() { } public LinkedList(Collection<? extends E> c) { this(); addAll(c); } // 获取头部元素 public E getFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return f.item; } // 获取尾部元素 public E getLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return l.item; } // 删除头部元素 public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); } // 删除尾部元素 public E removeLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return unlinkLast(l); } // 添加头部元素 public void addFirst(E e) { linkFirst(e); } // 添加头部元素的具体执行方法 private void linkFirst(E e) { final Node<E> f = first; final Node<E> newNode = new Node<>(null, e, f); first = newNode; if (f == null) last = newNode; else f.prev = newNode; size++; modCount++; } // 添加尾部元素 public void addLast(E e) { linkLast(e); } // 添加尾部元素的具体方法 void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; } // 查询链表个数 public int size() { return size; } // 清空链表 public void clear() { for (Node<E> x = first; x != null; ) { Node<E> next = x.next; x.item = null; x.next = null; x.prev = null; x = next; } first = last = null; size = 0; modCount++; } // 根据下标获取元素 public E get(int index) { checkElementIndex(index); return node(index).item; } 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; } } // 忽略其他方法...... }
从上述节点 Node 的定义可以看出：LinkedList 其实是一个双向链表，因为它定义了两个指针 next 和 prev 分别用来指向自己的下一个和上一个节点。
链表常用方法
LinkedList 的设计还是很巧妙的，了解了它的实现代码之后，下面我们来看看它是如何使用的？或者说它的常用方法有哪些。
1.增加
接下来我们来演示一下增加方法的使用：
public class LinkedListTest { public static void main(String[] a) { LinkedList list = new LinkedList(); list.add("Java"); list.add("中文"); list.add("社群"); list.addFirst("头部添加"); // 添加元素到头部 list.addLast("尾部添加"); // 添加元素到最后 System.out.println(list); } }
以上代码的执行结果为：
[头部添加, Java, 中文, 社群, 尾部添加]
出来以上的 3 个增加方法之外，LinkedList 还包含了其他的添加方法，如下所示：
- add(int index, E element)：向指定位置插入元素；
- offer(E e)：向链表末尾添加元素，返回是否成功；
- offerFirst(E e)：头部插入元素，返回是否成功；
- offerLast(E e)：尾部插入元素，返回是否成功。
add 和 offer 的区别
它们的区别主要体现在以下两点：
- offer 方法属于 Deque接口，add 方法属于 Collection的接口；
- 当队列添加失败时，如果使用 add 方法会报错，而 offer 方法会返回 false。
2.删除
删除功能的演示代码如下：
import java.util.LinkedList; public class LinkedListTest { public static void main(String[] a) { LinkedList list = new LinkedList(); list.offer("头部"); list.offer("中间"); list.offer("尾部"); list.removeFirst(); // 删除头部元素 list.removeLast(); // 删除尾部元素 System.out.println(list); } }
以上代码的执行结果为：
[中间]
除了以上删除方法之外，更多的删除方法如下所示：
- clear()：清空链表；
- removeFirst()：删除并返回第一个元素；
- removeLast()：删除并返回最后一个元素；
- remove(Object o)：删除某一元素，返回是否成功；
- remove(int index)：删除指定位置的元素；
- poll()：删除并返回第一个元素；
- remove()：删除并返回第一个元素。
3.修改
修改方法的演示代码如下：
import java.util.LinkedList; public class LinkedListTest { public static void main(String[] a) { LinkedList list = new LinkedList(); list.offer("Java"); list.offer("MySQL"); list.offer("DB"); // 修改 list.set(2, "Oracle"); System.out.println(list); } }
以上代码的执行结果为：
[Java, MySQL, Oracle]
4.查询
查询方法的演示代码如下：
import java.util.LinkedList; public class LinkedListTest { public static void main(String[] a) { LinkedList list = new LinkedList(); list.offer("Java"); list.offer("MySQL"); list.offer("DB"); // --- getXXX() 获取 --- // 获取最后一个 System.out.println(list.getLast()); // 获取首个 System.out.println(list.getFirst()); // 根据下标获取 System.out.println(list.get(1)); // peekXXX() 获取 System.out.println("--- peek() ---"); // 获取最后一个 System.out.println(list.peekLast()); // 获取首个 System.out.println(list.peekFirst()); // 根据首个 System.out.println(list.peek()); } }
以上代码的执行结果为：
DB
Java
MySQL
--- peek() ---
DB
Java
Java
5.遍历
LinkedList 的遍历方法包含以下三种。
遍历方法一：
for (int size = linkedList.size(), i = 0; i < size; i++) { System.out.println(linkedList.get(i)); }
遍历方法二：
for (String str: linkedList) { System.out.println(str); }
遍历方法三：
Iterator iter = linkedList.iterator(); while (iter.hasNext()) { System.out.println(iter.next()); }
