[JavaScript] List - Linked List(연결 리스트)

  리스트 자료구조는 데이터를 나란히 저장하며 중복된 데이터 또한 저장이 가능하다. 리스트 자료구조는 구현방법에 따라 Array List(배열 리스트)와 Linked List(연결 리스트)로 나눌 수 있다.

 

  자바스크립트의 배열은 배열의 크기를 데이터 추가/제거와 동시에 자동적으로 정의가 된다. 하지만 c언어, java 등과 같은 언어들은 배열의 크기가 자동적으로 늘어나거나 줄어들게 하는 기능이 없기 때문에 배열을 사용하는 범위가 한정되어 있다. 따라서 노드라는 개념으로 구조체들을 서로 연결하는 리스트 개념을 만들어 활용하는 것이 효율적이다.

 

 

Array List(배열 리스트)의 개념

Array

배열 리스트는 어떤 언어에서도 기본적으로 내장된 데이터 타입이다. 따라서 가장 사용하기 쉽다. 물리적으로 고정되어 있다고 볼수있는 특징을 가지고 있다.

 

배열 리스트의 장점으로는 앞에서 서술한것과 같이 간단하고 사용하기가 쉽다는 것이다. 또한 데이터 참조가 쉽고 인덱스 값 기준으로 어디든 한번에 찾을수 있다는 것이다.

 

배열 리스트의 단점은 고정된 크기이다. 배열의 크기를 초기에 결정지어 놓으면 변경이 불가능하다. (자바스크립트는 예외적으로 데이터 추가/제거시 자동적으로 크기가 변한다.) 또한 배열의 처음, 중간에 데이터를 넣고 빼려면 그 뒤에 있는 모든 데이터들을 옮겨야해서 연산의 횟수가 증가하여 시간복잡도가 증가한다.

 

 

Linked List(연결 리스트)의 개념

Linked List

node는 Data와 다음 Data가 무엇인지 저장되어 있는 Link정보를 가지고 있는 구조체이다. 

 

연결 리스트의 장점은 데이터를 추가/제거할 때 시간복잡도가 증가하지 않는다는 것이다. 데이터들이 고정되어 있지 않고 link정보로 다음 데이터를 정하기 때문에 데이터 추가/제거시 굉장히 효율적이라고 할 수 있다.

 

연결 리스트의 단점은 배열 리스트에 비해 데이터 탐색 속도가 많이 떨어진다. 어디에서든 데이터 인덱스 값을 기준으로 바로 찾을 수 있는 배열 리스트와 달리 순차적으로 탐색하지 않으면 특정 데이터에 접근할 수 없다.

 

연결리스트의 특징은 다음과 같다.

-연속되는 데이터들이 포인터로 연결되어 있다.

-마지막 항목은 null을 가르킨다.

-연산에 따라 크기가 늘어나거나 작아질 수 있다.

-메모리 공간을 낭비하지 않고 효율적으로 사용할 수 있다.

 

 

 

JavaScript를 이용한 Linked List(연결 리스트) 구현

 

1. 클래스 생성자를 통해 data와 link의 뼈대를 잡아준다.

class nodeType {
  constructor(item) {
    this.data = item;
    this.link = null;
  }
}

 

2. 클래스 안에 연결 리스트에 필요한 메서드들을 정의해준다.

 

firstNodeIn()

  firstNodeIn(item) {
    let newNode = new nodeType(item);
    if(this.link === null) {
        this.link = newNode;
    } else{
        newNode.link = this.link;
        this.link = newNode;
    }
  }

 

firstNodeOut()

  firstNodeOut() {
    if(this.link === null) return null;

    const tmp = this.link;
    this.link = tmp.link;
  }

 

lastNodeIn()

  lastNodeIn(item) {
    let newNode = new nodeType(item);
    let p = this;
    while(p.link !== null) {
      p = p.link;
    }
    p.link = newNode;
  }

p는 this 로 기준이 되는 노드(현재 노드)를 가르킨다.

 

 

