JavaScript 단일 연결 리스트

JavaScript로 연결 리스트를 구현해본다.

데이터(노드)의 추가와 삭제가 빈번하게 이루어질 경우 배열을 사용하는 것 보다 연결 리스트를 사용하는 것이 좋다. 연결 리스트의 특징은 head 포인터와 tail 포인터를 갖으며 각 노드는 다음 노드를 가리키는 포인터를 갖는다.

단일 연결 리스트 (Singly Linked List)

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

 클래스를 사용해서 Node를 만들고 생성자의 매개변수로 value를 받는다. this를 사용해서 생성한 Node의 value 값을 지정하고 다음 노드를 가리키는 포인터는 null로 생성한다.

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }

 단일 연결 클래스를 만든다. 생성과 동시에 head와 tail포인터를 null로 초기화한다.
아래에 있는 함수들은 모두 단일 연결 클래스 내부에 있는 함수들이다.

find(targetvalue)

  
  // 특정 값을 사용해서 원하는 노드를 찾는다.
  // 탐색하고자 하는 노드가 마지막에 있을 경우 선형 시간 복잡도를 갖는다.
  find (targetValue) {
    let currNode = this.head;
    let findNode = null;
    
    while (currNode !== null) {
      if (currNode.value === targetValue) {
        findNode = currNode;
      }
      currNode = currNode.next;
    }
    return findNode;
  }
    
    

 findNode는 특정 값(targetValue)이 연결 리스트에 존재하지 않을 경우 null을 반환하기 위해서 추가했다. while문을 사용해서 currNode가 null이 아닐 때까지 탐색을 하고 찾을 경우 해당 노드를 반환하고 찾지 못할 경우 null을 리턴한다.

값이 중복될 경우 가장 먼저 탐색되는 값을 리턴하는 문제가 있다.

append(newValue)

append(newValue) {
 const newNode = new Node(newValue); 
  if (this.head === null) {
    this.head = newNode;
    this.tail = newNode;
  } else {
   	this.tail.next = newNode;
    this.tail = newNode;
  }
}

 append함수는 newValue값을 갖고 새로운 노드를 생성한 다음 가장 마지막 노드에 추가한다. 만약 현재 head 포인터가 null이라는 것은 리스트가 비어있다는 뜻임으로 가장 첫번째 노드로 추가된다. 따라서 리스트의 head와 tail이 새로운 노드를 가리킨다.

insert(targetValue, newValue)

insert (targetValue, newValue) {
  const targetNode = this.find(targetValue);
  if (targetNode === null) {
    console.log("insert fail...");
  } else {
    const newNode = new Node(newValue);
    newNode.next = targetNode.next;
    targetNode.next = newNode;
  }
}

 insert 함수는 타겟 값을 갖는 리스트의 노드 뒤에 새로운 노드를 만들어서 추가한다. 우선 특정 값이 리스트에 있는지 탐색을 하고 없을 경우 insert faill을 알리고 함수는 종료된다.
만약 타겟 값을 갖고 있는 노드가 리스트에 존재한다면 새로운 노드를 만들고 새로운 노드의 다음 노드로 타겟 값의 다음 노드를 연결시키고 타겟 노드의 다음 노드는 새로운 노드가 되도록 연결시킨다.

remove(targetValue)

remove(targetValue) {
  if (this.find(targetValue) === null) {
    console.log("remove fail...");
  } else {
    let currNode = this.head;
    if (currNode.value === targetValue) {
      this.head = currNode.next;
    } else {
      while (currNode.next.value !== targetValue) {
        currNode = currNode.next;
      }
      if(currNode.next !== null) {
        currNode.next = currNode.next.next;
      }
    }
  }
}

 remove 함수 또한 기본적으로 find함수를 사용해서 targetValue를 갖는 노드를 탐색한다. 노드가 존재할 경우 두 가지 경우로 나누어지는데, 첫 번째 노드를 삭제하는 경우와 나머지 순서의 노드를 삭제하는 경우다. currNode는 리스트를 순회하면서 현재 노드를 의미하는데, 만약 첫 번째 노드를 삭제할 경우 간단하게 연결 리스트의 헤드 포인터를 다음 노드로 가리키면 된다.

 만약 첫 번째 노드가 아닐 경우 targetValue를 갖는 노드의 이전 노드를 찾아야 한다. targetValue를 갖는 노드가 아닌 그 노드의 이전 노드를 찾아야 하는 이유는 삭제하는 노드의 다음 노드를 이전 노드의 다음으로 만들어야 하기 때문이다. while문을 실행하면 현재 노드는 삭제하는 노드의 이전 노드가 된다. 그리고 나서 현재 노드의 다음 노드를 삭제하는 노드의 다음노드로 연결시키면 된다.

size()

size() {
  let currNode = this.head;
  let sizeCount = 0;
  
  while (currNode !== null) {
   	sizeCount += 1;
    currNode = currNode.next;
  }
  console.log(sizeCount);
}

 size 함수는 연결 리스트를 순회하면서 sizeCount 값을 증가시켜 계산한다.

size를 구할 때마다 탐색을 해야 한다...

따라서 노드를 추가하거나 삭제할 때 카운트를 하도록 수정해야 한다.

