Data Structures & Algorithms with Javascript : Linked Lists

[이전글]2024.07.21 - [🤖 data structures & algorithms] - Data Structures & Algorithms with Javascript : Linked Lists

2024.07.18 - [🤖 data structures & algorithms] - Data Structures & Algorithms with Javascript : Lists

👩🏻‍💻 이전 3장에서  array를 저장 메커니즘으로 활용하는 list에 대해 살펴봤다.
📖 이번에는 다른 종류의 list인 "linked-list"에 대해 살펴보자.

✍️ 어떤 점에서 list보다 효율적으로 쓰일 수 있을지 linked list란 무엇이고, class으로 구현, 그리고 종류에 대해서 다뤄보자.

☹️ Array의 한계

대부분의 프로그래밍 언어에서 array는 고정된 길이가 할당된다.

데이터 엘리먼트를 추가하거나  추가하거나 삭제했다는 걸 반영하여 엘리먼트를 위 아래로 이동시켜야 하기 때문에 번거롭다.

하지만 자바스크립트 array는 이런 복잡한 생각을 할 필요 없이 split()함수로 배열 요소를 추가하거나 삭제할 수 있다.

 

이는 자바스크립트 array는 객체로 구현되기 때문이다. 객체로 이루어졌기 때문에 c++이나 자바의 array보다 비효율적일 수 있다. array 자료구조를 활용한 연산이 느리다고 생각한다면,랜덤 요소에 접근해야하는 경우 제외하고는  linked list가 좋은 대안일 수 있다.

⛓️‍💥 Linked List 정의

Linked List는 'nodes' 라고 불리는 객체의 집합이다.

각 node는 객체 참조를 통해 다음 노드와 연결되고, 이 참조를 'link'라고 한다. 

array의 엘리먼트들은 위치에 의해 참조되지만 linked list의 엘리먼트들은 다른 엘리먼트와의 관계에 의해 참조된다.

 

다음 linked list의 예를 살펴보자.

linked list의 시작에서부터 bread는 milk를, eggs는 bread를, bacon은 eggs를 참조한다. linked list의 끝은 null node를 가리킨다.

linked-list의 시작을 표시하기 위해 head라는 특수한 node를 추가할 수 있다.

linked list에 새로운 노드를 추가하는 작업은 아주 효율적이다.

새로운 노드를 추가해주기 위해서 추가해줄 위치에 이전 노드가 새로 추가해주는 노드를 가리키고, 

새로운 노드가 다음 노드를 가리키도록 해주면 된다.

 

다음과 같이 Eggs와 Bacon 노드 사이에 새로운 노드 Cookies를 추가하는 연산을 생각해보자.

Eggs는 bread를 가리키고 있었지만, 이 link를 이제 Eggs가 Cookies를 가리키고, Cookies가 Bacon을 가리키도록 하면 된다.

linked list에서 아이템 추가

linked list에서 노드를 삭제하는 연산도 간단하다.

삭제하려는 노드를 가리키고 있는 링크가 삭제하려는 노드가 가리키고 있는 노드를 가리키도록 하면 된다.

linked list에서 아이템 삭제

⛓️‍💥 Linked List 구현

linked list 는 2개의 클래스로 구현할 수 있다. 

Node는 linked list에 노드를 추가하기 위한 클래스고, LinkedList는 노드 추가, 삭제, 리스트 보여주기 등 연산을 담당하기 위한 클래스로 만들 수 있다.

 

‼ 예제는 책의 구현을 참고하여 클래스로 재구성했습니다!!

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

class LinkedList{
	constructor(){
    	this.head = new Node("head");
    }
    
    // 다음 노드를 찾기 위한 헬퍼 함수
    find(item){
    	let currNode = this.head; // 시작 
        while(currNode.element != item){
        	currNode = currNode.next; // 노드를 돌면서 찾으려는 item을 현재 노드로 설정
        }
    	return currNode;
    }
    
