오늘 다룰 연결 리스트를 정의하는 클래스는 이렇게 생겼습니다 연결 리스트 코드의 첫 번째 줄입니다 이제 내부 클래스를 만들겠습니다 이 내부 클래스의 타입은 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라는 포인터를 만들게 되면서 연결 리스트의 크기를 알기 위한 시간 복잡도가 상수 시간이 됩니다 그렇기 때문에 이 값을 항상 두는 것이 좋죠 어떤 일을 하기 위해 더 빠른 방법이 있다면 그 방법을 고릅시다