JavaScript Linked List - 연결(링크드) 리스트 만들기 2, Data Structures

이어서 연결 리스트의 맨 앞에 데이터를 추가하고 삭제하는 함수를 추가하겠습니다.

 

맨 앞에 노드를 추가하기 위해서는 HEAD와 연결된 노드(Node) 객체를 생성된 노드(Node) 객체의 다음 노드로 참조시킵니다. 그리고 HEAD에 생성된 노드(Node) 객체를 참조시킵니다.

// 맨 앞에 데이터를 추가하는 함수
this.addFirstNode = function(data) {
	// 노드 객체 생성
	var node = new Node(data);
	
	// HEAD가 NULL이면 연결된 노드(Node)가 없는 빈 상태(Empty)이므로 생성된 노드를 참조시킵니다.
	if (this.isEmpty()) {
		this.head = node;
	} else {
		// HEAD가 NULL이면 연결된 노드(Node)가 없는 빈 상태(Empty)이므로 생성된 노드를 참조시킵니다.
		node.nextNode = this.head;
		// 생성된 노드를 HEAD에 참조시킵니다.
		this.head = node;
	}
}

 

맨 앞에 노드를 삭제하기 위해서는 HEAD와 연결된 노드(Node) 객체의 다음 노드가 NULL이 아니면 HEAD와 연결된 노드(Node) 객체의 다음 노드를 HEAD와 연결합니다. 만약 HEAD와 연결된 노드(Node) 객체의 다음 노드가 NULL이면 HEAD와 연결된 노드(Node) 객체가 마지막 노드(Node) 객체이므로 HEAD를 NULL 처리합니다.

// 맨 앞에 데이터를 삭제하는 함수
this.removeFirstNode = function() {
	var node = null;
	
	if (this.isEmpty()) {
		console.log("Empty");
	} else {
		// HEAD가 참조하는 노드(맨 앞 노드)
		node = this.head;
		if (this.head.nextNode != null) {
			// HEAD가 참조하는 노드의 다음 노드를 HEAD에 참조시킵니다.
			this.head = this.head.nextNode;
			// 맨 앞 노드의 다음 노드를 NULL 처리합니다.
			node.nextNode = null;
		} else {
			// HEAD가 참조하는 노드(맨 앞 노드)의 다음 노드가 NULL이면 노드가 하나만 있는 상태
			// 그래서 HEAD를 NULL 처리합니다.
			this.head = null;
		}
	}
	
	return node;
}

 

 

함수를 추가하고 단일 연결 리스트(Single Linked List)를 생성(new) 하여 데이터를 넣고 삭제하겠습니다.

var singleLinkedList = new SingleLinkedList();

console.log(singleLinkedList);
--> SingleLinkedList {head: null, addLastNode: ƒ, removeLastNode: ƒ, addFirstNode: ƒ, removeFirstNode: ƒ, isEmpty: ƒ, consoleLog: ƒ}

singleLinkedList.addLastNode("Data1");
singleLinkedList.addFirstNode("Data2");
singleLinkedList.addLastNode("Data3");

singleLinkedList.consoleLog();
--> Data2 -> Data1 -> Data3

var deleteNode = singleLinkedList.removeFirstNode();
console.log(deleteNode);
--> Node {data: 'Data2', nextNode: null}

singleLinkedList.consoleLog();
--> Data1 -> Data3

 

연결 리스트에서 데이터를 찾고 찾은 노드를 삭제하게 함수를 추가하겠습니다.

 

노드의 데이터를 찾기 위해서는 HEAD와 연결된 노드(Node) 객체부터 시작하여 연결된 마지막 노드(Node) 객체까지 데이터를 비교하여 노드(Node) 객체를 찾고 리턴합니다.

// 데이터를 찾는하는 함수
this.findNode = function(data) {
	var node = null;
	
	// HEAD가 참조하는 노드 부터 시작하여 연결된 마지막 노드를 찾습니다.
	var currentNode = this.head;
	while(currentNode != null) {
		// 노드의 데이터와 비교 대상 데이터가 같으면
		if (currentNode.data == data) {
			node = currentNode;
			break;
		} else {
			currentNode = currentNode.nextNode;
		}
	}
	
	return node;
}

 

