오늘은 연결 리스트에 요소를 추가하는 작업을 살펴보겠습니다
연결 리스트 맨 앞에 추가하는 경우부터 살펴보죠
리스트가 있고, 연결 리스트의 생성자를 호출할 때
가장 먼저 head를 null로 지정합니다
그리고 현재 크기는 0입니다
크기는 우선 넘어가도록 하죠
증가시킬 것인지 감소시킬 것인지만 알면 됩니다
head는 null로 생성됩니다
연결 리스트에 새로운 요소를 추가할 때
노드 클래스 객체를 하나 만들고
이 노드 클래스는 next와 data를 가지고 있습니다
그래서 연결 리스트가 비어있으면
head를 가지고 와서
새로 생성된 노드를 가리키도록 만들면 됩니다
이제 또 다른 노드를 리스트 맨 앞에 새로 추가하도록 합시다
새로운 노드를 만들고
여기 next와 data가 있습니다
여기서 어떻게 하면 될까요?
head를 옮긴 다음에
여기를 가리키도록 만들면
아무것도 A 노드를 가리키지 않기 때문에
가비지 컬렉션이 일어나게 됩니다
더이상 가리켜주는 것이 없어서 말이죠
이런 일이 일어나면 안됩니다
리스트에서 원래 head가 A를 가리키고 있었죠
그래서 여기서 가장 먼저 해야 할 것은
새로운 노드의 next도 A를 가리키게 만드는 것입니다
이제 head를 옮길 수 있죠
head는 B를 가리키고 head.next는 A를 가리킵니다
노드를 또 추가하려면
노드를 생성하고
next가 현재 head를 가리키도록 하고
head 포인터가 다시 새로운 노드를 가리키도록 만들면 됩니다
이렇게 맨 앞에 요소를 추가하면서 이 연결 리스트의 크기를 늘렸습니다
만약 리스트에 요소가 세 개 있고
네 번째 요소를 추가하고 싶으면
몇 개의 요소들을 살펴봐야
추가할 위치를 찾을 수 있을까요?
3은 아닙니다
head는 어디 있는지 알기 때문에
맨 앞에 요소를 추가하려면
새로운 노드를 여기 만들고
포인터를 설정해준 다음에
head 포인터를 이 노드로 옮기면 됩니다
새로운 요소를 추가하기 위해 이 뒷부분을 살펴볼 필요가 없었습니다
연결 리스트의 맨 앞에 추가하는 작업의 시간 복잡도는 어떻게 될까요?
정확히 1입니다
이제 맨 앞에 추가하기 위한 코드를 살펴보겠습니다
이 메소드는 타입 E의 객체를 받습니다
가장 먼저 새로운 노드를 만들어야 합니다
다른 작업을 하기 전에 꼭 만들어야 합니다
코드는 이렇게 생겼습니다
소문자로 node라고 합시다
새로운 노드로 지정합시다
객체가 무엇이든 상관 없습니다
이 객체를 추가하라고 들어왔기 때문에
그대로 Node 클래스로 넘기면 됩니다
Node 클래스는 이 객체를 data에 저장하고
next는 null을 가리키게 합니다
여기서 순서는 중요합니다
처음에는 새로운 노드를 가지고
node.next 가 리스트의 첫 노드를 가리키도록 합니다
여기 head와 이미 만들었던 노드가 있고
노드에 data와 next가 들어있습니다
이 노드를 찾기 위해
head를 이용하면 됩니다
head는 항상 리스트의 첫 노드를 가리키기 때문입니다
이것은 새로운 노드입니다
이제 node.next는
head가 가리키는 노드를 가리키게 만들면 됩니다
head가 가리키는 곳과 메모리상 같은 위치입니다
그래서 node.next에 head를 저장합니다
그리고 head 포인터가 새로운 노드를 가리키도록 하면 됩니다
지금까지 타입이 E인 객체들만 추가하고 있었습니다
이 E는 무엇인지 중요하지 않습니다
이 E를 Node 클래스에 넣고
그 내부 클래스에서 처리를 합니다
여기서 또 중요한 부분은
이 두 줄의 순서를 꼭 기켜야 합니다
그렇지 않으면
이 두 줄의 순서를 바꾸게 되면
head가 원래 있던 노드를 가리키고 있었다가
새로운 노드를 가리키게 되는데
원래 있던 노드를 가리키는 것이 이제 없기 때문에
가비지 컬렉션이 일어나게 됩니다
currentSize의 역할은
연결 리스트의 크기를 상수 시간으로 알 수 있도록 합니다
대신 새로운 요소를 추가할 때 이 값을 증가시켜야 하고
제거할 때 감소시켜야 합니다
저번에 봤던 다섯 가지 조건들을 기억하시나요?
첫 번째 주의해야 할 조건이 무엇이었죠?
비어있는 연결 리스트가 있을 때
head 는 null을 가리키죠
이렇게 head가 null을 가리키고 있다는게 중요한가요?
새로운 노드를 만들고
새로운 노드를 만들 때
Node의 생성자에서
node.next를 null로 지정합니다
그래서 next는 null입니다
여기 새로운 노드를 만들고
node.next를 head로 지정하고 head는 null을 가리키기 때문에
node.next도 결국 null을 가리키게 만든것입니다
그리고 head가
새로운 노드를 가리키도록 만들면서
이 관계를 없애기 때문에 문제는 없습니다
연결 리스트의 맨 앞에 추가하는 작업은 비어있을 때도 상관 없습니다
이제 한 개의 요소를 가진 리스트가 되버렸습니다
이 사실이 중요한가요?
요소가 한 개일 때 주의해야 할 점이 있을까요?
한 개의 요소를 가진 리스트에 추가를 할 때
새로운 노드를 만들고
node.next는 head이고
head는 new node가 됩니다
그래서 요소가 한 개만 있을 때 따로 주의 할 점은 없죠
이렇게 다섯 가시 조건들을 한 번씩 살펴봐야 합니다
리스트 중간에 추가하는 경우에 대해서는
이 메소드는 맨 앞에만 추가하기 때문에 고려할 필요가 없죠
addFirst 메소드이기 때문에 리스트의 맨 앞만 살펴보는 것입니다
맨 뒤에 추가하는 경우에 대해서도 마찬가지로
앞에만 추가하는 메소드이기 때문에 주의할 필요가 없습니다
이렇게 이 메소드는 다섯 가지 경우에서 문제가 없다는 것을 확인했습니다