수정 및 완성본

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class SinglyLinkdedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.count = 0;
  }

  find(targetValue) {
    let currNode = this.head;
    let findNode = null;
    while (currNode !== null) {
      if (currNode.value === targetValue) {
        findNode = currNode;
      }
      currNode = currNode.next;
    }
    // 값이 중복일 경우??? 일단 중복은 없다고 생각함...
    return findNode;
  }

  append(newValue) {
    const newNode = new Node(newValue);
    if (this.head === null) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.count += 1;
  }

  insert(targetValue, newValue) {
    const targetNode = this.find(targetValue);
    if (targetNode === null) {
      console.log("insert fail...");
    } else {
      const newNode = new Node(newValue);
      newNode.next = targetNode.next;
      targetNode.next = newNode;
      this.count += 1;
    }
  }

  remove(targetValue) {
    // 값을 기준으로 리스트를 순회.
    // 리스트의 마지막 노드일 경우 -> 선택 노드의 앞 노드의 next를 null로 변경
    // 리스트의 처음 노드일 경우 -> 헤드 포인터 변경
    // 리스트의 중간 노드일 경우 -> 선택 노드의 앞 노드의 next를 선택 노드의 next로 변경
    // 리스트에 없는 값을 삭제하려고 할 경우. -> find함수 사용 find 함수의 시간복잡도를 생각하면 그리 좋은 방법은 아님...

    if (this.find(targetValue) === null) {
      console.log("remove fail...");
    } else {
      let currNode = this.head;
      if (currNode.value === targetValue) {
        this.head = currNode.next;
        this.count -= 1;
      } else {
        while (currNode.next.value !== targetValue) {
          currNode = currNode.next;
        }
        if (currNode.next !== null) {
          currNode.next = currNode.next.next;
          this.count -= 1;
        }
      }
    }
  }

  display() {
    let currNode = this.head;
    let displyString = "[";
    while (currNode !== null) {
      let addString = `${currNode.value}`;
      if (currNode.next !== null) {
        addString += `, `;
      }
      displyString += addString;
      currNode = currNode.next;
    }
    displyString += "]";
    console.log(displyString);
  }

  size() {
    console.log(this.count);
  }
}

만약 연결 리스트가 많아진다면?...

프로토 타입을 사용해보자!

프로토 타입을 사용한 결과

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.count = 0;
  }
}

SinglyLinkedList.prototype.find = function (targetValue) {
  let currNode = this.head;
  let findNode = null;
  while (currNode !== null) {
    if (currNode.value === targetValue) {
      findNode = currNode;
    }
    currNode = currNode.next;
  }
  // 값이 중복일 경우??? 일단 중복은 없다고 생각함...
  return findNode;
};

SinglyLinkedList.prototype.append = function (newValue) {
  const newNode = new Node(newValue);
  if (this.head === null) {
    this.head = newNode;
    this.tail = newNode;
  } else {
    this.tail.next = newNode;
    this.tail = newNode;
  }
  this.count += 1;
};

SinglyLinkedList.prototype.insert = function (targetValue, newValue) {
  const targetNode = this.find(targetValue);
  if (targetNode === null) {
    console.log("insert fail...");
  } else {
    const newNode = new Node(newValue);
    newNode.next = targetNode.next;
    targetNode.next = newNode;
    this.count += 1;
  }
};

SinglyLinkedList.prototype.remove = function (targetValue) {
  // 값을 기준으로 리스트를 순회.
  // 리스트의 마지막 노드일 경우 -> 선택 노드의 앞 노드의 next를 null로 변경
  // 리스트의 처음 노드일 경우 -> 헤드 포인터 변경
  // 리스트의 중간 노드일 경우 -> 선택 노드의 앞 노드의 next를 선택 노드의 next로 변경
  // 리스트에 없는 값을 삭제하려고 할 경우. -> find함수 사용 find 함수의 시간복잡도를 생각하면 그리 좋은 방법은 아님...

  if (this.find(targetValue) === null) {
    console.log("remove fail...");
  } else {
    let currNode = this.head;
    if (currNode.value === targetValue) {
      this.head = currNode.next;
      this.count -= 1;
    } else {
      while (currNode.next.value !== targetValue) {
        currNode = currNode.next;
      }
      if (currNode.next !== null) {
        currNode.next = currNode.next.next;
        this.count -= 1;
      }
    }
  }
};

SinglyLinkedList.prototype.display = function () {
  let currNode = this.head;
  let displyString = "[";
  while (currNode !== null) {
    let addString = `${currNode.value}`;
    if (currNode.next !== null) {
      addString += `, `;
    }
    displyString += addString;
    currNode = currNode.next;
  }
  displyString += "]";
  console.log(displyString);
};

SinglyLinkedList.prototype.size = function () {
  console.log(this.count);
};

const linkedList = new SinglyLinkedList();
const linkedList2 = new SinglyLinkedList();
const linkedList3 = new SinglyLinkedList();
const linkedList4 = new SinglyLinkedList();

linkedList.append(1);
linkedList.append(2);
linkedList.append(3);
linkedList.append(4);

linkedList2.append(1);
linkedList2.append(2);
linkedList2.append(3);
linkedList2.append(4);

linkedList3.append(1);
linkedList3.append(2);
linkedList3.append(3);
linkedList3.append(4);

linkedList4.append(1);
linkedList4.append(2);
linkedList4.append(3);
linkedList4.append(4);

console.log(linkedList, linkedList2, linkedList3, linkedList4);
linkedList.display();
linkedList2.display();
linkedList3.display();
linkedList4.display();

인스턴스가 생성될 때마다 공통으로 사용되는 함수들이 새로 생성되는 것이 아니라 프로토 타입에 있는 함수를 사용하게 됨으로 메모리 사용량을 줄일 수 있다.