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

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

 

연결 리스트에서 노드의 데이터를 찾기 위해서는 앞(front, HEAD와 연결된 노드(Node) 객체) 또는 뒤(rear, TAIL과 연결된 노드(Node) 객체)부터 노드의 데이터를 비교하여 노드(Node) 객체를 찾고 리턴합니다.

// 연결 리스트에서 데이터를 찾는 함수
this.findNode = function(data, findDirection) {
	if (data == undefined || typeof data == "undefined " || data == null) {
		return null; 
	}
	
	var node = null;
	
	// findDirection - front (default)
	if (findDirection == undefined || typeof findDirection == "undefined " || findDirection == null) {
		findDirection = "front"; 
	}
	
	var currentNode = this.head;
	if (findDirection == "rear") {
		currentNode = this.tail;
	}
	while(currentNode != null) {
		if (currentNode.data == data) {
			node = currentNode;
			break;
		} else {
			if (findDirection == "rear") {
				currentNode = currentNode.prevNode;
			} else {
				currentNode = currentNode.nextNode;
			}
		}
	}
	
	return node;
}

 

함수를 추가하고 이중 연결 리스트(Doubly Linked List)를 생성(new) 하여 데이터를 찾아보겠습니다.

var doublyLinkedList = new DoublyLinkedList();

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

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

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

findNode = doublyLinkedList.findNode("Data3");
console.log(findNode);
--> Node {data: 'Data3', prevNode: Node, nextNode: null}

 

 

연결 리스트에서 데이터로 노드(Node) 객체를 찾고 찾은 노드의 앞(front, 노드의 이전 노드)에 새로운 노드(Node) 객체를 추가할 때는 찾은 노드의 이전 노드(prevNode)를 생성된 노드의 이전 노드(prevNode)에 참조시키고 찾은 노드의 이전 노드(prevNode)의 다음 노드(nextNode)에 생성된 노드를 참조시킵니다. 그리고 찾은 노드의 이전 노드(prevNode)에 생성된 노드를 참조시키고 생성된 노드의 다음 노드(nextNode)에 찾은 노드를 참조시킵니다. 

 

그러나 찾은 노드의 이전 노드(prevNode)가 NULL이면 찾은 노드의 이전 노드(prevNode)에 생성된 노드를 참조시키고 생성된 노드의 다음 노드(nextNode)에 찾은 노드를 참조시킵니다. 그리고 생성된 노드를 HEAD에 참조시킵니다.

 

반대로 찾은 노드의 뒤(rear, 노드의 다음 노드)에 새로운 노드(Node) 객체를 추가할 때는 찾은 노드의 다음 노드(nextNode)를 생성된 노드의 다음 노드(nextNode)에 참조시키고 찾은 노드의 다음 노드(nextNode)의 이전 노드(prevNode)에 생성된 노드를 참조시킵니다. 그리고 찾은 노드의 다음 노드(nextNode)에 생성된 노드를 참조시키고 생성된 노드의 이전 노드(prevNode)에 찾은 노드를 참조시킵니다.

 

그러나 찾은 노드의 다음 노드(nextNode)가 NULL이면 찾은 노드의 다음 노드(nextNode)에 생성된 노드를 참조시키고 생성된 노드의 이전 노드(prevNode)에 찾은 노드를 참조시킵니다. 그리고 생성된 노드를 TAIL에 참조시킵니다.

