ES6 자료구조 연결리스트(LinkedList) 구현하기(이중연결리스트, 원형연결리스트) 그리고 의문점..

ES6로 연결리스트(LinkedList) 만들기

연결리스트라는 자료구조를 구현해본다.

기존 배열은 단점이 있다. 자바스크립트에서는 아니지만 다른 언어에서 배열은 길이를 자유롭게 늘리고 줄이기 어렵고, 자바스크립트에서 배열은 객체이므로 효율이 약간 떨어질 수 있다고 한다.

(왜 객체라는 이유로 효율이 떨어지는지는 찾아보았는데 잘 안나와서 찾아보는 중이다... 알고 계신분이 있다면 댓글로 도움을 주셨으면 좋겠다.)

따라서 처리속도가 빠른 것을 원한다면 배열 대신 연결리스트를 사용하면 조금더 성능이 좋아질 때가 있다. 하지만 임의의 접근(index를 통한 접근)을 지원하지 않으므로 접근이 잦은 경우에는 배열을 쓰는 것이 좋다.

---

연결리스트는 어떤 object를 갖는 Node를 담고 있고 연결이라는 단어 그대로 next 변수(포인터 역할)로 다음에 어떤 Node를 가리키는지를 나타낸다.

따라서 접근할 때 next를 통해서 다음다음으로 넘어가면서 접근해야한다.

---

class Node{
  constructor(element){
    this.element = element;
    this.next = null;
  }
}
class LinkedList{
  constructor(){
    this.head = new Node("head");
  }
    find(item){
      let currNode = this.head;
      while(currNode.element != item){
        currNode = currNode.next;
      }
      return currNode;
    }
    insert(newElement, item){
      let newNode = new Node(newElement);
      let current = this.find(item);
      newNode.next = current.next;
      current.next = newNode;
    }
    display(){
      let currNode = this.head;
      while(!(currNode.next == null)){
        console.log(currNode.next.element);
        currNode = currNode.next;
      }
    }
    findPrevious(item){
      let currNode = this.head;
      //다음 노드가 존재하면서 다음노드의 아이템이 
      while(!(currNode.next == null) && (currNode.next.element != item)){
        currNode = currNode.next;
      }
      return currNode;
    }
    remove(item){
      let prevNode = this.findPrevious(item);
      if(!(prevNode.next == null)){
        prevNode.next = prevNode.next.next;
      }
    }
}
 
const ll = new LinkedList();
ll.insert("Seoul","head");//head->Seoul
ll.insert("Busan","Seoul");//head->Seoul->Busan
ll.insert("Daegu","Seoul");//head->Seoul->Daegu->Busan
ll.insert("Incheon","Busan");//head->Seoul->Daegu->Busan->Incheon
ll.display();//head->Seoul->Daegu->Busan->Incheon
ll.remove("Busan");
ll.display();//head->Seoul->Daegu->Incheon

굉장히 심플한 자바스크립트 연결리스트다.

기본적으로 Node를 만들고, 그 Node집합을 관리하는 LinkedList를 만든다.

노드의 시작하는 부분을 head라는 노드를 LinkedList가 갖고 있는 구조다.

find()메서드는 head노드부터 차례로 해당 item을 검색하면서 찾고 찾으면 해당 노드를 리턴해준다.

insert()메서드는 find()메서드로 찾은 노드 뒤에다가 새로운노드(newNode)를 연결한다.

만약 find()에서 해당 노드를 못찾으면 제일 뒤에 노드가 가리키고 있는 next, 즉 null임을 인지하고 제일 뒤에 노드를 연결한다.

위 연결리스트는 중복을 허용하기 때문에 중복된 값을 넣다보면 head에서 처음 찾아낸 Node뒤에 연결하므로 에러가 있다...

remove()메서드는 삭제할 노드 바로 직전에 있는 노드를 찾아 연결을 끊어버리는 것으로 삭제처리를 한다.

---

양방향 연결 리스트

