자료구조(java) 3_2 노드와 크기

노드와 크기

연결 리스트의 내부 클래스

public class LinkedList <E> implements ListI<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;
	}
}

위 코드는 연결 리스트의 내부 클래스에서 노드를 정의한 내용이다. 하나씩 뜯어보자.

노드 객체

내부 클래스(class Node<E>)는 두가지를 가지고 있다.

전 강의에서 그렸 듯, 노드의 next 포인터와 data 이 두가지.

내부 클래스이기 때문에 다른 곳에서 접근이 불가능하다.

E data;

data의 타입은 E이고, 제너릭 타입으로써 어떤 뭐든 타입이건 뭔상관.

이렇게 구현한 연결 리스트를 사용하면 그때 타입을 지정하겠다는 의미.

Node<E> next;

이 next는 다른 노드를 가리키는 포인터이다.

👉 next는 마찬가지로 타입이 Node 이다.

public Node(E obj){
			data=obj;	//받은 객체를 data에 저장
			next=null;	//우선 null로 지정
		}

우리는 노드를 만들 때 비어있는 노드를 만들지는 않는다. 노드는 항상 내용을 가지기 때문.

👉 생성자를 통해 항상 어떠한 객체를 받게 만든다.

타입은 지정되지 않았기 때문에 마찬가지로 E.

내부 클래스로 만들게 되면, 이 클래스에 접근할 수 있는 것들은 외부 클래스에 있는 객체들이나 메소드들 뿐이다. 이곳에서만 다룰 수 있도록 제한. (만약 외부에서 포인터들을 수정한다면 링크가 끊겨 데이터들을 못찾음.)

추가 변수

private Node<E> head;

헤드가 어디에 있는지 알기 위한 변수 head.

private int currentSize;

currentSize 변수. 밑에서 추가 설명.

연결 리스트의 생성자

public LinkedList(){
		head=null;
		currentsize=null;
	}

생성자는 E를 써주지 않음.

새로운 기본 생성자를 만들기 때문에 기존에 있던 기본 생성자를 오버라이딩 하게 된다.

#### 변수(currentSize)

👎 만약 연결 리스트의 크기를 구할 때, 매번 Head 부터 하나씩 차례로 세어 나간다면,

이 알고리즘의 시간 복잡도는 O(n)(정확히는 θ(n)) 가 된다.

👍 currentSize 변수를 만들고 이 리스트에 요소를 추가할 때마다 currentSizedml 값을 늘린다.

이 알고리즘의 시간 복잡도는 정확히 1이다.

크기를 구할 때 소요 시간은 요소의 개수에 영향을 받지 않게됨.

currentSize라는 포인터를 만들게 되면서 연결 리스트의 크기를 알기 위한 시간 복잡도가 상수 시간이 된다. O(1)

생각해보기

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

외부에서 next의 값을 바꾸게 되고 Node의 위치를 잃어버리게 된다.

References

자바로 구현하고 배우는 자료구조 -Rob Edwards (boostcourse)