[TIL][Data Structure] Linked List JS구현

김태수·2020년 10월 27일
0

datastructure

목록 보기
2/4


Data Structure 에서 Linked List 에 대하여 Java Script를 이용하여 구현해 보았다.
Linked List는 Single Linked List와 Double Linked List 두가지로 크게 나뉘는데,

Single Linked List의 경우

그림과 같이 리스트를 이루고있는 노드 하나에 해당 노드의 값과, 다음 노드에 대한 주소를
내포하고 있다. 그러나 이전 노드에 대한 정보는 갖고있지 않은데, 때문에 다음노드로만 이동할 수 있을뿐, 통상적인 방법으로는 이전노드로의 이동은 힘들다. 그때문에

Double Linked List의 구현 방법이 있는데,

리스트를 이루고있는 노드 하나에 해당 노드의 값과, 다음 노드에 대한 주소, 그리고
자신의 이전 노드에 대한 주소도 갖게된다. 이를 통해 자신의 다음노드와 이전노드로의 이동이 수월하며, Single Linked List 를 순회하는것 보다 시간복잡도를 적게 가져가나, 노드 하나당 가지고 있어야할 주소가 하나 더 늘어나기 때문에 공간복잡도는 약간 늘어나게 된다.

통상적으로 얘기하는 Linked List 는 Single Linked List 이며 앞으로 후술할 Linked List 역시
Single Linked List 이다.

Head & Tail

Linked List를 이루고있는 노드들중에 가장 첫번째의 노드를 head로 가르키고 있으며 다른 노드가 가장 첫번째자리에 새롭게 들어오게 될때, head의 자리를 승계받게 된다.
Tail 또한 마찬가지로 가장 마지막 노드를 가르키고 있으며, 리스트에 새로운 노드를 추가할 때는
보통 Tail에 노드를 달아주기 때문에 Tail의 경우 리스트의 길이가 바뀌면 계속해서 바뀌게 된다.

Linked List 구현

새로운 List 자체와, 리스트 안에 들어가게될 Node를 생성하는 클래스와 메소드를 구현하였다. 전체 코드와 핵심이라 생각되는 메소드에 대한 설명을 작성해 보았다.

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

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this._size = 0;
  }

  addToTail(value) {
    // 새 노드 생성
    let node = new Node(value);
    // 리스트가 비었을 경우 / 리스트에 기존 노드가 있을경우
    if(this.head === null) {
      this.head = node;
      this.tail = node;
      this._size ++;
    }
    else if(this.head !== null) {
      this.tail.next = node;
      this.tail = node;
      this._size ++;
    }
  }

  remove(value) {
    let preNode = this.head;
    let loopCount = this._size;
    while(loopCount > 0) {
      if(this.head.value === value) {
        this.head = this.head.next;
        this._size -= 1;
        break;
      }
      else if(preNode.next.value === value) {
        preNode.next.next = null;
        preNode.next = preNode.next.next;
        this._size -= 1;
        break;
      }
      else {
        loopCount -= 1;
        preNode = preNode.next;
      }
    }
  }

  getNodeAt(index) {
    if((index + 1) > this._size) {
      return undefined;
    }
    let head = this.head;
    for(let i = 0; i < index; i ++) {
      head = head.next;
    }
      return head;
  }

  contains(value) {
    if(this.head.value === value) {
      return true;
    }
    let node = this.head.next;
    for(let i = 1; i < this._size; i ++) {
      if(node.value === value) {
        return true;
      }
      else {
        node = node.next;
      }
    }
    return false;
  }

  indexOf(value) {
    if(this.head.value === value) {
      return 0;
    }
    let node = this.head.next;
    let index = 1;
    for(let i = 1; i < this._size; i ++) {
      if(node.value === value) {
        return index;
      }
      else {
        node = node.next;
        index += 1;
      }
    }
    return -1;
  }

  size() {
    return this._size;
  }
}

주어진 값을 가진 노드를 리스트 마지막에 추가하는 메소드

addToTail(value) {
    // 새 노드 생성
    let node = new Node(value);
    // 리스트가 비었을 경우 / 리스트에 기존 노드가 있을경우
    if(this.head === null) {
      this.head = node;
      this.tail = node;
      this._size ++;
    }
    else if(this.head !== null) {
      this.tail.next = node;
      this.tail = node;
      this._size ++;
    }
  }

생성자를 이용하여 값(인자)를 내포한 새로운 노드를 만들어서
경우에 따라 리스트의 head, tail, size 또는 이전 노드의 next 속성등을 수정해주었다.

주어진 값을 가진 노드를 리스트에서 삭제하는 메소드

remove(value) {
    let preNode = this.head;
    let loopCount = this._size;
    while(loopCount > 0) {
      if(this.head.value === value) {
        this.head = this.head.next;
        this._size -= 1;
        break;
      }
      else if(preNode.next.value === value) {
        preNode.next.next = null;
        preNode.next = preNode.next.next;
        this._size -= 1;
        break;
      }
      else {
        loopCount -= 1;
        preNode = preNode.next;
      }
    }
  }

루프를 통해 리스트를 처음부터 조회하여, 해당 value를 포함한 노드를 찾아 삭제 후,
삭제된 노드의 이전 노드의 next 속성을 통해 삭제자와의 연결을 다음 노드로 변경해주었다.

주어진 값을 가진 노드를 조회해 Boolean으로 반환하는 메소드

 remove(value) {
    let preNode = this.head;
    let loopCount = this._size;
    while(loopCount > 0) {
      if(this.head.value === value) {
        this.head = this.head.next;
        this._size -= 1;
        break;
      }
      else if(preNode.next.value === value) {
        preNode.next.next = null;
        preNode.next = preNode.next.next;
        this._size -= 1;
        break;
      }
      else {
        loopCount -= 1;
        preNode = preNode.next;
      }
    }
  }

삭제와 마찬가지로 루프로 조회하여 참과 거짓으로 반환해 주었다.

Linked List를 구현해 보며..

Linked List의 전체적인 개념은 chain 방식이며, 노드와 노드를 연결하는 next 속성이
중요하다는 것이 느껴졌다. 삽입, 삭제 등의 행동을 수행할 때 마다 해당 노드와 이전노드, 이후노드 간의 연결을 수정해주는것 만으로 해당 삭제대상 노드는 리스트에서 퇴출되어 더이상 삭제대상 노드를 참조할 수 있는 방법이 없어서 garbage 처리되어 버린다.
Linked List에 대한 개념은 현재로써 이정도로 괜찮다고 여겨진다.. 그래도 추후에 좀 더 공부 해보면 좋을것 같다!!

profile
개발학습 일기

0개의 댓글