Skip to main content

LinkedList addLast & getAt

本篇要來介紹 LinkedList 的 addLast() & getAt()

  1. addLast() 在 LinkedList 的後面加上 element
  2. getAt() 取得在 LinkedList 中的第幾個 (index) 元素並回傳該元素。

addLast() 方法​

addLast() 在 LinkedList 的後面加上 element

JavaScript addLast()作法​

這次我們來點不同的做法，不要再 while loop 找最後一個那招了。

既然我們都實作過 getLast()，那 addLast() 就簡單多了。

我們只要找到最後一個，然後往後加入就可以了~

addLast(data){
  const last = this.getLast()

  // check node exists
  if(last){
    last.next = new Node(data);
  } else {
    this.head = new Node(data);
  }
}

Java addLast() 官方做法​

Source from openjdk-1.8

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++;
    }

getAt()方法​

getAt() 取得在 LinkedList 中的第幾個 (index) 元素並回傳該元素。

JavaScript getAt() 實作​

解法: 從 head node 開始每一次加一個，宣告一個變數 counter 每加一次+1， 用來數加幾次了，就可以知道是第幾個 node

注意: chain 的長度需要留意。

getAt(index){
  let counter = 0;
  let node = this.head;
  while(node){
    if(counter === index){
      return node
    }

    counter++
    node = node.next
  }

  return null
}

Java getAt() 官方做法​

Source from openjdk-1.8

public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
}

private void checkElementIndex(int index) {
      if (!isElementIndex(index))
          throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
  }

本文同時發布於鐵人賽