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

本文同時發布於鐵人賽