자바 알고리즘 공부 4일차

👉오늘의 정리(알고리즘 비교)

LinkedList

비교전에 LinkedList를 한번 정리하고 넘어가겠습니다.

진짜 그림이 이해하는데 최고인 것 같습니다. 진짜 왜 이름이 Linked인지 확실하게 알게 해주는 객체 다이어 그램입니다. ListNode들이 계속 연결되어 있는 구조이고 이번에 메서드를 구현하면서 중요하게 여겼던 것은 연결의 시작점이 되는 첫번째 노드가 매우 중요하다는 점입니다. 그리고 확실히 index를 알면 값을 찾기가 편했던 ArrayList보다 값이 나올때 까지 순회하는 식이라 장단점 파악이 확실히 되는 느낌입니다.

ArrayList와 LinkedList

1은 상수이고 n은 선형입니다. 이번에 비교할 때 Profiler 클래스를 사용하는데 특별한 것은 아니고 학원에서도 했었던 시간비교입니다. 오늘 사용해본 것 말고도 구글 것도 있고 나중에 사용해 볼 예정입니다. 찾아보니까 cpu 체크 등등 더 많은 기능들을 지원하는데 오늘 사용한 클래스는 시간비교용으로 사용을 했습니다.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import org.jfree.data.xy.XYSeries;

import com.allendowney.thinkdast.Profiler.Timeable;

/**
	 * Characterize the run time of adding to the end of an ArrayList
	 */
	public static void profileArrayListAddEnd() {
		Timeable timeable = new Timeable() {
			List<String> list;

			public void setup(int n) {
				list = new ArrayList<String>();
			}

			public void timeMe(int n) {
				for (int i=0; i<n; i++) {
					list.add("a string");
				}
			}
		};
		int startN = 4000;
		int endMillis = 1000;
		runProfiler("ArrayList add end", timeable, startN, endMillis);
	}
	

결과값과 그래프는 다음과 같습니다.