자바스크립트 원형 연결리스트 정리

 

// Node(): data와 point를 가지고 있는 객체
function Node(data) {
  this.data = data;
  this.next = null;
}

// CircularLinkedList(): head와 length를 가지고 있는 객체
function CircularLinkedList() {
  this.head = null;
  this.length = 0;
}

// size(): 연결 리스트 내 노드 개수 확인
CircularLinkedList.prototype.size = function () {
  return this.length;
};

// isEmpty(): 객체 내 노드 존재 여부 파악
CircularLinkedList.prototype.isEmpty = function () {
  return this.length === 0;
};

- 원형연결리스트는 일반 연결리스트와 거의 비슷하다.

Node() : data와 point를 가지고 있는 객체

CircularLinkedList() : head와 length를 가지고 있는 객체

CircularLinkedList.size() - 노드 개수 확인

CircularLinkedList.isEmpty() - 비어있는지 확인 / true, false 반환

 

4가지는 똑같고 나머지 메서드에서 노드를 출력하거나 index를 움직일때 다르게 코드를 짜야했다.

연결리스트는 끝부분이 null로 끝나지만 원형연결리스트는 마지막이 첫부분이 head를 가르킨다.

 

 

CircularLinkedList.printNode() - 노드 출력

// 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");
};

- 노드를 출력할때는 무한반복이 되기 때문에 편의상 끝부분을 null로 표시 하였다. null로 나오지만 가르키고 잇는 것은 head이다.

 

 

---

CircularLinkedList.append() - 연결리스트 가장 끝에 노드 추가

// append(): 연결 리스트 가장 끝에 노드 추가
CircularLinkedList.prototype.append = function (value) {
  let node = new Node(value),
    current = this.head;

  if (this.head === null) { // this.head가 null이면 아무것도 없기 때문에 head에 node를 넣어준다.
    this.head = node;
  } else {
    while (current.next != this.head) { // 다시 첫 head까지 while을 돌면서 next로 움직인다.
      current = current.next;
    }
    current.next = node;
  }
  node.next = this.head; // 마지막 node.next는 null이 아니라 head를 연결해준다.
  this.length++;
};

- 일반 연결리스트와 다른점은 끝 노드 부분에서 null이 아닌 첫 head를 가르킨다.

원형이 때문에  null이 없이 계속 연결되어있다.

---

CircularLinkedList.insert() : position 위치에 노드 추가, position이 없으면 앞으로 추가

CircularLinkedList.prototype.insert = function (value, position = 0) {
  if (position < 0 || position > this.length) {
    //position이 음수거나, this.length 길이보다 크면 false
    return false;
  }
  let node = new Node(value),
    current = this.head,
    index = 0,
    prev;

  if (position === 0) {
    // position이 0이면 첫번째부분에 추가
    node.next = current; // node.next에 current(this.head)

    if (this.isEmpty()) {
      // 만약 이 객체가 비어있으면?
      current = node; // current(this.head)에 node 추가
    } else {
      // 값이 비어있지 않고 값이 있다면?
      while (current.next != this.head) {
        // currnt.next로 this.head를 만날때까지
        current = current.next; // current에 current.next를 넣어준다.
      }
    }
    this.head = node;
    current.next = this.head; // 마지막에는 null이 아닌 첫 this.head(node)
  } else {
    // position이 0이 아니라면
    while (index++ < position) {
      // index를 증가시키면서 position값과 같을떄까지
      prev = current;
      current = current.next; // 입력받은 index를 찾는다.
    }

    node.next = current; // node.next에는 current를 넣어주고.
    prev.next = node; // prev.next에 node를 넣어줘서 완성 시킨다.

    if (node.next === null) {
      // 만약 넣은 위치가 끝 위치면?
      node.next = this.head; // node값을 this.head를 넣어줘서 circuler형태로 만들어준다.
    }
  }

  this.length++;

  return true;
};

 

 

---

 

CircularLinkedList.remove()   / value 데이터를 찾아서 노드 삭제

// remove() : value 데이터를 찾아 노드 삭제
CircularLinkedList.prototype.remove = function (value) {
  let current = this.head,
    prev = current,
    data;

  while (current.data != value && current.next != this.head) {
    // 순회하며 prev와 current값을 계속 이동시킨다.
    prev = current;
    current = current.next;
  }
  if (current.data != value) {
    // value와 같지 않으면 찾지 못한 것이므로 null을 리턴
    return null;
  }

  data = current.data; // 현재 data부분을 찾은 데이터를 임시저장
  if (current == this.head) {
    // 들어온 value가 첫번째 요소라면
    while (current.next != this.head) {
      // 끝쪽에 있는 node를 찾을때까지 while을 돌면서
      current = current.next;
    }
    this.head = this.head.next; // 끝쪽에 있는 node를 찾게 되면
    current.next = this.head; // 삭제한 노드를 head로 연결시킨다.
  } else {
    prev.next = current.next; // 중간에 있는 node라면 next만 바꿔준다.
  }

  this.length--;

  return data;
};

 

---

CircularLinkedList.removeAt() // position 위치의 노드를 삭제한다. 

//removeAt() : position 위치 노드 삭제
CircularLinkedList.prototype.removeAt = function (position = 0) {
  if (position < 0 || position >= this.length) {
    // positin이 음수이거나 length보다 크거나 같은값이면 null 리턴
    return null;
  }
  let current = this.head,
    index = 0,
    prev,
    data;

  if (position === 0) {
    // position이 0이면 current.data를 data에 넣어주고
    data = current.data;

    while (current.next != this.head) {
      // 끝에 있는 node로 이동시킨다.
      current = current.next;
    }

    this.head = this.head.next; // head.next를 head로 옮겨주고
    current.next = this.head; // 기존에 있던 current.next값에도 head값을 넣어준다.
  } else {
    while (index++ < position) {
      // index를 증가시키면서 position값 위치까지 이동시킨다.
      prev = current;
      current = current.next;
    }
    data = current.data; // 현재 삭제될 data를 저장시키고
    prev.next = current.next; // prev.next에 current.next를 연결 시킨다.
  }
  this.length--;
  return data;
};

CircularLinkedList.indexOf // value값을 갖는 노드 위치를 반환

// indexOf() : value 값을 갖는 노드 위치 반환
CircularLinkedList.prototype.indexOf = function (value) {
  let current = this.head,
    index = 0;

  do {
    // 첫부분에서 head를 만나기 때문에 무조건 한번은 이동을 할 수 있게 do while을 사용
    if (current.data === value) {
      // current.data가 value일 경우
      return index;
    }
    index++;
    current = current.next; // index를 올려주면서 next로 옮겨준다.
  } while (current != this.head); // head를 만날떄까지
  {
    return -1;
  }
};

 

 

 

remove2 // indexOf + remoteAt // value데이터를 찾아서 노드를 삭제하는 다른 방법

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