addLast 메소드

들어가기 전에

연결 리스트의 마지막에 node를 추가하는 addLast 메소드에 대해 살펴보도록 하겠습니다.

 

학습 목표

addLast 메소드를 이해하고 경계 조건을 만족하는지 확인할 수 있습니다.

 

핵심 단어

• addLast 메소드
• 연결 리스트
• 경계 조건
• 시간 복잡도

addLast 메소드

 

addLast 메소드에서는 연결 리스트의 마지막을 가리키는 임시 포인터를 사용합니다. 연결 리스트의 요소를 확인하려면 무조건 head에서 시작해야 하는데, 연결 리스트의 마지막까지 도달하는 데 next를 너무 많이 사용해야 하기 때문입니다.

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

문제 1. 경계 조건

head가 비어있는 경우에는 tmp가 null이 되고, tmp.next를 찾지 못하는 NullPointerException 에러가 발생합니다. 이 문제를 해결하기 위해 리스트 맨 뒤에 추가하려 하는데 리스트가 비어있다면, addFirst 메소드처럼 노드를 추가합니다. 이 내용을 추가한 코드는 아래와 같습니다.}

문제 2. 시간 복잡도

연결 리스트의 마지막 노드를 찾을 때 리스트의 맨 앞부터 시작해서 마지막 요소까지 살펴보면 시간 복잡도는  O(n)O(n) 입니다. 하지만 tail 포인터를 사용하면 이 시간 복잡도를  O(1)O(1) 로 만들 수 있습니다. 리스트의 마지막을 가리키는 tail 포인터를 head, currentSize와 같은 전역 변수로 설정하고, 아래와 같이 tail 포인터를 추가하면 됩니다.; }

---

 

생각해보기

1) 왜 currentSize 변수 대신 tail 포인터를 사용하나요?

 

나의 생각 : currentSize를 사용하면 시간복잡도가 O(n)이 되지만 tail 포인터를 사용하면 한 번에 찾을 수 있어서 시간복잡도가 1로 줄기 때문이다.

 

출처 : https://www.boostcourse.org/cs204/lecture/625942?isDesc=false 네이버커넥트재단