addLastメソッド

addLast

addLastメソッドでは、接続リストの最後の一時ポインタを使用します.
nextが接続リストの最後に到達するために多すぎるため、headから接続リストの要素をチェックする必要があります.
例えば、このような方法です.head.next.next.next.next = node;
では、どのようにして一時的な飾りを使うのでしょうか.

headは通常、最初のノードaを指す.aはb、bはcを指す.そしてcはnullを指す.
では、最後のノードが見つかった場合、next変数はnullを指しますか?見つかればわかる.
だから一時ポインタはリストの一番前からtmpnextがnullでない場合は、後にもっと多くのノードがあることを示します.
tmpは、tmpとともに次のノードに移動し続ける.nextがnullの場合、新しいノードtmpが使用されます.nullではなくnextに新しいノードを指します.
次のaddLastメソッドを作成できます.

public void addLast(E obj){
	Node<E> tmp = head;
	while(tmp.next != null)
		tmp=tmp.next
	tmp.next=node;
}

tmpが範囲を超えた場合、tmpはゴミ収集の目標になります.

きょうかいじょうけん

ノードが作成されず、headがnullを指し、tmpもnullを指す場合、tmp.nextが見つからないため、実行中にエラーが発生しました.
つまり、リストの最後にノードを追加するが、リストが空の場合、
以前にパブリッシュしたaddFirstメソッドを使用してノードを追加します.

public void addLast(E obj){
	Node<E> node = new Node<E>(obj);
	if (head == null){ // head가 비어있는 경우
		head=node;
		currentsize++;
		return;
	}
	Node<E> tmp = head;
	while(tmp.next != null)
		tmp=tmp.next
	tmp.next=node;
	currentsize++;
}

時間の複雑さ

接続リストの最後のノードを検索する場合、リストの先頭から最後の要素までの時間的複雑度はO(n)O(n)O(n)O(n)O(n)O(n)である.
ただし、tailポインタを使用して、この時間の複雑さをO(1)O(1)O(1)に設定することができます.
リストの末尾を指すtailポインタをhead、currentSizeなどのグローバル変数に設定し、次のようにtailポインタを追加します.

public void addLast(E obj){
	Node<E> node = new Node<E>(obj);
	if (head == null){
		head=node;
		tail=node; // head 포인터뿐만 아니라 tail 포인터도 바꿔줘야 합니다.
		currentsize++;
		return;
	}
	tail.next=node;
	tail = node;
	currentsize++;
}