2-2) 연결 리스트 - addFirst, addLast (+ 자료구조의 경계 조건)

 

아래 내용은 부스트코스 <자바로 구현하고 배우는 자료구조> 강의를 들으며 정리한 것입니다.

 

경계 조건 (Boundary Conditions)

어떤 자료구조든 아래와 같은 경계 조건에서 발생 가능한 문제를 항상 고려해야 한다.

1. 자료구조가 비어있는 경우
2. 자료구조에 하나의 요소만이 들어있을 때
3. 자료구조의 시작에 삽입 / 삭제할 경우
4. 자료구조의 끝에 삽입 / 삭제할 경우
5. 자료구조의 중간 부분을 처리할 경우

 

AddFirst 메소드

아래와 같이 코드를 작성해 연결리스트 앞부분에 새로운 node를 추가할 수 있다.

public void addFirst(E obj){
	Node<E> node = new Node<E>(obj); // 1	새로운 node 객체 생성
	node.next = head; // 2  새 node의 next가 현재 head가 가리키고 있는 곳을 가리키게 함
	head = node; // 3	head가 새 노드를 가리키게 함
	currentSize ++;
}

1. 새로운 node를 만든다.
2. 새로운 node의 next가 현재 head를 가리키도록 한다.
3. head 포인터가 다시 새로운 노드를 가리키도록 한다. 

 + 리스트 크기를 나타내기 위한 currentSize를 함께 하나 추가해준다.

 

 

※ 2번이 과정이 선행해야만 하는 이유

head 포인터를 먼저 새로운 노드로 오게 하면, 기존의 node를 가리키던 head 포인터가 다른 값을 가리키게 되면서 아무것도 가리키고 있지 않게 된 기존의 node가 가비지 컬렉터로 넘어가게 된다.

 

 

경계조건 5case 살펴보기

1. 자료구조가 비어있는 경우

문제 없음

2, 3의 경우 역시 같은 방식으로 추가해주면 되기 때문에 문제 없다. 

addFirst는 맨 앞에 추가하기 위한 메소드이기에 4, 5는 고려할 필요가 없다.

 

 

addLast 메소드

연결리스트의 요소를 확인하기 위해서는 무조건 head에서 시작해서 나아가야 하는데 이를 통해 마지막까지 도달하는 것은 비효율적이다.  ( head.next.next.next.next … = node )

연결리스트 마지막 부분에 새로운 node를 추가하는 addLast 메소드를 위해 연결 리스트의 마지막을 찾아 가리키려면 임시 포인터를 사용한다. 

 

임시 포인터를 이용해 작성한 초기 addLast 

public void addLast(E obj){
	Node<E> tmp = head;	// 임시포인터 tmp
	while(tmp.next != null)  // 마지막 노드(next가 null을 가리킴)에 도달할 때까지
		tmp=tmp.next
	tmp.next=node;	// 마지막 노드에 도달: 임시 포인터가 새로운 노드를 가리키게 함
}		// 위와 같이 하여 끝까지 도달하면 tmp -> 가비지 컬렉션 (node는 그대로 남아있음)

 

그러면 위의 코드를 경계 조건에서 발생할 수 있는 문제가 있는지의 관점에서 살펴보자.

 

경계 조건 1. head가 비어있는(null) 경우  - empty list

tmp = head = null이고, 그러므로 tmp.next를 찾지 못하는 NullPointerException 런타임 에러가 발생한다.

따라서 이렇게 addLast 하려하는데 리스트가 비어있다면, 별도로 처리해 addFirst 메소드와 같은 방식으로 노드를 추가한다.

이를 포함하여 작성하면 아래와 같다.

 

 

addLast  = O(n)

public void addLast(E obj){
	Node<E> node = new Node<E>(obj);
	if (head == null){ 		// head가 비어있는 경우
		head=node;
		currentsize++;
		return;
	}
	Node<E> tmp = head;
	while(tmp.next != null)
		tmp=tmp.next
	tmp.next=node;
	currentsize++;
}

위 코드는 n번 살피기 때문에 시간복잡도 O(n)이다.

addLast의 시간복잡도를 O(1) : 상수인 더 효율적인 코드로 만들기 위해 tail 포인터를 사용한다.

 

tail 포인터를 추가한 addLast  =  O(1)

public void addLast(E obj){
	Node<E> node = new Node<E>(obj);
	if (head == null){
		head=tail=node;
		// null을 가리키던 head 포인터, tail 포인터 모두 node를 가리키게 함
		currentsize++;
		return;
	}
	tail.next=node;	 	// tail이 가리키던 노드의 next가 새로 추가하는 node를 가리키게 함
	tail = node;		// tail이 제대로 마지막 node를 가리키도록 새로 추가한 node로 지정
	currentsize++;
}

tail 포인터를 LinkedList의 내부 클래스 Node 를 작성할 때 head, currentSize와 같이 전역 변수로 설정하고

위 코드와 같이 뒤에 노드를 추가했을 때 함께 옮겨 tail이 마지막 노드를 가리키게 한다.

이렇게 tail 포인터를 사용하면 앞으로 removeLast 등에서도 어떻게 tail을 처리할 지 더 꼼꼼히 생각해야 한다.

 

 

생각해보기

Q. 왜 currentSize 변수 대신 tail 포인터를 사용할까?

마지막 노드를 찾을 때 currentSize를 사용하면 currentSize가 가장 큰 값인 것을 찾는 과정이 필요하며 더하여 currentSize 값을 바꿔야 하는데 실수로 바꾸지 않았을 경우 여러모로 복잡한 문제가 될 수 있다. tail을 사용해 만들면 항상 마지막을 가리키게 보장시킬 수 있다.