[자료구조] 연결 리스트(linked list)

이번에는 연결 리스트를 js로 구현해보았습니다.

연결 리스트를 알고 계신다를 전제로,, 연결리스트의 스펙을 먼저 보겠습니다.

method	설명
add(...arg)	새로운 아이템을 추가합니다. 인자가 하나 또는 두 개이며, 인자가 하나일 땐 해당 인자를 값으로 하는 아이템을 맨 마지막에 추가합니다. 인자가 두개라면, 첫 번째 인자는 추가될 인덱스고 두 번째 인자가 값이 됩니다.
get(index)	index에 위치한 Node를 반환합니다. 만약 해당 노드가 존재하지 않는다면 null을 리턴합니다.
size()	아이템의 총 개수를 반환합니다.
contains(value)	리스트 내부에 해당 값을 갖는 노드가 존재하는지 여부
remove(index)	인덱스에 존재하는 아이템을 제거합니다.

전체 코드는 다음과 같다. (편의를 위해 전체 아이템을 출력하는 show함수를 구현했다.)

연결리스트 코드

	function Node(value) {
	this.value = value;
	let next;
	}
	function LinkedList() {
	this.firstNode = null;
	this.length = 0;
	}
	LinkedList.prototype.add = function(...arg) {
	let newValue, index;
	if(arg.length === 1) {
	index = Number.MAX_VALUE;
	newValue = arg[0];
	} else {
	index = arg[0];
	newValue = arg[1];
	}
	let newNode = new Node(newValue);
	if(!this.firstNode) {
	this.firstNode = newNode;
	} else if (index === 0) {
	newNode.next = this.firstNode;
	this.firstNode = newNode;
	} else {
	let endNode = this.firstNode;
	let currentPosition = 1;
	while(endNode.next && currentPosition < index) {
	currentPosition++;
	endNode = endNode.next;
	}
	newNode.next = endNode.next ? endNode.next : null;
	endNode.next = newNode;
	}
	this.length++;
	}
	LinkedList.prototype.size = function() {
	return this.length;
	}
	LinkedList.prototype.show = function() {
	let currentNode = this.firstNode;
	let currentIndex = 0;
	while(currentNode && currentNode.value) {
	console.log(`[${currentIndex++}] ${currentNode.value}`);
	currentNode = currentNode.next;
	}
	console.log('------------------');
	}
	LinkedList.prototype.contains = function(value) {
	let currentNode = this.firstNode;
	let currentIndex = 0;
	while(currentNode && currentNode.value) {
	if(value === currentNode.value) {
	return true;
	}
	currentNode = currentNode.next;
	}
	return false;
	}
	LinkedList.prototype.get = function(index) {
	if(index < 0) return null;
	let currentNode = this.firstNode;
	let currentIndex = 0;
	while(currentNode && currentNode.value && currentIndex < index) {
	currentNode = currentNode.next;
	currentIndex++;
	}
	return currentNode && index === currentIndex ? currentNode : null;
	}
	LinkedList.prototype.remove = function(index) {
	if(index === 0) {
	this.firstNode = this.firstNode.next ? this.firstNode.next : null;
	this.length = this.firstNode ? this.length - 1 : 0
	} else if(index < this.size()) {
	const prevNode = this.get(index - 1);
	const selectNode = this.get(index);
	prevNode.next = selectNode.next;
	this.length = this.firstNode ? this.length - 1 : 0
	} else {
	return;
	}
	}
	let linkedList = new LinkedList();
	linkedList.add(4);
	linkedList.add('고기');
	linkedList.add(1, 7);
	linkedList.add(2, '6');
	linkedList.add(1, 9);
	console.log(linkedList.size());
	console.log(linkedList.get(5));
	console.log(linkedList.get(4));
	linkedList.show();
	linkedList.remove(0);
	linkedList.remove(6);
	linkedList.remove(2);
	linkedList.show();
	console.log(linkedList.size());
	console.log(linkedList.contains('고기'))

