자료구조 원형 연결 리스트(Circular Linked List) #2

자료구조 원형 연결 리스트(Circular Linked List) #1

지난 번에 원형 연결 리스트 구현하다 남은 부분 구현하기

• n번째 추가
• n번째 삭제
• 특정 data값을 가진 노드 삭제
• 원형 리스트의 현재 모든 노드 출력

특정 data 값을 가진 노드 삭제

메서드 이름을 뭐라고 지어야 할지 고민하다가 결국 dropData라고 지었다....

CLL.prototype.dropData = function (data) {
  if (this.length === 0) return `연결 리스트에 노드가 존재하지 않음.`;
  let currentNode = this.head;
  let prevNode = this.head;
  let index = 0;
  let foundData = false;
  let lastNode;

  for (let node = this.head.next; node !== this.head; node = node.next) {
    lastNode = node;
  }

  while (currentNode.data !== data && index < this.length) {
    if (currentNode.data === data) {
      foundData = true;
      break;
    } else {
      currentNode = currentNode.next;
      prevNode = currentNode;
      index++;
    }
  }

  if (currentNode.data === data) foundData = true;
  if (!foundData) return `찾는 데이터 값이 존재하지 않음`;

  if (this.length === 1) {
    this.head = null;
  } else if (index === 0) {
    this.head = currentNode.next;
    lastNode.next = this.head;
  } else {
    prevNode.next = currentNode.next;
  }

  this.length--;
  return `${data}값을 가진 노드가 삭제되었습니다.`;
};

dropData 메서드 테스트

let cll = new CLL();
cll.append(1);
cll.append(2);
cll.append(3);
console.log(cll.dropData(1));
console.log(cll.dropData(1));
console.log(cll.dropData(2));
console.log(cll.dropData(3));
console.log(cll);

n번째에 노드 추가

맨 앞, 맨 뒤 위치가 아닌 사이에 낀 노드를 추가하는 경우 코드를 잘못 짜서 해당 부분 코드만 여러차례 수정했다.
분명 어려운 개념이 아닌데 헷갈려서 문제인듯...ㅠㅠ

CLL.prototype.insert = function (index, data) {
  if (this.length < index || 0 > index) {
    return `잘못된 인덱스 설정`;
  }

  let newNode = new Node(data);
  let currentNode = this.head;
  let prevNode;
  let lastNode;
  let currentIndex = 0;

  // 현재 노드가 없는 경우
  if (this.length === 0) {
    this.head = data;
  } else if (this.length === index) { // 가장 마지막에 추가하는 경우
    for (let node = this.head.next; node !== this.head; node = node.next) {
      lastNode = node;
    }

    lastNode.next = newNode;
    newNode.next = this.head;
  } else { // 중간에 추가하는 경우
    while( currentIndex !== index){
      prevNode = currentNode;
      currentNode = currentNode.next;
      currentIndex++;
    }
    console.log({currentNode, prevNode})
    newNode.next = currentNode;
    prevNode.next = newNode;
  }

  this.length++;
  return `${index}번째에 ${data}값을 가진 노드가 추가되었습니다.`;
};

insert 메서드 테스트

let cll = new CLL();
cll.append(1);
cll.append(2); 
cll.append(3); 
console.log(cll.insert(44, "테스트"));
console.log(cll.insert(1, "테스트 1번째"));
console.log(cll.insert(2, "테스트 2번째"));
console.log(cll.insert(3, "테스트 3번째"));
console.log(cll.insert(6, "테스트 마지막"));
console.log(cll);

n번째 노드 삭제

얘도 마찬가지로 맨 앞, 맨 뒤, 중간 위치에 따라 로직을 다르게 해야할 것 같아서 if-else문을 사용했다.

CLL.prototype.dropDataAt = function (index) {
  if (index > this.length || index < 0) return `잘못된 인덱스 설정`;

  let currentIndex = 0;
  let currentNode = this.head;
  let prevNode;
  let lastNode;

  if (this.length === 0) return `삭제할 수 있는 노드가 존재하지 않습니다.`;

  // 맨 앞 노드 삭제하는 경우
  if (index === 0) {
    for (let node = this.head.next; node !== this.head; node = node.next) {
      lastNode = node;
    }
    currentNode = currentNode.next;
    this.head = currentNode;
    lastNode.next = currentNode;
  } else if (index === this.length) {
    // 맨 뒤 노드 삭제하는 경우
    for (let node = this.head.next; node !== this.head; node = node.next) {
      prevNode = currentNode;
      currentNode = currentNode.next;
    }

    prevNode.next = this.head;
  } else {
    // 중간 노드 삭제하는 경우
    while (currentIndex !== index) {
      prevNode = currentNode;
      currentNode = currentNode.next;
      currentIndex++;
    }

    currentNode = currentNode.next;
    prevNode.next = currentNode;
  }

  this.length--;
  return `${index}번째 노드가 삭제되었습니다.`;
};

dropDataAt 테스트

let cll = new CLL();
cll.append(1);
cll.append(2);
cll.append(3);
cll.append(4);
console.log(cll.dropDataAt(444));
console.log(cll.dropDataAt(0));
console.log(cll);
console.log(cll.dropDataAt(3));
console.log(cll);

노드 출력하는 메서드부터 먼저 만들었으면 저렇게 하나씩 오브젝트를 안뜯어봐도 됐을텐데 ㅋㅋㅋ 가장 마지막에 만들어버림..ㅠㅠ

전체 노드 출력

현재 원형 연결 리스트에 있는 모든 노드 데이터값을 배열로 출력하는 메서드

CLL.prototype.printNode = function () {
  if (this.length === 0) return [];
  if (this.length === 1) return [this.head.data];
  let currentNode = this.head.next;
  let nodeList = [];

  nodeList.push(this.head.data);
  while (currentNode.next !== this.head) {
    nodeList.push(currentNode.data);
    currentNode = currentNode.next;
  }

  nodeList.push(currentNode.data);

  return nodeList;
};

길이가 0인 경우엔 빈 배열을 반환하도록 했다.
length가 1 일때도 따로 if문으로 예외처리를 한 것은 안그러면 원형 연결 리스트 노드가 1개일 때 중복으로 데이터가 들어가기 때문에..

printNode 테스트

let cll = new CLL();
console.log(cll.printNode());

cll.append(1);
console.log(cll.printNode());

cll.append(2);
cll.append(3);
cll.append(4);
console.log(cll.printNode());

특정 data 값 삭제하는 메서드 구현할 때랑 insert 구현할 때가 제일 오래걸렸다.
아무튼 연결 리스트 3종 시리즈를 모두 1회차씩은 직접 구현해봤으니 만족...ㅎㅎ
물론 중복되는 코드도 있어서 리팩토링이 필요하긴 하겠지만ㅎㅎ..