들어가기 전에
연결 리스트의 앞부분에 node를 추가하는 addFirst 메소드에 대해 살펴보도록 하겠습니다.
학습 목표
addFirst 메소드를 이해하고 경계 조건을 만족하는지 확인할 수 있습니다.
핵심 단어
- addFirst 메소드
- 연결 리스트
- 경계 조건
- 시간 복잡도
강의 듣기
1-4. addFirst 메소드
addFirst 메소드
새로운 node를 연결 리스트의 앞부분에 추가하는 방법은 다음과 같습니다.
1. 새로운 node를 만든다.
2. 새로운 node의 next가 현재 head를 가리키도록 한다.
3. head 포인터가 다시 새로운 노드를 가리키도록 한다.
이 과정을 코드로 작성하면 다음과 같습니다.
public void addFirst(E obj){
Node<E> node = new Node<E>(obj); // 1
node.next = head; // 2
head = node; // 3
}
위 코드는 5가지 경계 조건에 대하여 생각하였을 때에도 문제가 없습니다. 그리고 새로운 요소를 추가하기 위해 뒷부분을 살펴볼 필요가 없기 때문에 시간 복잡도는 1입니다.
생각해보기
1) head가 비어있는 경우, 즉 head가 null을 가리키는 경우에 addFirst 메소드를 사용하면 node.next, head가 어떻게 달라지나요?
comment
새로운 node를 연결 리스트의 앞부분에 추가하는 방법은 다음과 같습니다.
1. 새로운 node를 만든다.
2. 새로운 node의 next가 현재 head를 가리키도록 한다.
3. head 포인터가 다시 새로운 노드를 가리키도록 한다.
여기의 2.에서 node의 next가 현재 head가 가리키는 것을 가리키도록 한다 가 더욱 헷갈리지 않을 것 같네요
새로운 node가 생기고, node.next는 null을 가리킨 다음 head는 새로 생긴 node를 가리킨다.
head가 비어있는경우 addfirst메소드를 사용하면 node.next는 head가 가리키던곳(null)을 가리키고, head는 새로운노드 node를 가리킨다.
새로생긴 node.next는 null 을 가리키게 되고, head는 새로생긴 node를 가리키게 된다
head- > node / node.next -> null
샘플코드에 currentSize 증가시켜주는 부분이 빠졌습니다.
node.next는 null, head는 새로생긴 node
head.next에는 null이 head에는 새롭게 생성한 node
첫번째로, node.next = head , 즉 nodenext 또한 헤드가 가리키는 null을 가리키게 되고, 다음으로 head = node, 즉 head가 새롭게 추가되는 node를 가리키게 됩니다. // 아랫분 댓글보니 node.next는 원래부터 null을 가리키게 되어있다는 점을 제가 간과하고 답글을 단걸 알았습니다.
1) head가 비어있는 경우, 즉 head가 null을 가리키는 경우에 addFirst 메소드를 사용하면 node.next, head가 어떻게 달라지나요?
node.next는 생성될 때 null로 지정되고 node.next=head;문장을 실행하여 node.next는 이전처럼 null을 가리키고, head는 node를 가리키게 된다.
node.next는 생성시부터 null을 가리키고 있었고, addFirst로 연결리스트에 들어간 이후에도 null을 가리킨다.
head는 null을 가리키고 있다가 방금 막 삽입된 node를 가리키게 된다.