view raw linkedList.js hosted with ❤ by GitHub

이중연결리스트 코드

	function Node(value) {
	this.value = value;
	let next;
	let prev;
	}
	function DoubleLinkedList() {
	this.firstNode = null;
	this.lastNode = null;
	this.length = 0;
	}
	DoubleLinkedList.prototype.add = function(...arg) {
	let newValue, index;
	if(arg.length === 1) {
	index = Number.MAX_VALUE;
	newValue = arg[0];
	} else {
	index = arg[0];
	newValue = arg[1];
	}
	let newNode = new Node(newValue);
	if(!this.firstNode || !this.lastNode) {
	this.firstNode = newNode;
	this.lastNode = newNode;
	} else if (index === 0) {
	newNode.next = this.firstNode;
	this.firstNode.prev = newNode;
	this.firstNode = newNode;
	} else {
	let endNode = this.firstNode;
	let currentPosition = 1;
	while(endNode.next && currentPosition < index) {
	currentPosition++;
	endNode = endNode.next;
	}
	// 도중에 삽입
	if(endNode.next) {
	newNode.next = endNode.next
	endNode.next.prev = newNode;
	newNode.prev = endNode;
	} else {
	newNode.next = null;
	newNode.prev = endNode;
	this.lastNode = newNode;
	}
	endNode.next = newNode;
	}
	this.length++;
	}
	DoubleLinkedList.prototype.size = function() {
	return this.length;
	}
	DoubleLinkedList.prototype.show = function() {
	let currentNode = this.firstNode;
	let currentIndex = 0;
	while(currentNode && currentNode.value) {
	console.log(`[${currentIndex++}] ${currentNode.value}`);
	currentNode = currentNode.next;
	}
	console.log('------------------');
	}
	DoubleLinkedList.prototype.contains = function(value) {
	let currentNode = this.firstNode;
	let currentIndex = 0;
	while(currentNode && currentNode.value) {
	if(value === currentNode.value) {
	return true;
	}
	currentNode = currentNode.next;
	}
	return false;
	}
	DoubleLinkedList.prototype.get = function(index) {
	if(index < 0) return null;
	let currentNode = this.firstNode;
	let currentIndex = 0;
	while(currentNode && currentNode.value && currentIndex < index) {
	currentNode = currentNode.next;
	currentIndex++;
	}
	return currentNode && index === currentIndex ? currentNode.value : null;
	}
	DoubleLinkedList.prototype.remove = function(index) {
	if(index === 0) {
	this.firstNode = this.firstNode.next ? this.firstNode.next : null;
	this.length = this.firstNode ? this.length - 1 : 0
	} else if(index < this.size()) {
	const prevNode = this.get(index - 1);
	const selectNode = this.get(index);
	if(selectNode === this.lastNode) {
	this.lastNode = prevNode;
	}
	prevNode.next = selectNode.next;
	this.length = this.firstNode ? this.length - 1 : 0
	} else {
	return;
	}
	}
	let doubleLinkedList = new DoubleLinkedList();
	doubleLinkedList.add(4);
	doubleLinkedList.add('고기');
	doubleLinkedList.add(1, 7);
	doubleLinkedList.add(2, '6');
	doubleLinkedList.add(1, 9);
	console.log(doubleLinkedList.size());
	console.log(doubleLinkedList.get(5));
	console.log(doubleLinkedList.get(4));
	doubleLinkedList.show();
	doubleLinkedList.remove(0);
	doubleLinkedList.remove(6);
	doubleLinkedList.remove(2);
	doubleLinkedList.show();
	console.log(doubleLinkedList.size());
	console.log(doubleLinkedList.contains('고기'))
	console.log(doubleLinkedList.get('고기'))

view raw doubleLinkedList.js hosted with ❤ by GitHub

코드 개선이 필요하지만, 그건 나중에.. 0인덱스나 끝 인덱스 처리에 대해 깔끔하지 않는게 조금 아쉽다..