// 연결 리스트에서 데이터를 찾은 후 앞(front) 또는 뒤(rear)에 데이터를 추가하는 함수
this.addNode = function(data, newData, addDirection, findDirection) {
	var node = null;
	if (addDirection == undefined || typeof addDirection == "undefined " || addDirection == null) {
		addDirection = "rear"; 
	}
	if (findDirection == undefined || typeof findDirection == "undefined " || findDirection == null) {
		findDirection = "front"; 
	}
	
	var findNode = this.findNode(data, findDirection);
	if (findNode != null) {
		// 노드 생성
		node = new Node(newData);
		
		if (addDirection == "front") {
			if (findNode.prevNode == null) {
				// 찾은 노드의 이전 노드에 생성된 노드를 참조시킵니다.
				findNode.prevNode = node;
				// 생성된 노드의 다음 노드에 찾은 노드를 참조시킵니다.
				node.nextNode = findNode;
				
				// 생성된 노드를 HEAD에 참조시킵니다.
				this.head = node;
			} else {
				// 생성된 노드의 이전 노드에 찾은 노드의 이전를 참조시킵니다.
				node.prevNode = findNode.prevNode;
				// 찾은 노드의 이전 노드의 다음 노드에 생성된 노드를 참조시킵니다.
				findNode.prevNode.nextNode = node;
				
				// 찾은 노드의 이전 노드에 생성된 노드를 참조시킵니다.
				findNode.prevNode = node;
				// 생성된 노드의 다음 노드에 찾은 노드를 참조시킵니다.
				node.nextNode = findNode;
			}
		} else {
			if (findNode.nextNode == null) {
				// 찾은 노드의 다음 노드에 생성된 노드를 참조시킵니다.
				findNode.nextNode = node;
				// 생성된 노드의 이전 노드에 찾은 노드를 참조시킵니다.
				node.prevNode = findNode;
				
				// 생성된 노드를 TAIL에 참조시킵니다.
				this.tail = node;
			} else {
				// 생성된 노드의 다음 노드에 찾은 노드의 다음 노드를 참조시킵니다.
				node.nextNode = findNode.nextNode;
				// 찾은 노드의 다음 노드의 이전 노드에 생성된 노드를 참조시킵니다.
				findNode.nextNode.prevNode = node;
				
				// 찾은 노드의 다음 노드에 생성된 노드를 참조시킵니다.
				findNode.nextNode = node;
				// 생성된 노드의 이전 노드에 찾은 노드를 참조시킵니다.
				node.prevNode = findNode;
			}
		}
	}
	
	return node;
}

 

함수를 추가하고 이중 연결 리스트(Doubly Linked List)를 생성(new) 하여 데이터를 추가해 보겠습니다.

var doublyLinkedList = new DoublyLinkedList();

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

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

var addNode = doublyLinkedList.addNode("Data1", "Data4");
console.log(addNode);
--> Node {data: 'Data4', prevNode: Node, nextNode: Node}

doublyLinkedList.consoleLog();
--> Data2 -> Data1 -> Data4 -> Data3

addNode = doublyLinkedList.addNode("Data1", "Data5", "front");
console.log(addNode);
--> Node {data: 'Data5', prevNode: Node, nextNode: Node}

doublyLinkedList.consoleLog();
--> Data2 -> Data5 -> Data1 -> Data4 -> Data3

addNode = doublyLinkedList.addNode("Data3", "Data6");
console.log(addNode);
--> Node {data: 'Data6', prevNode: Node, nextNode: null}

doublyLinkedList.consoleLog();
--> Data2 -> Data5 -> Data1 -> Data4 -> Data3 -> Data6

addNode = doublyLinkedList.addNode("Data2", "Data7", "front");
console.log(addNode);
--> Node {data: 'Data7', prevNode: Node, nextNode: Node}

doublyLinkedList.consoleLog();
--> Data7 -> Data2 -> Data5 -> Data1 -> Data4 -> Data3 -> Data6

 

 

연결 리스트에서 데이터로 노드(Node) 객체를 찾고 찾은 노드를 삭제할 때는 찾은 노드의 이전 노드(prevNode)의 다음 노드(nextNode)를 찾은 노드의 다음 노드(nextNode)에 참조시키고 찾은 노드의 다음 노드(prevNode)의 이전 노드(prevNode)에 찾은 노드의 이전 노드(prevNode)를 참조시킵니다. 그리고 찾은 노드의 이전 노드(prevNode)와 다음 노드(nextNode)는 NULL 처리합니다.

 

그러나 찾은 노드의 다음 노드(nextNode)가 NULL이면 마지막 노드이기 때문에 TAIL에 찾은 노드의 이전 노드(prevNode)를 참조시키고 찾은 노드의 이전 노드(prevNode)의 다음 노드(nextNode)와 찾은 노드의 이전 노드(prevNode)는 NULL 처리합니다.

