연결리스트 구현해보기

연결리스트란?

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

구현 메서드

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

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

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

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

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

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

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

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

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

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

1. node에 LinkedList의 head를 저장해둔다.
2. node의 마지막은 null이기에, null이 아닐 때까지 loop문을 진행한다.
3. node의 포인터를 node.next로 변경해준다.

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

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

1. 새로운 노드를 생성한다.
2. 현재 head를 current에 저장한다.
3. LinkedList가 비어있을 경우 (head가 null일 경우) head에 노드를 저장한다.
4. 그렇지 않을 경우, current.next가 null이 아닐 때까지 current의 포인터를 current.next로 옮긴다.
5. current.next에 새롭게 만든 노드를 저장한다.
6. LinkedList의 length를 증가시킨다.

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

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

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

1. 위치 값이 0보다 작거나 기존 LinkedList의 길이보다 클 경우, false를 리턴한다.
2. 새로 노드를 생성하고, current에 head, index, prev를 선언한다.
3. 만약 position이 0일 경우, 가장 처음에 node를 넣는 것이기 때문에, node.next를 current로 바꿔주고, head에 node를 삽입한다.
4. position이 0이 아닐 경우, position이 될 때까지 prev에 current를 임시저장한 후, current에 current.next를 넣는다.
5. position까지 이동하면 prev.next에 node를 추가하고, node.next에 current를 넣는다.
6. length를 증가시킨다.

LinkedList.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;
        this.head = node;
    } else {
        while (index++ < position) {
            prev = current;
            current = current.next;
        }
        prev.next = node;
        node.next = current;
    }
    this.length++;
    return true;
}

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

1. current.data가 value가 아니거나, next가 있을 경우 prev에 current를 임시저장하고, current에 current.next를 저장한다.
2. 끝까지 찾고도 current.data가 없을 경우, null를 반환한다.
3. current가 this.head일 경우, head를 current.next로 바꾸며 current를 없앤다.
4. head가 아닐 경우, prev.next를 current.next로 바꾼다.
5. length를 줄인다.

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

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

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

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

    return current.data;
}

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

1. position값 확인한다
2. current에 head 저장하고, index, prev 선언한다.
3. position이 0일 경우, head를 current.next로 변경한다.
4. position 위치까지 이동한 후 prev.next를 current.next로 변경하면서 기존 current값 삭제한다.
5. length를 줄이고, current.data를 반환한다.

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

    let current = this.head, index = 0, prev;
    if (position === 0) {
        this.head = current.next;
    } else {
        while (index++ < position) {
            prev = current;
            current = current.next;
        }
        prev.next = current.next;
    }

    this.length--;

    return current.data;
}

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

1. current가 null이 아니고, 현재 current.data가 찾는 value일 경우 바로 index를 반환한다.
2. 현재 current.data가 value가 아니면, Index를 증가시키고 current의 포인터를 current.next로 이동한다.
3. 찾는 값이 없을 경우 -1를 반환한다.

LinkedList.prototype.indexOf = function(value) {
    let current = this.head, index = 0;

    while (current != null) {
        if (current.data === value) {
            return index;
        }
        index++;
        current = current.next;
    }
    return -1;
};

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