자바스크립트 연결리스트(Linked List)/이중연결(Double)

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

HEAD ->  Node ->  Node ->  Node ->  null

 

 

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

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

 

---

 

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

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

 

---

 

LinkedList.size() - 노드 개수 확인 /

 

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

 

---

 

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

 

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

 

---

 

LinkedList.printNode() - 노드 출력

// printNode(): 노드 출력
LinkedList.prototype.printNode = function () {
  for (let node = this.head; node != null; node = node.next) {
    process.stdout.write(`${node.data} -> `);
  }
  console.log("null");
}; // 1 -> 2 -> 3 -> 4 -> null

- 콘솔에 정리해서 출력!

 

---

 

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

// append(): 연결 리스트 가장 끝에 노드 추가
LinkedList.prototype.append = function (value) {
  let node = new Node(value), // 새로은 node 변수에 value값을 넣어준다.
  current = this.head; // current변수에는 head를 지정한다.

  if (this.head === null) { // 만약 velue의 head가 비어있으면
    this.head = node; // 첫 head에 node를 넣어준다.
  } else {
    while (current.next != null) { // 포인터의 next가 비어있지 않으면
      current = current.next; // 새로운 current의 next를 계속 넣어준다.
    }
    current.next = node; // 끝지점을 찾게 되면 마지막에는 node를 넣고 끝낸다.
  }
  this.length++; // 새로 추가된 length값을 업데이트한다.
};

ll.append(1);
ll.append(2);
ll.append(3);
ll.append(4);
ll.printNode(); // 1 -> 2 -> 3 -> 4 -> null

- 자동으로 노드를 추가할 수 있는 함수.

 

---

 

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

// insert(): position 위치에 노드 추가
LinkedList.prototype.insert = function (value, position = 0) {
  if (position < 0 || position > this.length) { //만약 position이 음수이거나 length길이보다 크면 false를 반환
    return false;
  }

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

  if (position === 0) { // position이 0이면 head를 value에 연결하고 .next를 처음에 있던 node로 연결한다.
    node.next = current;
    this.head = node;
  } else {
    while (index++ < position) { // 만약 0이 아니면 index를 position길이만큼 증가시키면서 c를 .next로 옮기고 p는 c를 따라가면서 찾는 position값 까지 이동한다.
      prev = current;
      current = current.next;
    }
    node.next = current; // 그리고 position위치에서 value node를 추가한다.
    prev.next = node;
  }
  this.length++;

  return true;
};

- position을 입력하게 되면 while문에서  index 0부터 시작해서 입력한 position 값만큼 while문이 돌고 index++이 position과 같은 값이 되면 멈춘다.

 

---

---

 

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

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

  while (current.data != value && current.next != null) {
    // value데이터가 현재 있거나 head.next가 null이면 실행
    prev = current; // prev는 head / current가 움직일때마다 prev도 같이 움직인다. current가 같은 값을 찾을때까지
    current = current.next; // current는 next가 가리키고 있는 다음 node로 찾을 때까지 이동
  }

  if (current.data != value) {
    // value 데이터가 없으면 null을 반환
    return null;
  }

  if (current === this.head) {
    // value 같은 값을 만나게 되면
    this.head = current.next; // head가 가리키고 있는 첫 노드가 맞으면 다음 next로 연결 아니면 밑에!
  } else {
    prev.next = current.next; // 같은 값은 넘기고 current.next의 노드에 연결한다.
  }

  this.length--;

  return current.data;
};

- 실행 단계

- value가 들어오면 while문을 먼저 실행시킨다. 여기서 value 데이터가 현재 head.data에 없고 .next에 null이 있을 때까지 돌아봤을 때 없을때까지 우선 돈다.

- 그렇게 while문을 지나서 if에서 c.data에 value가 없으면 null을 반환한다.( node에 없는 값이면 null 반환)

- 만약 있는 값이면 while 문에서 있는 node까지 c.next로 옮기고 그 c를 따라 p도 같이 따라가며 찾게된다.

- 그 값을 찾았으면 두번째 if문에서 있는 값을 없애고 그사이에 다른 값으로 연결이 된다.

- 마지막으로 length값을 빼주고 끝난다.

 

---

 

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

// removeAt(): position 위치 노드 삭제
LinkedList.prototype.removeAt = function (position = 0) {
  if (position < 0 || position >= this.length) { //position이 음수이거나, Head의 length보다 크거나 같을때는 null
    return null;
  }

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

  if (position === 0) { //position이 0이면 head의 0index에 next로 연결
    this.head = current.next;
  } else {
    while (index++ < position) {//while문을 돌면서 입력 값의 position만큼 index를 이동
      prev = current;
      current = current.next;
    }
    prev.next = current.next; //입력한 position의 index가 되었을 때 입력한 position을 없애고 다음 인덱스와 연결.
  }

  this.length--;
  return current.data;
};

- 실행단계

- value값으로 position위치(index)를 받는다.

- 첫 if 에서 position값이 음수이거나, length길이보다 크거나 같으면 null을 반환한다.(index값이기 때문에 0부터 시작하기 때문에 값이 같으면 length의 길이보다 큰걸 알 수 있다.)

- 두번째 if 에서 position이 0이라면 바로 첫 head가 가르키고 있는 node를 삭제하고 .next의 node에 연결한다.

- 만약 첫번째에서 없다면 while을 돈다. while은 index값을 증가시키면서 찾고자하는 position값 까지 돈다.

- 그렇게 입력한 position값이 되었을 때 입력한 position값을 없애고 다음 node와 연결한다.

- length는 증감시키고 리턴시킨다.

 