    // 노드 추가
    insert(newElement, item){
    	let newNode = new Node(newElement);	// 새로운 노드 추가
        let current = this.find(item); // 추가하려는 위치
        newNode.next = current.next; // 추가하려는 위치 이전이 새로운 노드 가리키도록
        current.next = newNode;	// 추가하려는 위치의 노드가 새로운 노드를 가리키도록
    }
    
    // 이전 노드 찾기
    findPrevious(item){
    	let currNode = this.head;
        while(!(currNode.next == null) && (currNode.next.element != item)){
        	currNode = currNode.next;
        }
        return currNode;
    }
    
    // 노드 제거
    remove(item){
    	let previousNode = this.findPrevious(item);
        if(!(previousNode.next == null)){
        	previousNode.next = previousNode.next.node;
        }
    }
    
    // 노드 출력
    display(){
    	let currNode = this.head;
        const print = (item)=> console.log(item);
        while(!(currNode.next == null)){
        	print(currNode.next.element);
            currNode = currNode.next;
        }
    }
}



const cities = new LinkedList();
cities.insert("Seoul","head");
cities.insert("Incheon","Seoul");
cities.insert("Busan","Incheon");
cities.insert("Jeju","Busan");
cities.display();
console.log('\nremove Busan\n');
cities.remove("Busan");
cities.display();

/**
Seoul
Incheon
Busan
Jeju

remove Busan

Seoul
Incheon
*/

🧬 이중 Linked list

linked list를 첫 노드에서 마지막 노드까지 순회하는 건 간단하지만 이전 노드를 거슬러 순회하는 건 쉽지 않다.

Node 클래스에 이전 노드 정보를 담고 있으면 역순회하는 과정이 쉬워진다.

노드를 linked list에 추가할 때 추가로 이전과 다음 노드의 링크를 할당하는 연산을 추가해줘야한다.

double linked list

double linked list 노드 삭제

‼ 예제는 책의 구현을 참고하여 클래스로 재구성했습니다!!

class Node{
	constructor(element){
    	this.element = element;
        this.next = null;
        this.previous = null; // 이전 노드 정보
    }
}

class LinkedList{
	constructor(){
    	this.head = new Node("head");
    }
    
    // 다음 노드를 찾기 위한 헬퍼 함수
    find(item){
    	let currNode = this.head; // 시작 
        while(currNode.element != item){
        	currNode = currNode.next;
        }
    	return currNode;
    }
    
    // 노드 추가
    insert(newElement, item){
    	let newNode = new Node(newElement);
        let current = this.find(item); 
        newNode.next = current.next;
        newNode.previous = current; // 추가
        current.next = newNode;	
    }
    
    // 순회하지 않고 마지막 노드로 이동
    findLast(item){
    	let currNode = this.head;
        while(!(currNode.next == null)){
        	currNode = currNode.next;
        }
        return currNode;
    }
    
    // 노드 제거
    remove(item){
    	let currNode = this.find(item);
        if(!(currNode.next == null)){
        	currNode.previous.next = currNode.next;
            currNode.next.previous = currNode.previous;
            currNode.next = null;
            currNode.previous = null;
        }
    }
    
    // 역으로 출력
    displayReverse(){
    	let currNode = this.head;
        currNode = this.findLast();
        const print = (item)=> console.log(item);
        while(!(currNode.previous ==null)){
        	print(currNode.element);
            currNode = currNode.previous;
        }
    }
    
}



const cities = new LinkedList();
cities.insert("Seoul","head");
cities.insert("Incheon","Seoul");
cities.insert("Busan","Incheon");
cities.insert("Jeju","Busan");
cities.displayReverse();
console.log('\nremove Busan\n');
cities.remove("Busan");
cities.displayReverse();

/**

Jeju
Busan
Incheon
Seoul

remove Busan

Jeju
Incheon
Seoul

*/

🛟 순환 linked list

순환 linked list는 단일 linked list의 node 종류와 구조가 비슷하다. 