class Node{
  constructor(element){
    this.element = element;
    this.next = null;
    this.prev = null;//추가
  }
}
class LinkedList{
  constructor(){
    this.head = new Node("head");
  }
    find(item){
      let currNode = this.head;
      while(currNode.element != item){
        currNode = currNode.next;
      }
      return currNode;
    }
    insert(newElement, item){
      let newNode = new Node(newElement);
      let current = this.find(item);
      if(current.next == null){
        newNode.next = null;
        newNode.prev = current;
        current.next = newNode;
      }
      else{
        newNode.next = current.next;
        newNode.prev = current;
        current.next.prev = newNode;
        current.next = newNode;
      }
    }
    display(){
      let currNode = this.head;
      while(!(currNode.next == null)){
        console.log(currNode.next.element);
        currNode = currNode.next;
      }
    }
    /*findPrevious(item){
      let currNode = this.head;
      //다음 노드가 존재하면서 다음노드의 아이템이 
      while(!(currNode.next == null) && (currNode.next.element != item)){
        currNode = currNode.next;
      }
      return currNode;
    }*/
    remove(item){
      let currNode = this.find(item);
      if(!(currNode.next == null)){
        //자신 노드가 삭제되기 위해 앞뒤 노드를 연결시켜주는 과정
        currNode.prev.next = currNode.next;
        currNode.next.prev = currNode.prev;
        currNode.next = null;
        currNode.prev = null;
      }
    }
    findLast(){
      let currNode = this.head;
      while(!(currNode.next == null)){
        currNode = currNode.next;
      }
      return currNode;
    }
    dispReverse(){
      let currNode = this.head;
      currNode = this.findLast();
      while(!(currNode.prev == null)){
        console.log(currNode.element);
        currNode = currNode.prev;
      }
    }
}
 
const ll = new LinkedList();
ll.insert("Seoul","head");//head->Seoul
ll.insert("Busan","Seoul");//head->Seoul->Busan
ll.insert("Daegu","Seoul");//head->Seoul->Daegu->Busan
ll.insert("Incheon","Busan");//head->Seoul->Daegu->Busan->Incheon
ll.display();//Seoul->Daegu->Busan->Incheon
ll.remove("Busan");
ll.display();//Seoul->Daegu->Incheon
ll.dispReverse();//Incheon->Daegu->Seoul

기본적인 연결리스트는 기존의 노드들이 next만을 이용해서 한쪽방향으로만 접근했다면,

양방향 연결리스트는 노드가 앞(prev), 뒤(next)로 접근할 수 있게 하는 연결리스트다.

수정된 메서드(Node클래스, insert(), remove())와 추가된 메서드(findLast(), dispReverse())가 있다.

insert()와 remove()메서드를 자세히 봐야한다.

책에서 작성한 코드와는 다르게 내 맘대로 테스트를 해보니 뭔가 이상했다. 이상한 점은 insert()코드에서 현재 노드의 next 노드가 있을 때 다음 노드의 prev가 새로운 노드를 가리키게 해야하는데 그 코드가 없었다.

다시 한 번 공부할 때 역시 insert()와 remove()코드를 잘 봐야할 것이다.

---

원형 연결 리스트 

class Node{
  constructor(element){
    this.element = element;
    this.next = null;
    this.prev = null;//추가
  }
}
class LinkedList{
  constructor(){
    this.head = new Node("head");
    this.head.next = this.head;
  }
    find(item){
      let currNode = this.head;
      while(currNode.element != item){
        currNode = currNode.next;
      }
      return currNode;
    }
    insert(newElement, item){
      let newNode = new Node(newElement);
      let current = this.find(item);
      if(current.next == null){
        newNode.next = null;
        newNode.prev = current;
        current.next = newNode;
      }
      else{
        newNode.next = current.next;
        newNode.prev = current;
        current.next.prev = newNode;
        current.next = newNode;
      }
    }
    display(){
      let currNode = this.head;
      while(!(currNode.next == null) && !(currNode.next.element == "head")){
        console.log(currNode.next.element);
        currNode = currNode.next;
      }
    }
    remove(item){
      let currNode = this.find(item);
      if(!(currNode.next == null)){
        //자신 노드가 삭제되기 위해 앞뒤 노드를 연결시켜주는 과정
        currNode.prev.next = currNode.next;
        currNode.next.prev = currNode.prev;
        currNode.next = null;
        currNode.prev = null;
      }
    }
}
 
const ll = new LinkedList();
ll.insert("Seoul","head");//head->Seoul
ll.insert("Busan","Seoul");//head->Seoul->Busan
ll.insert("Daegu","Seoul");//head->Seoul->Daegu->Busan
ll.insert("Incheon","Busan");//head->Seoul->Daegu->Busan->Incheon
ll.display();//Seoul->Daegu->Busan->Incheon
ll.remove("Busan");
ll.display();//Seoul->Daegu->Incheon
console.log(ll.head.prev.element);//Incheon
console.log(ll.head.next.element);//Seoul

원형 연결리스트는 노드의 next가 null을 가리키는 것이 아니라 head노드를 다시 가리켜서

순환 구조를 갖는 연결 리스트다.

일반 연결리스트에서 변경되는 사항은 처음 head노드의 next가 head를 가리키게 초기화 시키는 것이다.

* 위 코드는 버그가 있을 수 있다. 심각하게 고민하지 않고 작성했기 때문이다. (댓글로 알려주시면 감사하겠습니다.)

참고 도서 : DataStructures & Algorithms with javascript