LinkedList removeFirst() & removeLast()#

本篇要來實作 removeFirst() 與 removeLast()

  1. removeFirst() : 移除第一個 node
  2. removeLast() : 移除最後一個 node

removeFirst() 方法#

Java 官方作法#

Java 的 LinkedList 內建這兩種做法,

我們來看看 java8 官方的開放原始碼怎麼實作:

Source from openjdk-1.8

public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}

說明: 若沒有第一個 node (空的 List)則拋出例外 NoSuchElementException(), 若有就刪除並回傳第一個元素。

我們來看看 unlinkFirst() 是如何做到的:

private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}

解析: 最主要是 first = next; 這行,把下一個 node 變第一個 node,就是移除第一個 node 了。

JavaScript 實作#

看完了 Java 開源實作,我們來寫 JS 的作法吧!原理相同

class Node {
constructor(data, next = null) {
this.data = data;
this.next = next;
}
}
class LinkedList {
constructor() {
this.head = null;
}
removeFirst() {
if (!this.head) {
return;
}
this.head = this.head.next;
}
}

removeLast() 方法#

Java 也有內建做法,我們這邊就不再貼官方開源的程式碼。直接來實作 JavaScript 的 removeLast()。

JavaScript 實作 removeLast()#

提示: 先看有沒有第一個跟第二個 node,然後一次檢查兩個 node, 一直往後檢查...

直到沒有,就移除兩個之中的後面那個。

removeLast(){
if(!this.head){
return;
}
// if second node is empty, remove the first one
if(!this.head.next){
this.head = null
return;
}
// 一次檢查兩個 node,一直往下檢查
let pre = this.head;
let node = this.head.next;
while(node.next){
pre = node;
node = node.next;
}
// 最後兩個node, 移除後面那個
pre.next = null;
}

本文同時發布於鐵人賽