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

이중 연결(링크드) 리스트(Doubly Linked List)

 

이중 연결 리스트(Doubly Linked List)란, 데이터와 2개의 포인터로 구성된 노드(Node)들을 연결하는 구조입니다.
노드는 2개의 포인터(이전 포인터(prev), 다음 포인터(next))를 이용하여 이전 노드와 다음 노드와 연결됩니다.

첫 번째 노드(Node)에 이전 포인터(prev)는 HEAD가 아닌 NULL입니다.

 

function()으로 Node 객체를 선언하겠습니다.
Node 객체는 데이터와 이전 노드, 다음 노드로 구성합니다. 이전 노드와 다음 노드는 Node 객체를 참조하게 됩니다.

// 노드 객체
var Node = function(data) {
	// 데이터
	this.data = data;
	// 이전 노드
	this.prevNode = null;
	// 다음 노드
	this.nextNode = null;
}

 

간단하게 노드(Node) 객체를 생성하여 이중 연결 리스트(Doubly Linked List)를 만들어 보겠습니다.

// HEAD
var head = null;

// 첫 번째 노드 생성
var firstNode = new Node("Data1");
// HEAD에 첫 번째 노드를 참조시킵니다.
head = firstNode;

// 두 번째 노드 생성
var secondNode = new Node("Data2");
// 첫 번째 노드의 다음 노드에 두 번째 노드를 참조시킵니다.
firstNode.nextNode = secondNode;
// 두 번째 노드의 이전 노드에 첫 번째 노드를 참조시킵니다.
secondNode.prevNode = firstNode;

// 세 번째 노드 생성
var thirdNode = new Node("Data3");
// 두 번째 노드의 다음 노드에 세 번째 노드를 참조시킵니다.
secondNode.nextNode = thirdNode;
// 세 번째 노드의 이전 노드에 두 번째 노드를 참조시킵니다.
thirdNode.prevNode = secondNode;

// 이중 연결 리스트 앞(HEAD)부터 출력
var linkedListText = "";
var currentNode = head;
while(currentNode != null) {
	if (linkedListText != "") {
		linkedListText += " -> "
	}
	linkedListText += currentNode.data;
	currentNode = currentNode.nextNode;
}
console.log(linkedListText);

--> Data1 -> Data2 -> Data3

노드(Node) 객체를 생성하고 이전 노드(Node) 객체의 nextNode에 생성된 노드(Node) 객체를 참조하게 하고 노드(Node) 객체의 prevNode에 이전 노드(Node) 객체를 참조하게 합니다. 그러면 노드(Node) 객체들이 서로 연결됩니다.

 

그럼 이중 연결 리스트(Doubly Linked List)에서 마지막 노드(Node) 객체부터도 HEAD와 연결된 맨 앞 노드(Node) 객체까지 출력하면 어떻게 해야 할까요?

 

HEAD처럼 마지막 노드(Node) 객체를 가리키는 마지막 포인터를 가지고 있으면 됩니다.

마지막 포인터를 TAIL이라고 합니다.

마지막 노드(Node)에 다음 포인터(next)는 TAIL이 아닌 NULL입니다.

 

노드(Node) 객체가 생성될 때마다 TAIL에 참조시키면 됩니다. 그러면 마지막에 생성된 노드(Node) 객체가 TAIL와 연결되게 됩니다.

// HEAD
var head = null;
// TAIL
var tail = null;

// 첫 번째 노드 생성
var firstNode = new Node("Data1");
// HEAD에 첫 번째 노드를 참조시킵니다.
head = firstNode;
// TAIL에 첫 번째 노드를 참조시킵니다.
tail = firstNode;

// 두 번째 노드 생성
var secondNode = new Node("Data2");
// 첫 번째 노드의 다음 노드에 두 번째 노드를 참조시킵니다.
firstNode.nextNode = secondNode;
// 두 번째 노드의 이전 노드에 첫 번째 노드를 참조시킵니다.
secondNode.prevNode = firstNode;
// TAIL에 두 번째 노드를 참조시킵니다.
tail = secondNode;

// 세 번째 노드 생성
var thirdNode = new Node("Data3");
// 두 번째 노드의 다음 노드에 세 번째 노드를 참조시킵니다.
secondNode.nextNode = thirdNode;
// 세 번째 노드의 이전 노드에 두 번째 노드를 참조시킵니다.
thirdNode.prevNode = secondNode;
// TAIL에 세 번째 노드를 참조시킵니다.
tail = thirdNode;