다른 점은 순환 linked list는 생성될 때 head 노드의 next 속성이 자기 자신을 가리킨다는 것이다.

head.next = head으로 할당될 수 있다. 따라서 다음과 같이 꼬리를 무는 형태로 이루어져 있다.

circular linked list

순환 linked list를 사용하면 이중 linked list를 사용하면서 이전 노드를 오가는 오버헤드를 줄일 수 있어서 좋다. 

순환 linked list는 앞으로 계속 이동하면 head로 이동하기 때문에 접근하려는 노드를 찾으려고 왔다갔다 할 필요가 없다.

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

class LinkedList {
    constructor() {
        this.head = new Node("head");
        this.head.next = this.head;
        this.current = this.head;
    }
    
    // 노드 찾기 헬퍼 함수
    find(item) {
        let currNode = this.head; 
        while (currNode.element != item) {
            currNode = currNode.next; 
        }
        return currNode;
    }
    
    // 새로운 노드 추가
    insert(newElement, item) {
        let newNode = new Node(newElement); 
        let current = this.find(item); 
        newNode.next = current.next; 
        current.next = newNode; 
    }
    
    // 이전 노드 찾기
    findPrevious(item) {
        let currNode = this.head;
        while (!(currNode.next == null) && (currNode.next.element != item)) {
            currNode = currNode.next;
        }
        return currNode;
    }
    
    // 노드 제거
    remove(item) {
        let previousNode = this.findPrevious(item);
        if (!(previousNode.next == null)) {
            previousNode.next = previousNode.next.next;
        }
    }
    
    // 모든 노드 프린트
    display() {
        let currNode = this.head;
        const print = (item) => console.log(item);
        while (!(currNode.next == null) && !(currNode.next.element == "head")) {
            print(currNode.next.element);
            currNode = currNode.next;
        }
    }
    
    // n 노드 앞으로 이동
    advance(n) {
        for (let i = 0; i < n; i++) {
            if (this.current.next != this.head) {
                this.current = this.current.next;
            } else {
                console.log("리스트 맨 끝입니다. 더 이상 앞으로 갈 수 없습니다.");
                break;
            }
        }
    }
    
    // n node 뒤로 이동
    back(n) {
        for (let i = 0; i < n; i++) {
            let prevNode = this.findPrevious(this.current.element);
            if (prevNode != this.head) {
                this.current = prevNode;
            } else {
                console.log("리스트 맨 앞입니다. 더 이상 뒤로 이동할 수 없습니다.");
                break;
            }
        }
    }
    
    // 현재 노드 데이터 보이기 
    show() {
        console.log("현재 노드: " + this.current.element);
    }
}

// Usage example

const cities = new LinkedList();
cities.insert("Seoul", "head");
cities.insert("Incheon", "Seoul");
cities.insert("Busan", "Incheon");
cities.insert("Jeju", "Busan");
cities.display();

console.log("\nRemove Busan\n");
cities.remove("Busan");
cities.display();

console.log("\nCurrent node operations\n");
cities.show();  // Show current node
cities.advance(2);  // Move forward 2 nodes
cities.show();  // Show current node
cities.back(1);  // Move backward 1 node
cities.show();  // Show current node

🍀 마치면서

☺️ 오늘은 큐가 무엇인지, 어떤 주요 연산이 있고, 큐를 사용해서 정렬하는 예시와 우선순위 큐에 대해서 살펴봤다.
이 책이 쓰이던 2014에는 클래스 문법이 공식 규정에 없었던 때라 function으로 쓰이고 있다. 물론 그냥 function으로 써도 되지만 클래스를 쓸 경우가 별롤 없어서 환기 차원에서 쓰니까 낫배드.
이전 묵혀뒀던 클래스 문법을 다시 사용해 봐서 좋았다.

---

📚 Reference

- Data Structures and Algorithms Using Java‐ Script by Michael McMillian (O’Reilly). Copyright 2014 Michael McMillan, 978-1-449-36493-9