---

 

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

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

  while (current != null) { // head가 null이면 while문이 멈춘다.
    if (current.data === value) { // value값이 head가 연결된 첫 노드인지 확인 맞으면 if이 실행되서 index 0 반환!
      return index;
    }

    index++; // if문에서 false가 되면 index를 증가시키면서
    current = current.next; // 다음 노드와 value값이 맞는지 확인해나간다.
  }

  return -1; // 만약 value값을 가진 node가 없으면 -1반환
};

- value값을 입력받고 index를 반환시킨다.

- 첫 while 에서 head가 null이될때까지 실행한다.

- if 에서 head에 연결 된 첫 node 값이 value가 맞으면 첫번째 index이기 때문에 0을 반환한다.

- 첫번째 index가 아니면 index를 증가시키면서 다음 노드와 value값이 맞는지 확인을 한다.

 

 

 

 

---

---

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

// remove2(): indexOf + remoteAt = remove
LinkedList.prototype.remove_2 = function (value) {
  let index = this.indexOf(value);
  return this.removeAt(index);
};

 

---

---

이중 연결 리스트 (Double Linked List)

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

 

DoubleNode() : data와 point를 가지고 있는 객체 / point에 next외에 prev가 추가되었다.

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

- 이중연결리스트는 node에서 next와 prev를가지고 있다.

- 하나만 연결하는 연결리스트와는 달리 next에만 연결하는게 아니라 prev를 같이 연결한다.

 

---

 

DoubleLinkedList() : head,tailㅡ length를 가지고 있는 객체

// LinkedList(): head, tail과 length를 가지고 있는 객체
function DoubleLinkedList() {
  this.head = null;
  this.tail = null;
  this.length = 0;
}

- head와 next를 연결했다면

- prev는 tail를 연결하는 속성이다.

 

---

DoubleLinkedList.size() - 노드 개수 확인 /

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

- 노드의 개수를 확인하는 메서드

---

 

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

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

- 객체 내 노드 존재를 true, false로 반환한다.

 

---

 

DoubelLinkedList.printNode() - 노드 출력

// printNode() : 노드 정방향 출력
DoubleLinkedList.prototype.printNode = function () {
  process.stdout.write("head- > ");
  for (let node = this.head; node != null; node = node.next) {
    process.stdout.write(`${node.data} -> `);
  }
  console.log("null");
};

- 노드를 출력하는데 정방향 head -> next 로 출력하여 보여준다.

---

 

DoubelLinkedList.printNodeInverse() - 노드 출력

// printNodeInverse() : 노드 역방향 출력
DoubleLinkedList.prototype.printNodeInverse = function () {
  let temp = [];

  process.stdout.write("null <- ");
  for (let node = this.tail; node != null; node = node.prev) {
    temp.push(node.data);
  }
  for (let i = temp.length - 1; i >= 0; i--) {
    process.stdout.write(`${temp[i]} <- `);
  }
  console.log("tail");
};

- 노드를 출력하는데 역방향으로 tail <- prev 로 출력하여 보여준다.

 

---

 

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

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

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

  this.length++;
};

- 연결리스트 끝쪽으로 노드를 추가시키는 메서드이다.

- 코드를 살펴보면 새로운 노드가 들어오게 되면 head가 널일때 head와 tail을 연결한다.

- head가 null이 아니면 head.tail.next에 연결시키고 node.prev에 tail을 연결시킨다. 그리고 tail을 node로 연결한다.

 

---

 

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

// insert(): position 위치에 노드 추가
DoubleLinkedList.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) {
    if (this.head === null) {
      this.head = node;
      this.tail = node;
    } else {
      node.next = current;
      current.prev = node;
      this.head = node;
    }
  } else if (position === this.length) {
    current = this.tail;
    current.next = node;
    node.prev = current;
    this.tail = node;
  } else {
    while (index++ < position) {
      prev = current;
      current = current.next;
    }
    node.next = current;
    prev.next = node;

    current.prev = node;
    node.prev = prev;
  }

  this.length++;

  return true;
};

- position index값을 같이 입력해서 원하는 위치에 노드를 추가할 수 있다.

- position을 입력하지않고 value값만 입력하게 되면 index는 0으로 앞에 추가한다.

 

---

 

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

// remove(): value 데이터를 찾아 노드 삭제
DoubleLinkedList.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;
    if (this.length === 1) this.tail = null;
    else this.head.prev = null;
  } else if (current === this.tail) {
    this.tail = current.prev;
    this.tail.next = null;
  } else {
    prev.next = current.next;
    current.next.prev = prev;
  }
  this.length++;

  return current.data;
};

- value를 입력해서 데이터를 찾아서 삭제하는 메서드이다.

 

 

 

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

//removeAt(): position 위치 노드 삭제
DoubleLinkedList.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;
    if (this.length === 1) this.tail = null;
    else this.head.prev = null;
  } else if (position === this.length - 1) {
    current = this.tail;
    this.tail = current.prev;
    this.tail.next = null;
  } else {
    while (index++ < position) {
      prev = current;
      current = current.next;
    }
    prev.next = current.next;
    current.next.prev = prev;
  }
  this.length--;

  return current.data;
};

- position index위치를 입력해서 노드를 삭제시키는 메서드이다.

 

---

 

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

// indexOf: value 값을 갖는 노드 위치 반환
DoubleLinkedList.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;
};

- 원하는 value값으로 노드의 위치를 알수있는 메서드이다.

 

 

 

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

// remove2(): indexOf + removeAt = remove
DoubleLinkedList.prototype.remove_2 = function (value) {
  let index = this.indexOf(value);
  return this.removeAt(index);
};