// 이중 연결 리스트 뒤(TAIL)부터 출력
var linkedListText = "";
var currentNode = tail;
while(currentNode != null) {
	if (linkedListText != "") {
		linkedListText += " -> "
	}
	linkedListText += currentNode.data;
	currentNode = currentNode.prevNode;
}

--> Data3 -> Data2 ->Data1

 

그럼 이중 연결 리스트(Doubly Linked List) 객체를 만들어 보겠습니다.

​

​

이중 연결 리스트(Doubly Linked List) 객체 생성하기

​

연결 리스트의 앞이나 뒤에 노드를 추가할 때는 HEAD와 TAIL이 NULL이면 연결된 노드가 없는 빈 상태(Empty)입니다. 그래서 생성된 노드를 HEAD와 TAIL에 참조시킵니다.

 

연결 리스트의 뒤에 노드를 추가할 때는 TAIL이 참조하는 노드(마지막 노드)의 다음 노드(nextNode)에 생성된 노드를 참조시키고 생성된 노드의 이전 노드(prevNode)에 마지막 노드를 참조시킵니다. 그리고 생성된 노드를 TAIL에 참조시킵니다.

 

연결 리스트의 앞에 노드를 추가할 때는 HEAD가 참조하는 노드(맨 앞 노드)의 이전 노드(prevNode)에 생성된 노드를 참조시키고 생성된 노드의 다음 노드(nextNode)에 맨 앞 노드를 참조시킵니다. 그리고 생성된 노드를 HEAD에 참조시킵니다.

 

연결 리스트의 뒤에 노드를 삭제할 때는 TAIL이 참조하는 노드(마지막 노드)의 이전 노드(prevNode)가 NULL이 아니면 마지막 노드의 이전 노드(prevNode)의 다음 노드(nextNode)를 NULL 처리하고 TAIL에 마지막 노드의 이전 노드(prevNode)를 참조시키고 마지막 노드의 이전 노드(prevNode)를 NULL 처리합니다. 만약 마지막 노드의 이전 노드(prevNode)가 NULL이면 노드가 하나만 있는 상태이므로 HEAD와 TAIL를 NULL 처리하여 연결된 노드가 없는 빈 상태(Empty)로 만듭니다.

 

연결 리스트의 앞에 노드를 삭제할 때는 HEAD가 참조하는 노드(맨 앞 노드)의 다음 노드(nextNode)가 NULL이 아니면 맨 앞 노드의 다음 노드(nextNode)의 이전 노드(prevNode)를 NULL 처리하고 HEAD에 맨 앞 노드의 다음 노드(nextNode)를 참조시키고 맨 앞 노드의 다음 노드(nextNode)를 NULL 처리합니다. 만약 맨 앞 노드의 다음 노드(nextNode)가 NULL이면 노드가 하나만 있는 상태이므로 HEAD와 TAIL를 NULL 처리하여 연결된 노드가 없는 빈 상태(Empty)로 만듭니다.

 

 

function()으로 DoublyLinkedList 객체를 선언하겠습니다.