그리고 찾은 노드의 이전 노드(prevNode)가 NULL이면 맨 앞 노드이기 때문에 HEAD에 찾은 노드의 다음 노드(nextNode)를 참조시키고 찾은 노드의 다음 노드(nextNode)의 이전 노드(prevNode)와 찾은 노드의 다음 노드(nextNode)는 NULL 처리합니다.

 

만약 찾은 노드의 이전 노드(prevNode)와 다음 노드(nextNode)가 NULL이면 노드가 하나만 있는 상태이므로 HEAD와 TAIL를 NULL 처리합니다.

// 연결 리스트에서 데이터를 찾아 노드를 삭제하는 함수
this.removeNode = function(data, findDirection) {
	var node = null;
	
	if (this.isEmpty()) {
		console.log("Empty");
	} else {
		var findNode = this.findNode(data, findDirection);
		if (findNode != null) {
			node = findNode;
			if (findNode.prevNode == null && findNode.nextNode == null) {
				// HEAD에 NULL를 참조시킵니다.
				this.head = null;
				// TAIL에 NULL를 참조시킵니다.
				this.tail = null;
			} else {
				if (findNode.nextNode == null) {
					// TAIL에 찾은 노드의 이전 노드를 참조시킵니다.
					this.tail = findNode.prevNode;
					// 찾은 노드의 이전 노드의 다음 노드를 NULL 처리합니다.
					findNode.prevNode.nextNode = null;
					// 찾은 노드의 이전 노드를 NULL 처리합니다.
					findNode.prevNode = null;
				} else if (findNode.prevNode == null) {
					// HEAD에 찾은 노드의 다음 노드를 참조시킵니다.
					this.head = findNode.nextNode;
					// 찾은 노드의 다음 노드의 이전 노드를 NULL 처리합니다.
					findNode.nextNode.prevNode = null;
					// 찾은 노드의 다음 노드를 NULL 처리합니다.
					findNode.nextNode = null;
				} else {
					// 찾은 노드의 이전 노드의 다음 노드에 찾은 노드의 다음 노드를 참조시킵니다.
					findNode.prevNode.nextNode = findNode.nextNode;
					// 찾은 노드의 다음 노드의 이전 노드에 찾은 노드의 이전 노드를 참조시킵니다.
					findNode.nextNode.prevNode = findNode.prevNode;
					// 찾은 노드의 이전 노드와 다음 노드를 NULL 처리합니다.
					findNode.prevNode = null;
					findNode.nextNode = null;
				}
			}
		}
	}
	
	return node;
}

 

 

함수를 추가하고 이중 연결 리스트(Doubly Linked List)를 생성(new) 하여 데이터를 삭제해 보겠습니다.

var doublyLinkedList = new DoublyLinkedList();

doublyLinkedList.addLastNode("Data1");
doublyLinkedList.addFirstNode("Data2");
doublyLinkedList.addLastNode("Data4");
doublyLinkedList.addLastNode("Data3");
doublyLinkedList.addFirstNode("Data5");
doublyLinkedList.addLastNode("Data6");

doublyLinkedList.consoleLog();
--> Data5 -> Data2 -> Data1 -> Data4 -> Data3 -> Data6

var deleteNode = doublyLinkedList.removeNode("Data4");
console.log(deleteNode);
--> Node {data: 'Data4', prevNode: null, nextNode: null}

doublyLinkedList.consoleLog();
--> Data5 -> Data2 -> Data1 -> Data3 -> Data6

var deleteNode = doublyLinkedList.removeNode("Data5");
console.log(deleteNode);
--> Node {data: 'Data5', prevNode: null, nextNode: null}

doublyLinkedList.consoleLog();
--> Data2 -> Data1 -> Data3 -> Data6

var deleteNode = doublyLinkedList.removeNode("Data6");
console.log(deleteNode);
--> Node {data: 'Data6', prevNode: null, nextNode: null}

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

 

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