-
오늘 다룰 연결 리스트를
정의하는 클래스는
-
이렇게 생겼습니다
-
연결 리스트 코드의
첫 번째 줄입니다
-
이제 내부 클래스를 만들겠습니다
-
이 내부 클래스의 타입은
Node입니다
-
내부 클래스는 두 가지를 가지고 있죠
-
저번에 그렸던
노드 객체에서도 봤습니다
-
그 두 가지는
next라는 포인터와
-
data입니다
-
data의 타입은 E입니다
-
E가 무엇인지 우리는 모르고
중요하지도 않습니다
-
정해지지 않은 타입이고
-
이렇게 구현한 연결 리스트를 사용하면
-
그때 지정하겠다는
의미입니다
-
그리고 이 next는
-
다른 노드를 가리키는 포인터입니다
-
그래서 next는 마찬가지로 타입이
Node입니다
-
이렇게 두 변수
next와 data를 만들었고
-
이제 생성자만 만들면 됩니다
-
노드를 만들 때
비어있는 노드를 만들지는 않죠
-
안에 내용이 들어갈 걸 알기 때문에
-
이 생성자는
-
항상 어떠한 객체를 받게 됩니다
-
타입은 지정되지 않았기 때문에
마찬가지로 E이고
-
그 객체를 data에 저장하고
-
next는 우선 null로 지정합니다
-
이 내부 클래스가
노드 객체에 해당합니다
-
내부 클래스이기 때문에
-
다른 곳에서 접근할 수 없습니다
-
연결 리스트가 아닌 다른 곳에서
접근하도록 만들면 안되겠죠
-
이 노드들이 어떻게 구성되어 있는지
공개하지 않습니다
-
그리고 data도 다른 곳에서
접근하는 것을 막아야 합니다
-
가장 중요한 것은 next 포인터에도
접근하지 못하도록 막아야 하죠
-
예를 들어, 연결 리스트를
잘 만들어 놓았는데
-
외부에서 이 next 포인터들을 건드리면
-
노드들의 위치를 바꾸게 되고
정보를 잃게 되겠죠
-
곧 다시 설명하겠습니다
-
내부 클래스로 만들게 되면
-
이 클래스에 접근할 수 있는 것들은
-
외부 클래스에 있는 객체들이나
메소드들뿐이죠
-
내부 클래스로 만들었기 때문에
-
이곳에서만 다룰 수 있도록 제한한 거죠
-
이제 변수만 몇 개 더 만들면 됩니다
-
헤드가 어디에 있는지
알아야 하므로
-
private 변수 head를 만들겠습니다
-
그리고 다른 변수를
하나 더 만듭시다
-
아, 그리고 head의 타입은
당연히 Node여야 하죠
-
그리고 int 타입인
변수를 만들겠습니다
-
이 변수를 currentSize라 부르겠습니다
-
이 변수에 대해서는 나중에
다시 얘기하도록 하죠
-
이 부분을 이제 완성하기 위해
-
연결 리스트의 생성자를 만들겠습니다
-
첫 줄은 public LinkedList
-
그리고 생성자를 만들 때
-
E를 써주지 않습니다
-
그리고 새로운 기본 생성자를
만들기 때문에
-
기존에 있던 기본 생성자를
오버라이딩 하게 됩니다
-
여기서 head는 null이라고
지정해주고
-
currentSize는
0으로 두겠습니다
-
나머지 코드는 우선 생략하고
-
LinkedList 클래스를
이렇게 마칩니다
-
data에는
E라는 타입의 객체가 들어있습니다
-
그림의 이 부분에 해당하죠
-
그리고 next는 다른 노드를
가리키는 포인터입니다
-
이제 currentSize에 대해서
잠시 설명하겠습니다
-
이런 리스트를 가지고 있을 때
-
맨 앞에 head가 있죠
-
head는 A를 가리키고
A.next는 B를 가리키고
-
B.next는 C를 가리키고
C.next는 D를 가리킵니다
-
그리고 D.next는 null을 가리키죠
-
누군가가 이 연결 리스트의 크기를
물어볼 수도 있습니다
-
이때 한 명쯤은 이 질문을
할 줄 알았는데 말이죠
-
일일이 센 다음에
크기를 알려드릴 수도 있겠죠
-
그렇게 해도 문제는 없습니다
-
여러분이 이 질문을 할 때마다
-
세서 알려드릴 수도 있겠죠
-
한 개, 두 개, 세 개
네 개, 다섯 개, 여섯 개
-
일곱 개, 여덟 개, 아홉 개
열 개, 열다섯 개, 스무 개
-
이 크기를 셀 때의
시간 복잡도가 뭘까요?
-
매번 처음부터 세야 하죠
-
그래서 만약 요소가 5개 있으면
-
몇 개의 요소를 세야 할까요?
-
요소가 10개면
몇 개를 세야 할까요?
-
요소가 n개면
몇 개를 세야 할까요?
-
n개입니다
-
그래서 하나씩
세는 것의 시간 복잡도는
-
O(n)입니다
-
모든 요소를 세야 하기 때문이죠
-
정확히 n 개를 세는 것이기 때문에
θ(n)이라고 하는게 더 정확하죠
-
리스트의 크기를 알 수 있는
방법의 하나로서
-
그때그때 세는 방법이 있죠
-
크기를 알기 위한 다른 방법은
-
currentSize라는
변수를 만들어놓고
-
이 리스트에 요소를 추가할 때마다
-
currentSize의 값을
늘리는 것입니다
-
그래서 이 리스트의
크기를 알고 싶을 때
-
1, 10, 5 혹은 1000이라고
바로 알 수 있죠
-
이럴 때의 시간 복잡도는
-
정확히 1입니다
-
크기를 알고 싶을 때마다
셀 필요가 없는 것입니다
-
요소의 개수와 상관없습니다
-
새로운 요소를 추가할 때마다
늘어나는 크기를 기록하기 때문이죠
-
하나하나 세서 시간 복잡도가
θ(n)인 방법이 있고
-
현재 크기를 기록하는 값을 두는
빠른 방법이 있죠
-
요소를 하나 추가할 때
-
값 하나를 바꾸는 건
큰일이 아닙니다
-
노드를 새로 생성하고 연결 리스트에
추가하는 것에 비하면 말이죠
-
이 currentSize라는 포인터를
만들게 되면서
-
연결 리스트의 크기를 알기 위한
시간 복잡도가 상수 시간이 됩니다
-
그렇기 때문에 이 값을
항상 두는 것이 좋죠
-
어떤 일을 하기 위해
더 빠른 방법이 있다면
-
그 방법을 고릅시다