노드의 데이터를 찾아서 새로운 노드를 추가하기 위해서는 HEAD와 연결된 노드(Node) 객체부터 연결된 마지막 노드(Node) 객체까지 노드의 데이터를 비교하여 노드(Node) 객체를 찾은 후 생성된 노드의 다음 노드에 찾은 노드의 다음 노드를 참조시키고 노드의 다음 노드에 생성된 노드를 참조시킵니다.

 

// 데이터를 찾은 후 뒤에 데이터를 추가하는 함수
this.addNode = function(data, newData) {
	// HEAD가 참조하는 노드 부터 시작하여 연결된 마지막 노드를 찾습니다.
	var currentNode = this.head;
	while(currentNode != null) {
		// 노드의 데이터와 비교 대상 데이터가 같으면
		if (currentNode.data == data) {
			// 노드 객체 생성
			var node = new Node(newData);
			// 생성된 노드의 다음 노드에 노드의 다음 노드를 참조시킵니다.
			node.nextNode = currentNode.nextNode;
			// 노드의 다음 노드에 생성된 노드를 참조시킵니다.
			currentNode.nextNode = node;
			break;
		}
	}
}

 

노드의 데이터를 찾아서 노드를 삭제하기 위해서는 HEAD와 연결된 노드(Node) 객체부터 연결된 마지막 노드(Node) 객체까지 노드의 데이터를 비교하여 노드(Node) 객체를 찾으면서 이전 노드(Node) 객체도 가져옵니다. 노드(Node) 객체를 찾은 후 이전 노드(Node) 객체가 NULL이 아니면 이전 노드(Node) 객체의 다음 노드를 찾은 노드(Node) 객체의 다음 노드로 연결합니다. 만약 이전 노드(Node) 객체가 NULL이면 HEAD와 연결된 노드(Node) 객체가 마지막 노드(Node) 객체이므로 HEAD를 NULL 처리합니다.

// 데이터를 찾아 삭제하는 함수
this.removeNode = function(data) {
	var node = null;
	
	if (this.isEmpty()) {
		console.log("Empty");
	} else {
		// 이전 노드
		var prevNode = null;
		// HEAD가 참조하는 노드 부터 시작하여 연결된 마지막 노드를 찾습니다.
		var currentNode = this.head;
		while(currentNode != null) {
			// 노드의 데이터와 비교 대상 데이터가 같으면
			if (currentNode.data == data) {
				node = currentNode;
				if (prevNode != null) {
					// 이전 노드가 NULL이 아니면 노드의 다음 노드를 이전 노드의 다음 노드로 참조를 참조시킵니다.
					prevNode.nextNode = currentNode.nextNode;
				} else {
					// 이전 노드가 NULL이면 맨 앞 노드이므로 HEAD에 노드의 다음 노드를 참조시킵니다.
					this.head = currentNode.nextNode;
				}
				// 노드의 다음 노드를 NULL 처리합니다.
				node.nextNode = null;
				break;
			} else {
				prevNode = currentNode;
				currentNode = currentNode.nextNode;
			}
		}
	}
	
	return node;
}

 

 

함수를 추가하고 단일 연결 리스트(Single Linked List)를 생성(new) 하여 데이터를 찾고 찾은 노드(Node) 객체에 데이터를 변경하고 추가, 삭제하겠습니다.

var singleLinkedList = new SingleLinkedList();

console.log(singleLinkedList);
--> SingleLinkedList {head: null, addLastNode: ƒ, removeLastNode: ƒ, addFirstNode: ƒ, removeFirstNode: ƒ, findNode: ƒ, addNode: ƒ, removeNode: ƒ, isEmpty: ƒ, consoleLog: ƒ}

singleLinkedList.addLastNode("Data1");
singleLinkedList.addFirstNode("Data2");
singleLinkedList.addLastNode("Data3");

singleLinkedList.consoleLog();
--> Data2 -> Data1 -> Data3

var findNode = singleLinkedList.findNode("Data2");
console.log(findNode);
--> Node {data: 'Data2', nextNode: Node}

findNode.data = "Data22";

singleLinkedList.consoleLog();
--> Data22 -> Data1 -> Data3

singleLinkedList.addNode("Data22", "Data4");

singleLinkedList.consoleLog();
--> Data22 -> Data4 -> Data1 -> Data3

deleteNode = singleLinkedList.removeNode("Data1");
console.log(deleteNode);
--> Node {data: 'Data1', nextNode: null}

singleLinkedList.consoleLog();
--> Data22 -> Data4 -> Data3

 

다양한 함수를 추가하여 사용해 보시기 바랍니다.