연결리스트

연결리스트란?

연결리스트는 각 노드가 데이터와 함께 다음 노드를 가리키는 포인터를 가지고 있는 자료구조이다.

장점

각 노드에 있는 포인터가 다음 노드를 가리키는 구조이기 때문에 메모리 내에 순차적으로 저장되어 있지 않아도 되기 때문에 빈 메모리 공간을 효율적으로 사용할 수 있다.

노드를 삭제할 때는 이전 노드의 포인터만 다음 노드의 주소를 가리키게 하면 되고,
노드를 추가할 때는 이전 노드의 포인터는 추가되는 노드의 주소를, 추가되는 노드의 포인터는 이전 노드의 포인터가 가리키고 있던 다음 노드의 주소를 가리키게 하면 되므로 배열의 삭제 및 추가보다 효율적이다.

단점

노드를 찾을 때 배열처럼 인덱스로 바로 찾아갈 수 없고,
무조건 HEAD에서부터 차례대로 노드를 찾아가야므로 배열보다 접근 속도가 느리다.

코드

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

메서드

노드 추가

append(data)

연결 리스트의 마지막 위치에 data를 추가한다.

append(data) {
        if (data == "undefined") return false;
        const newNode = new Node(data);
        this.length++;
        if (this.head === null) {
            this.head = newNode;
        }
        else {
            let curNode = this.head;
            while (true) {
                if (curNode.next === null) break;
                curNode = curNode.next;
            }
            curNode.next = newNode;
        }
        return true;
    }

insert(data, position)

연결 리스트의 position 위치에 data를 추가한다.

insert(data, position = 0) {
        if (data === "undefined" || position > this.length || position < 0) return false;
        let newNode = new Node(data);
        this.length++;
        if (position === 0) {
            newNode.next = this.head;
            this.head = newNode;
        } else {
            let curNode = this.head;
            for (let i = 1; i < position; i++) {
                curNode = curNode.next;
            }
            newNode.next = curNode.next;
            curNode.next = newNode;
        }
        return true;
    }

노드 삭제

remove(data)

연결 리스트에서 data를 찾아 삭제한다.

remove(data) {
        if (data === "undefined" || this.isEmpty()) return false;
        if (this.head.data == data) {
            this.head = this.head.next;
        }
        let curNode = this.head;
        for (let i = 1; i < this.length; i++) {
            if (curNode.next.data === data) {
                curNode.next = curNode.next.next;
                this.length--;
                return true;
            }
            curNode = curNode.next;
        }
        return false;
    }

removeAt(position)

연결 리스트의 position 위치의 data를 삭제한다.

removeAt(position = 0) {
        if (position > this.length - 1 || position < 0 || this.isEmpty()) return false;
        if (position === 0) {
            this.head = this.head.next;
        }
        let curNode = this.head;
        for (let i = 1; i < position; i++) {
            curNode = curNode.next;
        }
        curNode.next = curNode.next.next;
        this.length--;
        return true;
    }

노드 개수

size()

연결 리스트의 노드 개수를 반환한다.

size() {
        return this.length;
    }

isEmpty()

연결 리스트가 비어있으면 true를 반환한다.

isEmpty() {
        return this.length === 0 ? true : false;
    }

탐색

printNode()

모든 노드를 출력한다.

printNode() {
        let data = [];
        let curNode = this.head;
        while (curNode !== null) {
            data.push(curNode.data);
            curNode = curNode.next;
        }
        console.log(`head -> ${data.join(' -> ')} -> null`);
    }

indexOf(data)

연결 리스트에서 data를 찾아 해당 위치를 반환한다.

indexOf(data) {
        if (data === "undefined" || this.isEmpty()) return false;
        let curNode = this.head;
        for (let i = 1; i <= this.length; i++) {
            if (curNode.data === data) {
                return i - 1;
            }
            curNode = curNode.next;
        }
        return false;
    }