JS. 연결리스트 - 코딩테스트 광탈 방지, A to Z : JavaScript

정의

연결 리스트 : 각 요소를 포인터로 연결하여 관리하는 선형 자료구조

각 요소는 노드라고 부르며, 데이터 영역과 포인터 영역으로 구성된다

 

c언어에서 포인터를 배웠다면 이해가 쉬울 거 같다

나 같은 경우 정처기를 준비하면서 c언어를 접하였는데, 그 덕에 이해가 쉬웠다.

강희영 선생님 만세!

 

하... 그리고 내가 이 모든 걸 이해한다고 생각하면 오해다

 

하...

 

Singly Linked List

Head에서 Tail까지 단방향으로 이어지는 연결 리스트

 

Doubly Linked List

양방향으로 이어지는 연결 리스트

 

Circular Linked List

Tail이 Head로 연결되는 연결 리스트

 

코드

class Node {
	constructor(value) {
    	this.value = value;
        this.next = null;
    }
}

class SinglyLinkedList {
	constructor() {
    	this.head = null;
        this.tail = null;
    }
    
    find(value) {
    	let currNode = this.head;
        while (currNode.value !== value) {
        	currNode = currNode.next;
        }
        return currNode;
    }
    
    append(newValue) {
    	const newNode = new Node(newValue);
        if (this.head === null) {
			this.head = newNode;
			this.tail = newNode;
        } else {
			this.tail.next = newNode;
			this.tail = newNode;
        }
    }
    
    insert(node, newValue) {
    	const newNode = new Node(newValue);
        newNode.next = node.next;
        node.next = newNode;
    }
    
    remove(value) {
    	let prevNode = this.head;
        while (prevNode.next.value !== value) {
        	prevNode = prevNode.next;
        }
        
        if (prevNode.next !== null) {
        	prevNode.next = prevNode.next.next;
        }
    }
    
    display() {
    	let currNode = this.head;
        let displayString = "[";
        while (currNode !== null) {
        	displayString += `${currNode.value}, `;
            currNode = currNode.next
        }
        displayString = displayString
        	.substr(0, displayString.length - 2);
        displayString += "]";
        console.log(displayString);
    }
}

실행하기

const linkedList = new SinglyLinkedList();

linkedList.append(1);
linkedList.append(2);
linkedList.append(3);
linkedList.append(5);

linkedList.display();
// [1, 2, 3, 5]

console.log(linkedList.find(3));
// Node { value: 3, next: Node { value: 5, next: null } }

linkedList.remove(3);

linkedList.display();
// [1, 2, 5]

linkedList.insert(linkedList.find(2), 10);

linkedList.display();
// [1, 2, 10, 5]