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

이전글

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

선형데이터구조, 연결리스트(LinkedList) #1 연결리스트 소개

 

1. 개요

이전글에서는 연결리스트 데이터 구조의 특징에 대해서 소개하였습니다. 이번글에서는 연결리스트 클래스의 노드 정의와 필드 멤버를 정의하는 것을 소개하겠습니다. 그리고 자료구조에서 데이터들을 추가하거나 제거할때 등의 상황에서 고려해야 하는 경계 조건에 대해서 알아보겠습니다.

 

2. 연결리스트(LinkedList) 클래스 정의

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

Node 클래스의 대표적인 특징은 next라는 포인터 노드를 가지고 있는 점입니다. next 포인터 노드의 용도는 다음 노드를 가리키는데 필요합니다. 이는 연결리스트가 배열과 달리 메모리 위에서 연속적인 위치에 존재하지 않기 때문에 next 포인터 노드를 이용하여 다음 노드를 가리킬 수 밖에 없습니다.

 

LinkedList 클래스의 필드멤버인 head의 용도는 연결리스트의 첫번째 노드를 가리키는 역할입니다. head 포인터를 이용하여 연결리스트의 노드들을 순회할 수 있습니다.

 

currentSize 필드 멤버의 역할은 현재 연결리스트의 노드들의 개수를 저장하는 역할입니다. 이 변수를 사용하지 않으면 노드들의 개수 정보가 필요할때마다 모든 노드들의 개수를 일일히 세어야 합니다. 이는 O(n)의 시간복잡도가 소요됩니다. 따라서 노드가 추가되거나 제거될 때마다 currentSize 값을 조정해준다면 O(1)의 상수시간이 소요될 수 있습니다.

 

3. 경계 조건(Boundary Conditions)

어떠한 자료구조든 아래의 경계 조건에서 문제가 생기지 않을 지 고려해야 합니다. 이는 연결리스트도 마찬가지입니다.

• 자료구조가 비어있는 경우
• 자료 구조에 단 하나의 요소가 들어있는 경우
• 자료 구조의 첫 번째 요소를 제거하거나 추가하는 경우
• 자료 구조의 마지막 요소를 제거하거나 추가하는 경우
• 자료 구조의 중간 부분을 처리하는 경우

 

References

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