원형연결리스트 구현해보기

원형연결리스트란?

각 노드가 데이터와 포인터를 가지며, 원형 형태로 연결되어 있는 방식으로 데이터를 저장하는 자료구조

일반 연결리스트와 거의 비슷한 구조이지만, 마지막 node가 다시 첫번째 노드를 가리킨다는 것에서 차이점이 있다.

구현 메서드

• 노드 개수 / 비어있는지 확인 / 노드 출력: CircularLinkedList.size(), CircularLinkedList.isEmpty(), CircularLinkedList.printNode()
• 노드 추가: CircularLinkedList.append(), CircularLinkedList.insert()
• 노드 삭제: CircularLinkedList.remove(), CircularLinkedList.removeAt()
• 데이터 위치 확인: CircularLinkedList.indexOf()

1. data와 point를 가지고 있는 node 선언

function Node(value) {
    this.data = data;
    this.next = null;
}

2. head와 length를 가지고 있는 CircularLinkedList 선언

function CircularLinkedList() {
    this.head = null;
    this.length = 0;
}

3. CircularLinkedList 내부 노드 개수 (CircularLinkedList.size())

CircularLinkedList.prototype.size = function() {
    return this.length;
}

4. CircularLinkedList 내부 노드의 존재 여부 (CircularLinkedList.isEmpty())

CircularLinkedList.prototype.isEmpty = function() {
    return this.length === 0;
}

5. 노드를 출력 (CircularLinkedList.printNode())

CircularLinkedList의 경우, 마지막 node가 head를 가리키기 때문에,

node = this.head부터 할 수 없다.

그래서 처음에 node의 data를 하나 출력한 이후, head.next부터 출력한다.

CircularLinkedList.prototype.printNode = function() {
    process.stdout.write("head -> ");
    if (this.length != 0) {
        process.stdout.write(`${this.node.data} -> `);
        for (let node = this.head.next; node != this.head; node = node.next) {
            process.stdout.write(`${node.data} -> `);
        }
    }
    console.log("null");
}

6. 연결리스트 끝에 노드를 추가 (CircularLinkedList.append(value))

** 다른 과정의 경우 LinkedList와 동일하며, node.next에 this.head를 추가한다.

CircularLinkedList.prototype.append = function(value) {
    let node = new Node(value), current = this.head;

    if (this.head === null) {
        this.head = node;
    } else {
        while (current.next != this.head) {
            current = current.next;
        }
        current.next = node;
    }
    node.next = this.head;

    this.length++;
}

7. position 위치에 노드를 추가 (CircularLinkedList.insert(value, position))

1. 사용가능한 position값인지 확인한다.
2. position이 0일 때, node.next에 current를 넣는다.
3. CircularLinkedList가 비었다면 current는 다시 node가 되고, 그렇지 않다면 current의 가장 마지막지점으로 이동한다.
4. head를 node로 바꿔주고, current.next에 this.head를 넣는다.
5. position이 0이 아닌 경우, LinkedList와 같은 원리로 동작을 하지만, node.next가 없을 경우 node.next에 this.head를 넣어 circular로 만들어 준다.
6. length를 증가시킨다.

CircularLinkedList.prototype.append = function(value) {
    let node = new Node(value), current = this.head;

    if (this.head === null) {
        this.head = node;
    } else {
        while (current.next != this.head) {
            current = current.next;
        }
        current.next = node;
    }
    node.next = this.head;

    this.length++;
}

CircularLinkedList.prototype.insert = function(value, position = 0) {
    if (position < 0 || position > this.length) {
        return false;
    }

    let node = new Node(value);
    let current = this.head, index = 0, prev;

    if (position === 0) {
        node.next = current;

        if (this.isEmpty()){
            current = node;
        } else {
            while (current.next != this.head) {
                current = current.next;
            }
        }

        this.head = node;
        current.next = this.head;
    } else {
        while (index++ < position) {
            prev = current;
            current = current.next;
        }
        prev.next = node;
        node.next = current.next;

        if (node.next === null) {
            node.next = this.head;
        }
    }

    this.length++;

    return true;
}

8. 해당하는 value를 삭제(CircularLinkedList.remove(value))

1. current.data가 value가 아니며 current.next가 this.head가 아닐 때까지 prev와 current값을 바꿔준다.
2. 원형연결리스트의 경우 끝지점을 연결해줘야하기 때문에 current.data가 없어질 수 있어 data = current.data로 우선 저장해준다.
3. current가 head일 경우, head.next를 head로 변경한 이후, 끝까지 간 current.next를 this.head로 바꿔준다. 그러면 마지막과 처음이 연결된다.
4. length를 감소하고, data를 반환해준다.

CircularLinkedList.prototype.remove = function(value) {
    let current = this.head, prev = current, data;

    while (current.data != value && current.next != this.head) {
        prev = current;
        current = current.next;
    }

    if (current.data !== value) {
        return null;
    }

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

9. position 위치 노드 삭제 (CircularLinkedList.removeAt(position))

position값으로 구별하는 점을 제외하고는, 위의 remove와 동일하다.

CircularLinkedList.prototype.removeAt = function(position = 0) {
    if (position < 0 || position > this.length) {
        return null;
    }

    let current = this.head, index = 0, prev, data;

    if (position === 0) {
        data = current.data;
        
        while(current.next != this.head) {
            current = current.next;
        }
        this.head = this.head.next;
        current.next = this.head;
    } else {
        while (index++ < position) {
            prev = current;
            current = current.next;
        }
        data = current.data;
        prev.next = current.next;
    }
    this.length--;

    return data;
}

10. value값을 갖는 node의 위치를 반환 (CircularLinkedList.indexOf(value))

처음에 current가 this.head를 가리키고 있기 때문에 do while 구문을 이용해서, 먼저 실행되고 이후에 반복되도록 한다.

CircularLinkedList.prototype.indexOf = function(value) {
    let current = this.head, index = 0;
    do{
        if (current.data === value) {
            return index;
        }
        index++;
        current = current.next;
    } while (current != this.head);

    return -1;
}

관련 전체 코드는 Git에 업로드 해두었습니다.
Github_CircularLinkedList