[TIL] 자료구조 - 노드와 크기

※ 노드와 크기

public class LinkedList <E> implements Listl<E>{
	//노드 정의
    class Node<E>{
    E data;
    Node<E> next;
    public Node(E obj){
    	data = obj;
        next = null;
   	}
	}
    private Node<E> head;
    //노드 개수를 세는 변수
    private int currentSize;
    //기본 연결리스트
    public LinkedList(){
        head = null;
        currentsize = null;
	}
}

- 다음 예시는 연결 리스트의 내부 클래스에서 노드를 정의한 예시이다. 노드는 next 포인터와 data를 가진다.

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

 

생성자까지 추가해 코드를 작성하면 노드 객체가 완성된다. 생성자에서는 객체를 data에 저장하고 next는 우선 null로 지정한다. 해당 노드 객체는 내부 클래스로 연결 리스트가 아닌 다른 곳에서 접근할 수 없으며 외부에서 접근하고자 노드 객체를 만들때와 동일하게 private 변수 head를 만든다.

 

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

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

노드를 직접 센다면 노드개수가 n개일때 n번 세야하고 이 복잡도는 O(n)이 된다. 하지만 currentSize 라는 변수를 만들고 리스트 요소가 추가될 때마다 currentSize 값을 늘려두면 리스트의 크기를 바로 알 수 있다. 이럴 경우는 시간 복잡도가 정확히 1 이다.