[TIL] 자료구조 - addLast 메소드

※ addLast 메소드

- addLast 메소드에선 연결 리스트의 마지막을 가리키는 임시 포인터를 사용한다. 연결 리스트의 요소를 확인하기 위해

무조건 head에서 시작해야 하는데, 연결 리스트의 마지막까지 도달하는데 next를 너무 많이 사용해야 한다.

 

그리고 연결 리스트의 마지막 노드는 유일하게 next 포인터가 null을 가리키기 떄문에, 다음과 같이 addLast 메소드를 작성할 수 있다.

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

 

경계조건 에서의 문제

- head가 비어있는 경우는 tmp가 null이 되고, tmp.next를 찾지 못하는 NullPointerException 에러가 발생한다. 이 문제를 해결하기 위해 리스트 맨 뒤에 추가하고자 하지만 리스트가 비어있을 경우 addFirst 메소드처럼 노드를 추가한다.

 

시간 복잡도 문제

- 연결 리스트의 마지막 노드를 찾을 때 리스트의 맨앞부터 시작해 마지막 요소까지 살펴보면 시간 복잡도는 O(n)이다.

하지만 tail 포인터를 사용하면 이 시간 복잡도를 O(1)로 만들 수 있는데 리스트의 마지막을 가리키는 tail 포인터를 head, currentSize와 같은 전역 변수로 설정하고 tail 포인터를 추가하면 된다.