23张图!万字详解「链表」,从小白到大佬! (2)

要回答这个问题,首先我们要来看 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.修改

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wspjgw.html