[선형] 8. 원형 연결 리스트

02 Oct 2021 in 자료구조 on 선형

목차

1. 원형 연결 리스트 (Circular Linked List)

원형연결리스트

각 노드가 데이터와 포인터를 가지며, 원형 형태로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조
노드 개수 / 비어있는지 확인 : CircularLinkedList.size(), CircularLinkedList.isEmpty()`
노드 추가 : CircularLinkedList.append(), CircularLinkedList.insert()
노드 삭제 : CircularLinkedList.remove(), CircularLinkedList.removeAt()
데이터 위치 확인 / 노드 출력: CircularLinkedList.indexOf(), CircularLinkedList.printNode()

2. 원형 연결 리스트 구현하기

1. 기본

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

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

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

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

let cll = new CircularLinkedList()
let node
console.log(cll) //CircularLinkedList { head: null, length: 0 }

node = new Node(123)
cll.head = node
node.next = cll.head
cll.length++
console.log(cll)
// CircularLinkedList {
//     head: <ref *1> Node { data: 123, next: [Circular *1] },
//     length: 1
//   }

2. append(), printNode()

CircularLinkedList.prototype.printNode = function () {
    process.stdout.write("head -> ")

    if (this.length != 0){
        process.stdout.write(`${this.head.data} -> `)
        for (let node = this.head.next; node != this.head; node = node.next){
            process.stdout.write(`${node.data} -> `)
        }
    }

    console.log(null)
}

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++
}

cll.append(1)
cll.append(100)
cll.append(10)

cll.printNode() //head -> 123 -> 1 -> 100 -> 10 -> null
console.log(cll.size()) //4

3. insert()

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

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

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

    if (this.isEmpty()) {
      current = node;
    } else {
      // 끝에까지 찾아서 head랑 연결해주기
      while (current.next != this.head) {
        current = current.next;
      }
    }

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

    node.next = current;
    prev.next = node;

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

  return true;
};

cll.insert(1);
cll.insert(10);
cll.insert(100);
cll.printNode(); //head -> 100 -> 10 -> 1 -> 123 -> null
cll.insert(2, 1);
cll.printNode() //head -> 100 -> 2 -> 10 -> 1 -> 123 -> null
cll.insert(3, 3);
cll.printNode(); //head -> 100 -> 2 -> 10 -> 3 -> 1 -> 123 -> null

4. remove()

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
}



cll.insert(1);
cll.insert(10);
cll.insert(100);
cll.insert(2, 1);
cll.insert(3, 3);
cll.printNode(); //head -> 100 -> 2 -> 10 -> 3 -> 1 -> 123 -> null

console.log(cll.remove(1000)) //null
cll.printNode(); //head -> 100 -> 2 -> 10 -> 3 -> 1 -> 123 -> null
console.log(cll.remove(1)) //1
cll.printNode(); //head -> 100 -> 2 -> 10 -> 3 -> 123 -> null
console.log(cll.remove(2)) //2
cll.printNode(); //head -> 100 -> 10 -> 3 -> 123 -> null
console.log(cll.remove(100)) //100
cll.printNode(); //head -> 10 -> 3 -> 123 -> null
console.log(cll.size()) //3

5. removeAt()

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
}

cll.insert(1);
cll.insert(10);
cll.insert(100);
cll.insert(2, 1);
cll.insert(3, 3);
cll.printNode(); //head -> 100 -> 2 -> 10 -> 3 -> 1 -> 123 -> null

console.log(cll.removeAt(1000)) //null
cll.printNode(); //head -> 100 -> 2 -> 10 -> 3 -> 1 -> 123 -> null
console.log(cll.removeAt(4)) //1
cll.printNode(); //head -> 100 -> 2 -> 10 -> 3 -> 123 -> null
console.log(cll.removeAt()) //100
cll.printNode(); //head -> 2 -> 10 -> 3 -> 123 -> null
console.log(cll.removeAt(1)) //10
cll.printNode(); //head -> 2 -> 3 -> 123 -> null
console.log(cll.size()) //3

6. indexOf()

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;
};

CircularLinkedList.prototype.remove2 = function (value) {
  let index = this.indexOf(value);
  return this.removeAt(index);
};

cll.insert(1);
cll.insert(10);
cll.insert(100);
cll.insert(2, 1);
cll.insert(3, 3);
cll.printNode(); //head -> 100 -> 2 -> 10 -> 3 -> 1 -> 123 -> null

console.log(cll.indexOf(1000)) //-1
console.log(cll.indexOf(1)) //4
console.log(cll.indexOf(100)) //0
console.log(cll.indexOf(10)) //2

console.log(cll.remove2(1000)); //null
cll.printNode(); //head -> 100 -> 2 -> 10 -> 3 -> 1 -> 123 -> null
console.log(cll.remove2(4)); //null
cll.printNode(); //head -> 100 -> 2 -> 10 -> 3 -> 1 -> 123 -> null
console.log(cll.remove2(2)); //2
cll.printNode(); //head -> 100 -> 10 -> 3 -> 1 -> 123 -> null
console.log(cll.remove2(1)); //1
cll.printNode(); //head -> 100 -> 10 -> 3 -> 123 -> null
console.log(cll.size()); //4

3. 문제 - 대표 선출 🤔

마을에 대표를 선출해야 한다.
모두 자신이 대표가 되고 싶어 하며, 아래 규칙을 통해 대표를 선출하기로 하였다.
규칙은 먼저 원탁에 둘러 앉아 시계 방향으로 1번부터 n번까지 번호를 부여한다.
그리고 주사위를 통해 굴러나온 숫자 m의 사람을 제외하고, 그 다음으로 나온 주사위 숫자 k만큼 이동해가며 대표 후보에서 제외시킨다.
이렇게 순회하여 1명이 남을 때까지 반복해 마을의 대표를 선출하기로 하였다.
n, m, k가 주어졌을 때 대표 후보에서 제외되는 번호를 출력해주는 프로그램을 제작하시오.
입력은 n, m, k의 자연수가 주어지며, 대표 후보에서 제외되는 번호를 순차적으로 배열로 반환한다.

로직은 알겠는데 구현을 못하겠었다..ㅠㅠ

function CircularQueue(size){
  this.array = new Array(size)
  this.size = size
  this.length = 0
  this.head = 0
  this.tail = 0
}

CircularQueue.prototype.enqueue = function (element) {
  this.length++;
  this.array[this.tail++ % this.size] = element;
}

CircularQueue.prototype.dequeue = function () {
  this.length--;
  return this.array[this.head++ % this.size];
};

function answer(n, m, k) {
  let result = [];
  // 코드 구현 시작 영역

  // 1. 원탁에 후보 번호 세팅
  let cq = new CircularQueue(n)
  for (let i =1; i<=n; i++){
    cq.enqueue(i)
  }
  console.log(cq)

  // 2. 첫번째 노드 위치로 설정
  // 음수 안나오게끔 연산
  cq.tail = cq.head = (n + m-1) % n
  console.log(cq)

  // 3. k만큼 움직이면서 대표 후보를 제거 (제거된 번호는 result 에 추가)
  let count;
  result.push(cq.dequeue())
  console.log(cq)
  while(cq.length != 0){
    count = k-1
    while (count--){
      cq.enqueue(cq.dequeue())
      console.log(cq)
    }
    result.push(cq.dequeue())
  }
  // 코드 구현 종료 영역
  return result;
}

let input = [
  [8, 2, 3],
  [10, 2, 3],
  [10, 5, 7],
];

for (let i = 0; i < input.length; i++) {
  process.stdout.write(`#${i + 1}`);
  console.log(answer(input[i][0], input[i][1], input[i][2]));
}