Linkded List 구현하기

JavaScript 문법을 사용하여 Linked List를 구현해 보았습니다.

 

 

Node 클래스는 Linked List에서 각 노드를 나타내는 객체입니다.

 

각 노드는 데이터를 저장하는 부분인 data와 다음 노드를 가리키는 포인터인 next로 구성되어 있습니다.

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

---

LinkedList 클래스의 constructor(생성자)입니다.

 

LinkedList는 비연속적인 데이터 구조이기 때문에 첫 번째 Node를 가르키는 head와 LinkedList의 길이를 담는 size로 구성되어 있습니다.

초기에는 LinkedList가 비어있기 때문에 head = null과 size = 0으로 설정되어 있습니다.

class LinkedList {
    constructor() {
        this.head = null;
        this.size = 0;
    };
};

---

LinkedList 클래스의 add 메서드입니다. 리스트의 마지막에 노드를 추가할 때 사용합니다.

add(data) {
    const newNode = new Node(data); // 파라미터로 받아온 data로 새로운 노드를 생성합니다.
    let current; // 현재 노드

    if (this.head == null) { // 리스트가 비어있는 경우
        this.head = newNode; // 새 노드를 리스트의 맨 처음 노드로 설정합니다.
    } else { // 리스트에 이미 노드가 있는 경우
        current = this.head; // current 변수에 head를 할당하여 리스트의 첫 번째 노드부터 시작합니다.

        while (current.next) { // 리스트의 마지막 노드까지 이동합니다.
            current = current.next; // current를 다음 노드로 이동합니다.
        }
			
        current.next = newNode; // 마지막 노드의 다음에 새로운 노드를 연결합니다.
    }

    this.size++; // 리스트의 길이를 증가시킵니다.
};

---

LinkedList 클래스의 insert 메서드입니다. 노드를 LinkedList 맨 앞이나 주어진 위치에 삽입할 때 사용합니다.

insert(data, index) {
    // 인덱스가 양수이면서 리스트의 길이보다 작거나 같은 지 확인 후 조건에 부합하지 않은 경우 return 합니다.
    if (!(index >= 0 && index <= this.size)) {
        console.error('범위를 벗어났습니다.');
        return;
    };

    const newNode = new Node(data); // 파라미터로 받아온 data로 새로운 노드를 생성합니다.

    let current = this.head; // 현재 노드
    let currentIndex = 0; // 현재 인덱스
    let prev = null; // 이전 노드

    if (index === 0) { // 인덱스가 0인 경우, 새로운 노드를 리스트의 맨 앞에 삽입합니다.
        newNode.next = this.head; // 새 노드의 다음을 현재 head로 설정합니다.
        this.head = newNode; // head를 새 노드로 업데이트합니다.
    } else {
        while (currentIndex < index) { // 인덱스 위치까지 이동합니다.
            prev = current; // 이전 노드를 현재 노드로 설정합니다.
            current = current.next; // 현재 노드를 다음 노드로 이동합니다.
            currentIndex++; // 현재 인덱스를 증가시킵니다.
        };

        prev.next = newNode; // 이전 노드의 다음을 새 노드로 설정하여 새 노드를 삽입합니다.
        newNode.next = current; // 새 노드의 다음을 현재 노드로 설정하여 연결을 유지합니다.
    };

    this.size++; // 리스트의 길이를 증가시킵니다.
};

 

---

LinkedList 클래스의 delete 메서드입니다. 노드를 삭제할 때 사용합니다.

delete(data) {
    let current = this.head; // 현재 노드
    let prev = null; // 이전 노드

    while (current) { // 현재 노드가 있을 때까지 반복문을 돌립니다.
        if (current.data === data) { // 현재 노드의 데이터가 삭제할 데이터와 같은 경우
            if (!prev) { // 맨 앞 노드인 경우
                this.head = current.next; // head를 현재 노드의 다음 노드로 설정하여 첫 번째 노드를 삭제합니다.
            } else { // 중간 or 마지막 노드인 경우
                prev.next = current.next; // 이전 노드의 다음 노드를 현재 노드의 다음 노드로 설정하여 현재 노드를 건너뜁니다.
            }
        }

        prev = current; // 이전 노드를 현재 노드로 설정합니다.
        current = current.next; // 현재 노드를 다음 노드로 이동합니다.
    }
}

---

LinkedList 클래스의 print 메서드입니다. 노드를 출력할 때 사용합니다.

print() {
    let current = this.head;

    while (current) { // 현재 노드가 있는 동안 반복문을 돌립니다.
        console.log(current.data); // 현재 노드의 데이터를 콘솔에 출력합니다.

        current = current.next; // 다음 노드를 현재 노드로 대체합니다.
    }
}

 

 

 

전체 코드

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

class LinkedList {
    constructor() {
        this.head = null;
        this.size = 0;
    }

    add(data) {
        const newNode = new Node(data);
        let current;

        if (this.head == null) {
            this.head = newNode;
        } else {
            current = this.head;

            while (current.next) {
                current = current.next;
            }

            current.next = newNode;
        }

        this.size++;
    }

    delete(data) {
        let current = this.head;
        let prev = null;

        while (current) {
            if (current.data === data) {
                if (!prev) {
                    this.head = current.next;
                } else {
                    prev.next = current.next;
                }
            }

            prev = current;
            current = current.next;
        }
    }

    insert(data, index) {
        if (!(index >= 0 && index <= this.size)) {
            console.error('범위를 벗어났습니다.');
            return;
        }

        const newNode = new Node(data);

        let current = this.head;
        let currentIndex = 0;
        let prev = null;

        if (index === 0) {
            newNode.next = this.head;
            this.head = newNode;
        } else {
            while (currentIndex < index) {
                prev = current;
                current = current.next;
                currentIndex++;
            }

            prev.next = newNode;
            newNode.next = current;
        }

        this.size++;
    }

    print() {
        let current = this.head;

        while (current) {
            console.log(current.data);

            current = current.next;
        }
    }
}

const linkedList = new LinkedList();

linkedList.add(1);
linkedList.add(2);
linkedList.add(3);
linkedList.add(4);

console.log('------ 추가 ------');
linkedList.print(); // 1 2 3 4

linkedList.insert(5, 4);

console.log('------ 삽입 ------');
linkedList.print(); // 1 2 3 4 5

linkedList.delete(3);

console.log('------ 삭제 ------');
linkedList.print(); // 1 2 4 5