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

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

​

연결 리스트(Linked List)란, 데이터와 포인터로 구성된 노드(Node)들을 연결하는 구조입니다.

노드(Node)는 포인터를 이용하여 다음 노드(Node)와 연결됩니다.

 

스택(Stack), 큐(Queue), 덱/데크(Deque, Double-Ended Queue), 원형 큐/환상 큐(Circular Queue)는 버퍼(배열)를 사용하기 때문에 버퍼(배열)에서의 위치 값으로 데이터를 추가하고 가져갑니다.

 

버퍼(배열)가 아닌 포인터로 연결된 연결 리스트(Linked List)에서는 버퍼(배열)의 위치 값이 아닌 시작 포인터를 가지고 있습니다. 시작 포인터를 HEAD라고 합니다.

시작 포인트가 NULL이면 연결된 노드(Node)가 없는 빈 상태(Empty)입니다.

이처럼 노드(Node)에 하나의 포인터로 연결된 리스트를 단일 연결 리스트(Single Linked List)라고 합니다.

단일 연결 리스트(Single Linked List)는 자신과 연결된 다음 노드(Node)만 알 수 있습니다.

 

그럼 나와 연결된 이전 노드는 어떻게 찾을 수 있을까요?

단일 연결 리스트(Single Linked List)의 노드(Node)의 구조로는 불가능합니다.

 

그래서 노드(Node)에 포인터를 이전 포인터와 다음 포인터로 구성하여 이전 노드(Node)를 알 수 있게 하는 연결된 리스트를 이중 연결 리스트(Doubly Linked List)라고 합니다.

 

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

 

그리고 단일 연결 리스트(Single Linked List)에서 마지막 노드(Node)의 포인터를 첫 번째 노드(Node)와 연결한 것을 원형 연결 리스트(Circular Linked List)라고 합니다.

 

그럼 단일 연결 리스트(Single Linked List)를 만들어 보겠습니다.

 

 

JavaScript에서는 포인터라는 개념이 없습니다.

그래서 객체를 참조하는 방식을 사용합니다.

 

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

노드(Node) 객체는 데이터와 다음 노드로 구성합니다. 다음 노드는 노드(Node) 객체를 참조하게 됩니다.  

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

 

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

// HEAD
var head = null;

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

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

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

위에서 보시는 것처럼 노드(Node) 객체를 생성하고 이전 노드(Node) 객체의 nextNode에 생성된 노드(Node) 객체를 참조하게 하면 됩니다.

간단하지만 단일 연결 리스트(Single Linked List)입니다.

 

그럼 단일 연결 리스트(Single Linked List)를 콘솔로 출력해 보겠습니다.
HEAD와 연결된 노드(Node) 객체부터 nextNode가 NULL 아닌 노드(Node) 객체까지 while() 문으로 반복하면서 노드(Node) 객체의 데이터를 출력하게 합니다.

// 단일 연결 리스트 출력
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) 객체를 쉽게 찾을 수 있었습니다.

 

그러나 함수로 데이터를 추가할 경우는 마지막 노드(Node) 객체를 항상 찾아야 합니다.

// HEAD
var head = null;

// 함수로 데이터를 추가합니다.
function addNode(data) {
	// 노드 객체 생성
	var node = new Node(data);
	
	// HEAD가 NULL이면 연결된 노드(Node)가 없는 빈 상태(Empty)이므로 생성된 노드를 참조시킵니다.
	if (head == null) {
		head = node;
	} else {
		// HEAD가 참조하는 노드 부터 시작하여 연결된 마지막 노드를 찾습니다. 
		var currentNode = head;
		while(currentNode.nextNode != null) {
			currentNode = currentNode.nextNode;
		}
		// 마지막 노드의 다음 노드에 생성된 노드를 참조시킵니다.
		currentNode.nextNode = node;
	}
}

addNode("Data1");
addNode("Data2");
addNode("Data3");

// 단일 연결 리스트 출력
var linkedListText = "";
var currentNode = head;
while(currentNode != null) {
	if (linkedListText != "") {
		linkedListText += " -> "
	}
	linkedListText += currentNode.data;
	currentNode = currentNode.nextNode;
}
console.log(linkedListText);

--> Data1 -> Data2 -> Data3

 

반응형

 

또는 마지막 노드(Node) 객체를 HEAD처럼 별도로 관리할 수 있습니다. 개념적으로는 적합하지 않지만 프로그램으로 문제가 없습니다.

// HEAD
var head = null;
// 마지막 노드
var lastNode = null;

// 함수로 데이터를 추가합니다.
function addNode(data) {
	// 노드 객체 생성
	var node = new Node(data);
	
	// HEAD가 NULL이면 연결된 노드(Node)가 없는 빈 상태(Empty)이므로 생성된 노드를 참조시킵니다.
	if (head == null) {
		head = node;
	} else {
		// HEAD가 참조하는 노드 부터 시작하여 연결된 마지막 노드를 찾습니다. 
		var currentNode = head;
		while(currentNode.nextNode != null) {
			currentNode = currentNode.nextNode;
		}
		// 마지막 노드의 다음 노드에 생성된 노드를 참조시킵니다.
		currentNode.nextNode = node;
		// 생성된 노드를 마지막 노드로 참조시킵니다.
		lastNode = node;
	}
}

addNode("Data1");
addNode("Data2");
addNode("Data3");