lastNodeOut()

  lastNodeOut() {
    if(this.link === null) return null;

    let p = this;
    while(p.link.link !== null) {
      p = p.link;
    }
    p.link = null;
  }

p.link.link는 p의 다음 노드의 링크를 나타내고 p.link.link !== null 을 통해 다음 노드가 있는지 확인하는 것이다. p.link.link가 있다면 p.link = null 로 현재 노드 p에서 바로 link를 끊어주어 삭제가 되는 것이다.

 

lastOutNode() 설명

 

print()

  print() {
    let string = '';
    for(let p = this; p !== null; p = p.link) {
      string += `${p.data} | `;
    }
    string += `NULL`;
    console.log(string)
  }

 

node의 데이터들 확인

let head = new nodeType("head");
head.firstInNode(1); // head | 1 | null
head.firstInNode(2); // head | 2 | 1 | null
head.firstInNode(3); // head | 3 | 2 | 1 | null
head.firstInNode(4); // head | 4 | 3 | 2 | 1 | null
head.firstInNode(5); // head | 5 | 4 | 3 | 2 | 1 | null
head.firstInNode(6); // head | 6 | 5 | 4 | 3 | 2 | 1 | null
head.firstInNode(7); // head | 7 | 6 | 5 | 4 | 3 | 2 | 1 | null
head.firstInNode(8); // head | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | null
head.lastInNode(0); //  head | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | null
head.firstOutNode(); //  head | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | null
head.lastOutNode();  //  head | 7 | 6 | 5 | 4 | 3 | 2 | 1 | null
console.log(head)
// nodeType {     
//  data: 'head',
//  link: nodeType { data: 7, link: nodeType { data: 6, link: [nodeType] } }
// }
head.print(); // head | 7 | 6 | 5 | 4 | 3 | 2 | 1 | NULL

 

 

3. 전체 코드

class nodeType {
  constructor(item) {
    this.data = item;
    this.link = null;
  }

  firstNodeIn(item) {
    let newNode = new nodeType(item);
    if(this.link === null) {
        this.link = newNode;
    } else{
        newNode.link = this.link;
        this.link = newNode;
    }
  }

  firstNodeOut() {
    if(this.link === null) return null;

    const tmp = this.link;
    this.link = tmp.link;
  }

  lastNodeIn(item) {
    let newNode = new nodeType(item);
    let p = this;
    while(p.link !== null) {
      p = p.link;
    }
    p.link = newNode;
  }

  lastNodeOut() {
    if(this.link === null) return null;

    let p = this;
    while(p.link.link !== null) {
      p = p.link;
    }
    p.link = null;
  }

  print() {
    let string = '';
    for(let p = this; p !== null; p = p.link) {
      string += `${p.data} | `;
    }
    string += `NULL`;
    console.log(string)
  }
}



let head = new nodeType("head");
head.firstNodeIn(1); // head | 1 | null
head.firstNodeIn(2); // head | 2 | 1 | null
head.firstNodeIn(3); // head | 3 | 2 | 1 | null
head.firstNodeIn(4); // head | 4 | 3 | 2 | 1 | null
head.firstNodeIn(5); // head | 5 | 4 | 3 | 2 | 1 | null
head.firstNodeIn(6); // head | 6 | 5 | 4 | 3 | 2 | 1 | null
head.firstNodeIn(7); // head | 7 | 6 | 5 | 4 | 3 | 2 | 1 | null
head.firstNodeIn(8); // head | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | null
head.lastNodeIn(0); //  head | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | null
head.firstNodeOut(); //  head | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | null
head.lasttNodeOu();  //  head | 7 | 6 | 5 | 4 | 3 | 2 | 1 | null
console.log(head)
// nodeType {     
//  data: 'head',
//  link: nodeType { data: 7, link: nodeType { data: 6, link: [nodeType] } }
// }
head.print(); // head | 7 | 6 | 5 | 4 | 3 | 2 | 1 | NULL