선형데이터구조, 연결리스트(LinkedList) #3 addFirst/addLast 메서드

이전글

https://yonghwankim-dev.tistory.com/106?category=974118 

선형데이터구조, 연결리스트(LinkedList) #2 노드와 크기 및 경계조건

 

개요

이전글에서는 연결리스트 클래스에서 Node라는 내부 클래스를 정의하고 데이터를 추가하거나 제거할 때 주의해야할 경계 조건에 대해서 알아보았습니다. 이번 글에서는 연결리스트에 데이터를 추가할 때 앞쪽에 노드를 추가하는 addFirst, 뒤쪽에 노드를 추가하는 addLast 메서드를 구현하겠습니다.

 

1. addFirst 메서드

addFirst 메서드는 연결리스트의 제일 앞쪽에 노드를 추가하는 방식입니다. 

 

새로운 노드(newNode)를 연결리스트의 앞부분에 추가하는 방식은 다음과 같습니다.

1. 새로운 노드 생성
2. 새로운 노드의 next 포인터가 head를 가리키게 함
3. head 포인터가 새로운 노드를 가리키도록 함

위의 과정을 그림으로 표현하면 아래와 같습니다.

위의 그림을 코드로 표현하면 아래와 같습니다.

1. Node<E> newNode = new Node<E>(data);
2. newNode.next = head;
3. head = newNode;

 

위 과정을 addFirst 메서드로 구현하면 다음과 같습니다.

public void addFirst(E data) {
		Node<E> newNode = new Node<E>(data);
		newNode.next = head;
		head = newNode;		
		currentSize++;
}

addFirst 메서드를 테스트이전에 toString 메서드를 구현합니다.

@Override
public String toString() {
	StringBuilder sb = new StringBuilder();
	Node<E> cur = head;
	
	while(cur!=null)
	{
		sb.append(cur.data + " ");
		cur=cur.next;
	}
	sb.append("\n");
	
	return sb.toString().trim();	
}

다음 코드는 addFirst 메서드를 테스트하는 코드입니다.

@Test
void addFirstTest() {
	LinkedList<String> list = new LinkedList<String>();
	
	list.addFirst("A");
	list.addFirst("B");
	list.addFirst("C");
		
	System.out.println(list);	// Expected Output : C B A
}

C B A

addFirst 메서드를 통하여 데이터를 추가할때마다 연결리스트의 제일 앞부분에 추가했을 경우의 장점은 새로운 데이터를 추가하기 위해 뒷 부분을 살펴볼 필요가 없기 때문에 시간 복잡도가 O(1)이라는 점입니다. 그리고 경계조건에 대해서도 head가 null이라고 가정하고 addFirst 메서드를 수행하여도 문제가 없다는 점을 알 수 있습니다.

 

2. addLast 메서드

addLast 메서드는 연결리스트의 제일 뒷부분에 노드를 추가하는 방식입니다. 연결리스트의 특징은 마지막 노드의 next 포인터는 null을 가리킨다는 점입니다. 이 점을 활용하여 아래와 같이 addLast 메서드를 작성할 수 있습니다.

public void addLast(E data) {	
	Node<E> newNode = new Node<E>(data);		
	Node<E> cur = head;
	while(cur.next!=null)
	{
		cur=cur.next;
	}
		
	cur.next = newNode;
		
	currentSize++;
}

위와 같이 메서드를 수행하면 연결리스트의 제일 뒷부분에 노드를 추가할 수 있습니다. 하지만 위의 메서드는 두가지 문제점을 가지고 있습니다. 그 문제점은 아래와 같습니다.

• 자료구조가 비어있는 경우(head==null) cur.next에서 NullPointerException이 발생
• 연결리스트의 노드들이 n개 존재할 경우 데이터를 추가하기 위해서 cur 노드가 이동하는 시간복잡도가 O(n)이 소요됨

 

3. addLast 메서드 개선

기존 addLast 메서드의 2개의 문제점인 경계 조건인 문제점과 시간 복잡도를 해결하기 위해서는 아래와 같이 메서드를 작성할 수 있습니다.

public void addLast(E data) {	
	...
    
	// 1. 경계조건, 자료구조가 비어있는 경우
	if(head==null)
	{
		head = newNode;
		currentSize++;
		return;
	}
    ...
}

위와 같이 head가 null인 경우를 따로 처리해주면 연결리스트가 비어있다고 해도 에러가 발생하지 않을 것입니다.

 

2번째 문제점인 시간복잡도 O(n) 문제를 해결하기 위해서는 tail이라는 포인터를 사용하는 방법이 존재합니다. tail 포인터의 역할은 연결리스트의 제일 뒤쪽의 노드를 가리키는 역할입니다. 그림으로 표현하면 아래와 같습니다.

tail 포인터를 활용하면 연결리스트 제일 뒷부분에 노드를 상수 시간으로 추가할 수 있습니다. 추가하는 과정은 아래 그림과 같습니다.

위의 그림을 코드로 표현하면 아래와 같습니다.

1. tail.next = newNode;
2. tail = newNode;

 

위의 문제점들을 개선한 addLast 메서드는 다음과 같습니다.

public void addLast(E data) {	
	Node<E> newNode = new Node<E>(data);
	// 1. 경계조건, 자료구조가 비어있는 경우
	if(head==null)
	{
		head = tail = newNode;
		currentSize++;
		return;
	}
		
	tail.next = newNode;		
	tail = newNode;
		
	currentSize++;
}

위와 같이 tail 포인터를 활용하면 기존의 문제점인 연결리스트의 제일 뒷부분으로 이동하기 위해서 O(n) 시간을 소요하지 않고 O(1) 시간만을 소요하여 데이터를 추가할 수 있습니다.

 

4. tail 포인터로 인한 변경사항

1. 주의사항은 tail 포인터를 사용하기 위해서는 LinkedList 클래스의 필드멤버로 추가하여야 합니다.

public class LinkedList<E> {
	
    ...
    
	private Node<E> head;
	private Node<E> tail;
	private int currentSize;
	
	public LinkedList(){
		head = null;
		tail = null;
		currentSize = 0;
	}
    
    ...
    
}

 

2. tail 포인터를 활용한다면 addFirst 메서드를 수행할때 경계조건을 추가해야 합니다. 경계 조건의 내용은 연결리스트의 노드가 비어있는 경우 tail은 새로운 노드를 가리켜야 합니다. 왜냐하면 경계조건이 없다면 연결리스트가 비어있는 상태에서 addFirst 메서드를 수행하여 head가 단 한개 있는 노드를 가리키는데 tail은 null을 가리키기 때문입니다.

public void addFirst(E data) {
	Node<E> newNode = new Node<E>(data);
		
	// 1. 경계조건, 자료구조가 비어있는 경우
	if(head==null)
	{
		tail = newNode;
	}
		
	newNode.next = head;
	head = newNode;		
	currentSize++;
}

 

References

[부스트코스] 자바로 구현하고 배우는 자료구조