Skip to main content

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;

}

本文同時發布於鐵人賽