[자바/자료구조] 단일 연결 리스트(Singly Linked List)

2022. 1. 11. 00:31

들어가며

사실 단일 연결 리스트는 운좋게 적합한 상황이 나와주지 않는 이상 사용될 일이 잘 없고 데이터 순회가 양방향으로 가능한 이중 연결 리스트가 더 많이 사용된다. 그럼에도 불구하고 단일 연결 리스트는 한 번 쯤 구현해보는 것이 좋다고 생각한다. 자료구조에서 ArrayList, Stack과 같은 배열 기반의 자료구조들을 제외하면 대부분의 자료구조가 노드와 같이 데이터와 참조를 가진 형태로 구현되는데 그러한 자료구조 중 단일 연결 리스트의 구현 난이도가 가장 낮다고 생각하기 때문이다.

연결 리스트(Linked List)

https://ku-develog.tistory.com/25

단일 연결 리스트(Singly Linked List)

단일 연결 리스트를 그림으로 표현하면 위와 같다. 가장 기본적이고 심플한 연결 리스트 구조로 head에서 시작해서 노드의 참조가 null일때까지 순방향으로 조회한다.

연결 리스트 구현하기

LinkedList 클래스

public class LinkedList<E> {
	private Node<E> head;
	private int size;
	..
}

연결 리스트의 메인이 되는 클래스다. 여기서 연결 리스트의 동작(Method)을 작성한 뒤 메인 메서드에서 객체화하여 사용할 것이다. 간단하게 멤버 변수를 보면 앞서 설명했던 첫 노드의 참조를 가지는 head가 존재하는 것을 볼 수 있다.

두 번째로 size는 이름과 자료형에서 추측할 수 있듯 리스트에 추가된 요소들의 개수를 의미한다. 연결 리스트의 특성상 데이터의 총 개수를 확인하려면 모든 데이터를 순회하며 카운팅해야 하는 번거로움이 있기 때문에 이렇게 변수를 두고 사용하는 것이 일반적이다. 데이터가 추가/삭제될 때마다 값을 증감시켜서 리스트의 총 개수 정보를 유지할 것이다.

Node 클래스

class Node<E> {
	private E element;
	private Node<E> next;
	
	public Node(E element) {
		this.element = element;
	}
	
	public Node(Node<E> next, E element) {
		this.next = next;
		this.element = element;
	}
}

노드 클래스는 저장될 데이터의 타입을 아직 모르기 때문에 제네릭 타입으로 지정하였다. 간단하게 멤버 변수를 살펴보면 다음 노드에 대한 참조를 저장하는 next 변수, 실질적인 데이터가 저장될 element 변수를 가지고 있다. 예제인 만큼 코드 길이를 줄이기 위해서 이 클래스는 LinkedList의 내부 클래스로 사용한다.

범위 확인 메서드

private void rangeCheck(int index) {
	if(index >= size || index < 0)
		throw new IndexOutOfBoundsException(
				"Index " + index + " out of bounds for length " + size);
}

특정 위치의 노드 삭제, 탐색 시에 사용되는 범위 체크 메서드다. 예를 들어 특정 위치의 노드를 삭제하려고 했으나 범위에서 벗어난 값인 경우 예외를 발생시킨다.

이렇게 여러 메서드에서 공통으로 사용되는 코드는 하나의 메서드로 만들어서 공통으로 사용하면 전체 코드의 길이를 줄일 수 있고 코드 수정이 발생해도 이 코드만 수정하면 되는 장점이 있다.

삽입, 삭제, 탐색

삽입

노드를 삽입은 다음과 같이 여러 가지 방법이 존재하는데 여기서는 간단하게 처음과 끝에 삽입하는 것을 구현해 볼 것이다.

첫 번째에 노드 삽입
특정 위치에 노드를 삽입
마지막에 삽입
리스트를 처음부터 순회하여 특정 데이터를 찾아 삭제

첫 번째에 노드 삽입

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

리스트의 처음 위치 즉, head의 앞에 노드를 추가하는 메서드다. 이 작업은 연결 리스트 기초 이론과 객체 참조에 대한 개념만 제대로 잡혀 있다면 굉장히 쉽다. 새로운 Node 객체를 생성하면서 파라미터로 받은 데이터를 초기화한다. 그리고 다음 새로운 노드의 참조를 head 노드로 지정한 뒤 연결 리스트가 가진 head를 새로운 노드로 교체해주면 된다.

마지막에 삽입

public void addLast(E e) {
	if(size == 0) {
		addFirst(e);
		return;
	}
	
	Node<E> newNode = new Node<>(e);
	Node<E> preNode = head;
	
	while(preNode.next != null)
		preNode = preNode.next;
	
	preNode.next = newNode;
	size++;
}

리스트의 마지막 위치에 노드를 추가하는 메서드다. 연결 리스트 객체는 첫 번째 노드의 위치만 알고 있기 때문에 마지막 노드에 도달하기 위해서는 모든 노드를 순회해야만 한다.

