링크드 리스트로 브라우저 히스토리 구현하기

덱 자료구조를 활용한 경우를 찾아보면 브라우저 히스토리나  멀티 스레드 스케줄링 등이 나옵니다.
익숙하고 자주 사용해 본 브라우저 히스토리 API 의 메서드를 링크드 리스트로 구현해보았습니다.

 

브라우저 히스토리

브라우저 히스토리 API는 브라우저의 세션 히스토리에 접근할 있도록 합니다. 
주요 메서드는 다음과 같습니다.

• back() : 이전 기록으로 이동
• forward() : 앞선 기록으로 이동
• go(int i) : i 만큼 이동, 음수이면 back, 양수이면 forward와 같음

 

---

 

제약 조건

 브라우저 히스토리를 구현할 때 다음을 조건으로 두었습니다.

• 히스토리의 총 길이는 5이며,
  이를 넘어갈 경우 가장 오래된 기록을 삭제합니다.

 

• back, forward, go를 모두 구현합니다.
• 히스토리의 정해진 길이보다 앞으로 가거나 뒤로 갈 수 없습니다.
• 다른 기록으로 이동했을 때 새로운 기록을 추가하게 된다면,
  그 기록보다 최신의 기록들을 모두 제거한 후 추가합니다.

 

---

브라우저 히스토리 구현

로그 클래스

방문한 기록 정보를 나타내는 클래스를 구현합니다.
방문한 곳과 방문 시각을 객체 속성으로 가집니다.

import java.time.LocalDateTime;

public class Log {
	public String path;
	public LocalDateTime visitTime;
	
	public Log(String path) {
		this.path = path;
		visitTime = LocalDateTime.now();
	}
}

 

히스토리 클래스

로그를 요소로하는 링크드 리스트, 현재 인덱스, 최대 사이즈를 객체 속성으로 가지며,
방문 기록을 추가하는 메서드인 visit과 함께 위의 제약조건대로 forward, back, go 메서드를 구현했습니다.

package collection.linkedlist;

import java.util.LinkedList;

import collection.linkedlist.Log;

public class History {
	private LinkedList<Log> logs = new LinkedList<Log>();
	private int cursor = 0;
	final private int MAX_SIZE = 5;
	
	
	public int visit(String website) {
		if (cursor == 0) {
			if (logs.size() == MAX_SIZE) {
				logs.removeLast();
			}
		} else {
			for (int i = 0; i < cursor; i++) {
				logs.removeFirst();
			}
			cursor = 0;
		}
		logs.addFirst(new Log(website));
		return logs.size();
	}
	
	
	public String forward() {
		if (cursor == 0) {
			return null;
		}
		cursor --;
		return logs.get(cursor).path;
	}
	
	
	public String back() {
		if (cursor == logs.size() - 1) {
			return null;
		}
		cursor ++;
		return logs.get(cursor).path;
	}
	
	public String go(int i) {
		if (cursor - i < 0 ) {
			cursor = 0;
		} else if (cursor - i > logs.size() - 1) {
			cursor = logs.size() - 1;
		} else {
			cursor -= i;
		}
		return logs.get(cursor).path;
	}
	
}

 

visit 은 O(1), forward, back, go 메서드는 인덱스에 비례해 시간이 소요됩니다.
방문한 기록만 앞뒤로 순회하는 사용자가 다수가 아니라면, 링크드 리스트로 히스토리를 구현하는 건 괜찮을 것 같습니다. 

전체 코드와 테스트 코드는 여기서 확인할 수 있습니다.

 

---

Reference

 

History API - Web APIs | MDN