JAVA/자료구조

노드와 크기

도전하는일반인 2021. 10. 2. 21:37

들어가기 전에

연결 리스트의 구성 요소인 노드를 정의하는 방법에 대해 살펴보도록 하겠습니다.

 

학습 목표

노드를 정의하고 노드의 개수를 효율적으로 세는 방법을 설명할 수 있습니다.

 

핵심 단어

  • 노드
  • 시간 복잡도

노드와 크기

 

 

 

 

위 코드는 연결 리스트의 내부 클래스에서 노드를 정의한 내용입니다. 노드는 next라는 포인터와 data를 가집니다.

 

data의 자료형은 E입니다. E는 정해지지 않은 자료형이고 이렇게 구현한 연결 리스트를 사용하면 그때 지정하겠다는 의미입니다. 그리고 next의 타입은 Node입니다. 다른 노드를 가리키는 포인터이기 때문입니다.

생성자까지 추가하여 코드를 적으면 노드 객체가 완성됩니다. 생성자에서는 객체를 data에 저장하고 next는 우선 null로 지정합니다. 이 노드 객체는 내부 클래스이기 때문에 연결 리스트가 아닌 다른 곳에서 접근할 수 없습니다. 외부에서 접근하기 위해 노드 객체를 만들 때와 같이 private 변수 head를 만듭니다.

 

 

노드의 개수를 세는 효율적인 방법

 

노드의 개수를 직접 세는 방법보다 int 타입인 변수 currentSize를 만들어 노드의 개수를 세는 방법이 더 효율적입니다.

 

노드의 개수를 직접 셀 경우, 요소가 n개면 n번 세야 합니다. 따라서, 하나씩 세는 것의 시간 복잡도는 θ(nn)입니다. 하지만 currentSize라는 변수를 만들어놓고 리스트에 요소를 추가할 때마다 currentSize의 값을 늘려 놓으면, 리스트의 크기를 바로 알 수 있습니다. 이럴 경우, 시간 복잡도는 정확히 1입니다.

 

 

생각해보기


1) next가 내부 클래스에 있지 않으면 어떤 문제가 발생할까요?

 

나의 생각 : 다음 노드를 찾을 수 없다. 다음 노드랑 연결을 할 수가 없다.

 

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