새롭게 추가될 노드 객체를 초기화하고 순회를 하는데 사용할 참조 변수 preNode에 head의 위치를 초기화한다. preNode는 반복문을 통해 다음 참조(next)가 null인 노드, 즉 마지막 노드를 찾을 때 까지 순회한다. 마지막 노드에 도달했을 때 반복문을 종료하고 마지막 노드의 다음 참조에 새로운 노드를 초기화해주는 것으로 데이터를 연결해줄 수 있다.

삭제

노드를 삭제하는 방법은 다음과 같이 여러 가지 방법이 존재하는데 삽입과는 반대로 특정 위치에 노드를 삭제하는 것을 구현해본다.

첫 번째 노드 삭제
특정 위치의 노드를 삭제
마지막 노드 삭제
리스트를 처음부터 순회하며 특정 데이터를 찾아 삭제

특정 위치의 노드를 삭제

public E remove(int index) {
	rangeCheck(index);
	
	if(index == 0) { // 삭제 대상이 첫 번째 노드일 경우
		Node<E> removeNode = head;
		head = head.next;
		
		E removeElement = removeNode.element;
		removeNode.element = null;
		removeNode.next = null;
			
		if(--size == 0)
			head = null;
		
		return removeElement;
	}
   
	// 삭제 대상이 첫 번째 노드가 아닐 경우
	Node<E> preNode = head;
	
	for(int i = 1; i < index -1; i++)
		preNode = preNode.next;
		
	Node<E> removeNode = preNode.next;
	E removeElement = removeNode.element;
	preNode.next = removeNode.next;
	removeNode.element = null;
	removeNode.next = null;
	
	size--;
	
	return removeElement;
}

코드를 보면 먼저 범위 체크를 통해 삭제하려는 노드의 위치가 범위를 벗어났는지 체크한다. 범위에 문제가 없을 경우 삭제 위치가 head 즉, 0인지 확인한다. 삭제 위치가 첫 번째 노드라면 작업이 매우 간단해지는데, head의 참조를 다음 노드로 변경시켜주기만 하면 된다. 이 때 삭제하는 노드의 값들을 null로 초기화해주면서 GC에 의해 수거될 수 있도록 한다.

삭제 대상이 head가 아닐 경우 head 노드를 시작으로 삭제 노드 이전까지 순회한다. 그리고 다음 노드(삭제 대상)의 next값을 가져와 현재 노드의 next로 초기화하는 것으로 삭제 노드 앞과 뒤의 노드가 연결하면 특정 위치에 있는 노드를 삭제할 수 있다.

특정 위치의 데이터를 삭제하는 방식의 핵심은 삭제 노드 이전까지만 리스트를 순회를 하는 것이다. 이렇게 하는 이유는 각 노드가 다음 노드에 대한 참조만 알고 있고 이전 노드의 존재는 모르고 있기 때문에 특정 노드를 삭제하고 앞뒤의 노드를 연결해주는 작업을 하기 위해서는 삭제 바로 앞의 노드가 필요한 것이다.

마무리 작업으로 size 변수를 감소시켜 리스트의 총 요소 수를 유지해준다. 또한 삭제 대상이 된 노드 객체가 GC에 수거될 수 있도록 참조를 없애준다.

실제로 노드 삭제를 구현할 땐 좀 더 세세하게 메서드를 나누지만 여러 메서드를 나누어서 구현한 걸 올리려다 보니 글이 너무 길어지고 설명할 것이 많아져 하나로 통합했다.

탐색

public E get(int index) {
	rangeCheck(index);
	Node<E> node = head;
	for(int i = 0; i < index; i++)
		node = node.next;
	return node.element;
}

삭제 파트에서 노드 순회를 구현해봤으니 탐색은 간단하게 구현할 수 있을 것이다. 특정 위치의 노드까지 순회하고 노드가 가진 데이터를 반환한다.

이중 연결 리스트보다 단일 연결 리스트가 더 나은 경우

포스팅을 하면서 단일 연결 리스트가 나은 경우가 과연 얼마나 있을까하는 생각이 들었다. 이중 연결 리스트의 구현 난이도는 단일 연결 리스트보다 상대적으로 복잡할 뿐 사실 둘 다 굉장히 쉬운 편에 속한다. 구현 난이도는 비슷하지만 장단점을 생각해봤을 때 이중 연결리스트가 훨씬 나은데, 과연 단일 연결 리스트를 사용할 상황이 있을까?

개인적으로 생각해봐도 구현 난이도가 상대적으로 낮아진다는 것 외에는 딱히 떠오르는 것이 없어서 Stackflow를 뒤져봤다.

데이터 탐색이 반드시 순방향으로만 이루어질 경우
사용할 수 있는 메모리의 양이 극한으로 제한적인 경우
기초에 충실한 기본적인 스택을 구현할 경우

'자료구조(Java) > 이론' 카테고리의 다른 글

[자바/자료구조] 연결 리스트(Linked List) (0)	2022.01.11
[자바/자료구조] ArrayList에 대하여 (0)	2021.12.03

오래된 연습장