// 단일 연결 리스트 출력
var linkedListText = "";
var currentNode = head;
while(currentNode != null) {
	if (linkedListText != "") {
		linkedListText += " -> "
	}
	linkedListText += currentNode.data;
	currentNode = currentNode.nextNode;
}
console.log(linkedListText);

--> Data1 -> Data2 -> Data3

 

연결된 리스트에서 마지막에 있는 노드(Node) 객체를 함수로 삭제하겠습니다.

 

삭제 함수에서 HEAD가 NULL이면 데이터가 없는 공백 상태(Empty)입니다. 리턴 값으로 마지막 노드(Node) 객체를 리턴하게 합니다.

 

삭제 함수에서는 마지막 노드(Node) 객체를 찾으면서 마지막 이전 노드(Node) 객체도 가져옵니다. 마지막 노드(Node) 객체를 찾은 후 마지막 이전 노드(Node) 객체가 NULL이 아니면 마지막 이전 노드(Node) 객체의 다음 노드를 NULL 처리하여 참조를 해제합니다. 즉 링크된 연결을 끊습니다. 만약 마지막 이전 노드(Node) 객체가 NULL이면 HEAD와 연결된 노드(Node) 객체가 마지막 노드(Node) 객체이므로 HEAD를 NULL 처리하여 참조를 해제합니다.

// 함수로 데이터를 삭제합니다.
function removeNode() {
	var node = null;
	
	if (head == null) {
		console.log("Empty");
	} else {
		// 마지막 이전 노드
		var prevLastNode = null;
		// HEAD가 참조하는 노드 부터 시작하여 연결된 마지막 노드를 찾습니다.
		var currentNode = this.head;
		while(currentNode.nextNode != null) {
			// 마지막 이전 노드
			prevLastNode = currentNode;
			currentNode = currentNode.nextNode;
		}
		// 마지막 노드
		node = currentNode;
		// 마지막 이전 노드의 다음 노드를 NULL 처리
		if (prevLastNode != null) {
			prevLastNode.nextNode = null;
		} else {
			// 마지막 이전 노드가 NULL이면 노드가 하나만 있는 상태
			// 그래서 HEAD를 NULL 처리
			this.head = null;
		}
	}
	
	return node;
}

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

// 단일 연결 리스트 출력
var linkedListText = "";
var currentNode = head;
while(currentNode != null) {
	if (linkedListText != "") {
		linkedListText += " -> "
	}
	linkedListText += currentNode.data;
	currentNode = currentNode.nextNode;
}
console.log(linkedListText);

--> Data1 -> Data2

 

그럼 단일 연결 리스트(Single Linked List) 객체를 만들어 보겠습니다.

 

 

 

단일 연결 리스트(Single Linked List) 객체 생성하기

 

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

// 단일 연결 리스트 객체
var SingleLinkedList = function() {
	// HEAD
	this.head = null;
	// 마지막에 데이터를 추가하는 함수
	this.addLastNode = function(data) {
		// 노드 객체 생성
		var node = new Node(data);
		
		// HEAD가 NULL이면 연결된 노드(Node)가 없는 빈 상태(Empty)이므로 생성된 노드를 참조시킵니다.
		if (this.isEmpty()) {
			this.head = node;
		} else {
			// HEAD가 참조하는 노드 부터 시작하여 연결된 마지막 노드를 찾습니다.
			var currentNode = this.head;
			while(currentNode.nextNode != null) {
				currentNode = currentNode.nextNode;
			}
			// 마지막 노드의 다음 노드에 생성된 노드를 참조시킵니다.
			currentNode.nextNode = node;
		}
	}
	// 마지막에 데이터를 삭제하는 함수
	this.removeLastNode = function() {
		var node = null;
		
		if (this.isEmpty()) {
			console.log("Empty");
		} else {
			// 마지막 이전 노드
			var prevLastNode = null;
			// HEAD가 참조하는 노드 부터 시작하여 연결된 마지막 노드를 찾습니다.
			var currentNode = this.head;
			while(currentNode.nextNode != null) {
				prevLastNode = currentNode;
				currentNode = currentNode.nextNode;
			}
			// 마지막 노드
			node = currentNode;
			// 마지막 이전 노드의 다음 노드를 NULL 처리
			if (prevLastNode != null) {
				prevLastNode.nextNode = null;
			} else {
				// 마지막 이전 노드가 NULL이면 노드가 하나만 있는 상태
				// 그래서 HEAD를 NULL 처리
				this.head = null;
			}
		}
		
		return node;
	}
	// 연결 리스트에 연결된 노드(Node)가 없는 빈 상태(Empty)인지 확인하는 함수
	this.isEmpty = function() {
		return (this.head == null);
	}
	// 연결 리스트와 연결된 노드의 데이터를 출력하는 함수
	this.consoleLog = function() {
		if (this.isEmpty()) {
			console.log("Empty");
		} else {
			var linkedListText = "";
			var currentNode = this.head;
			while(currentNode != null) {
				if (linkedListText != "") {
					linkedListText += " -> "
				}
				linkedListText += currentNode.data;
				currentNode = currentNode.nextNode;
			}
			console.log(linkedListText);
		}
	}
}

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

 

function()으로 선언된 단일 연결 리스트(Single Linked List)를 생성(new) 하고 데이터를 넣고 삭제하겠습니다.

var singleLinkedList = new SingleLinkedList();

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

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

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

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

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

 

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