// 이중 연결 리스트 객체
var DoublyLinkedList = function() {
	// HEAD
	this.head = null;
	// TAIL
	this.tail = null;
	// 마지막에 데이터를 추가하는 함수
	this.addLastNode = function(data) {
		// 노드 생성
		var node = new Node(data);
		
		// HEAD와 TAIL이 NULL이면 연결된 노드(Node)가 없는 빈 상태(Empty)이므로 생성된 노드를 HEAD와 TAIL에 참조시킵니다.
		if (this.isEmpty()) {
			this.head = node;
			this.tail = node;
		} else {
			// TAIL이 참조하는 노드(마지막 노드)
			var lastNode = this.tail;
			// 마지막 노드의 다음 노드에 생성된 노드를 참조시킵니다.
			lastNode.nextNode = node;
			// 생성된 노드의 이전 노드에 마지막 노드를 참조시킵니다.
			node.prevNode = lastNode;
			// 생성된 노드를 TAIL에 참조시킵니다.
			this.tail = node;
		}
	}
	// 마지막에 데이터를 삭제하는 함수
	this.removeLastNode = function() {
		var node = null;
		
		if (this.isEmpty()) {
			console.log("Empty");
		} else {
			// TAIL이 참조하는 노드(마지막 노드)
			var lastNode = this.tail;
			// 마지막 노드
			node = lastNode;
			// 마지막 노드의 이전 노드가 NULL이 아니면 마지막 노드의 이전 노드의 다음 노드를 NULL 처리합니다.
			if (lastNode.prevNode != null) {
				lastNode.prevNode.nextNode = null;
				// 마지막 노드의 이전 노드를 TAIL에 참조시킵니다.
				this.tail = lastNode.prevNode;
				// 마지막 노드의 이전 노드를 NULL 처리합니다.
				lastNode.prevNode = null;
			} else {
				// 마지막 노드의 이전 노드가 NULL이면 노드가 하나만 있는 상태입니다.
				// 그래서 HEAD와 TAIL를 NULL 처리합니다.
				this.head = null;
				this.tail = null;
			}
		}
		
		return node;
	}
	// 맨 앞에 데이터를 추가하는 함수
	this.addFirstNode = function(data) {
		// 노드 생성
		var node = new Node(data);
		
		// HEAD와 TAIL이 NULL이면 연결된 노드(Node)가 없는 빈 상태(Empty)이므로 생성된 노드를 HEAD와 TAIL에 참조시킵니다.
		if (this.isEmpty()) {
			this.head = node;
			this.tail = node;
		} else {
			// HEAD가 참조하는 노드(맨 앞 노드)
			var firstNode = this.head;
			// 맨 앞 노드의 이전 노드에 생성된 노드를 참조시킵니다.
			firstNode.prevNode = node;
			// 생성된 노드의 다음 노드에 맨 앞 노드를 참조시킵니다.
			node.nextNode = firstNode;
			// 생성된 노드를 HEAD에 참조시킵니다.
			this.head = node;
		}
	}
	// 맨 앞에 데이터를 삭제하는 함수
	this.removeFirstNode = function() {
		var node = null;
		
		if (this.isEmpty()) {
			console.log("Empty");
		} else {
			// HEAD가 참조하는 노드(맨 앞 노드)
			var firstNode = this.head;
			// 맨 앞 노드
			node = this.head;
			// 맨 앞 노드의 다음 노드가 NULL이 아니면 HEAD에 맨 앞 노드의 다음 노드를 참조시킵니다.
			if (firstNode.nextNode != null) {
				// HEAD에 맨 앞 노드의 다음 노드를 참조시킵니다.
				this.head = firstNode.nextNode;
				// 맨 앞 노드의 다음 노드를 NULL 처리합니다.
				firstNode.nextNode = null;
			} else {
				// 맨 앞 노드의 다음 노드가 NULL이면 노드가 하나만 있는 상태입니다.
				// 그래서 HEAD와 TAIL를 NULL 처리합니다.
				this.head = null;
				this.tail = null;
			}
		}
		
		return node;
	}
	// 연결 리스트에 데이터가 공백 상태인지 확인하는 함수
	this.isEmpty = function() {
		return (this.head == null && this.tail == null);
	}
	// 연결 리스트완 연결된 노드의 데이터를 출력하는 함수
	this.consoleLog = function(direction) {
		if (this.isEmpty()) {
			console.log("Empty");
		} else {
			// direction - front (default)
			if (direction == undefined || typeof direction == "undefined " || direction == null) {
				direction = "front"; 
			}
			var linkedListText = "";
			var currentNode = this.head;
			if (direction == "rear") {
				currentNode = this.tail;
			}
			while(currentNode != null) {
				if (linkedListText != "") {
					linkedListText += " -> "
				}
				linkedListText += currentNode.data;
				if (direction == "rear") {
					currentNode = currentNode.prevNode;
				} else {
					currentNode = currentNode.nextNode;
				}
			}
			console.log(linkedListText);
		}
	}
}

연결 리스트에 연결된 노드의 데이터를 앞 또는 뒤에서부터 console로 출력하는 consoleLog 함수를 만들었습니다.

 

 

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

var doublyLinkedList = new DoublyLinkedList();

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

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

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

// 뒤에서 부터 출력
doublyLinkedList.consoleLog("rear");
--> Data3 -> Data1 -> Data2

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

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

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

doublyLinkedList.consoleLog();
--> Data1

 

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