JavaScript - 자료구조 (이중연결리스트)

오늘은 이중 연결 리스트 (Double Linked List)에 대해 알아보겠습니다.

파이썬에 있는 것을 스스로 JavaScript로 옮겼습니다.

 

연결 리스트란?

    기존 C++과 같이 메모리를 관리해줘야 하는 언어에서 배열은 사용할 공간이 늘어날 일을 대비해 미리 공간을 할당했어야 했습니다.

그러한 단점을 극복하고자 연결 리스트라는 자료구조가 탄생합니다.

일반 연결 리스트는 사람이 허리에 끈을 묶고 기차놀이를 하는 것이라 생각하시면 됩니다.

앞 사람이 가는 방향으로만 갈 수 있고 사람이 추가되면 뒤쪽에만 추가되듯이요

A → B

 

용어)

노드: 데이터 + 주소로 이루어진 데이터 저장 단위

포인터: 주소와 같은 말인데 이 데이터 다음에 어떤 노드가 오는지 가리키는 주소입니다

 

장점) 미리 공간을 할당하지 않아도 되고 이중 연결리스트의 경우에는 양방향으로 탐색이 가능합니다.

단점) 중간 노드가 삭제되면, 주변 노드 연결 작업을 부가적으로 해줘야 함, 접근 속도가 배열보다 상대적으로 느립니다.

 

이중 연결리스트?

    위에 예시로 든 기차놀이는 맨 앞사람이 가는 방향으로만 갈 수 있었지만 이제는 맨 뒷사람이 앞사람 역할을 하여 반대방향으로도 갈 수 있습니다. 그러니 양방향으로 연결이 되어있다고 생각하시면 됩니다.

 

먼저 CodeSandBox를 열어주세요. 

여기에서 확장 프로그램을 설치하시고 작업 표시줄에 고정하시면 별도의 프로그램처럼 사용가능하고 브라우저 창과 별도로 창이 띄워집니다.

https://codesandbox.io/

 

아래의 Code를 입력해보세요. 편의상 세미콜론은 생략하겠습니다.

맨 첫줄에 console.clear()를 입력해주는 이유는 코드 작성을 하다보면 웹 에디터가 중간중간에 문법 검사를 합니다. 나는 입력 중인데 중간에 웹 에디터가 검사해버리면 당연히 오류를 뿜어낼겁니다.

이 오류메시지는 계속 쌓이게 되므로 쌓이는 것이 싫다면 첫 줄에 console.clear()를 입력하시면 됩니다.

 

단일 연결 리스트의 경우에는 아래의 코드에서 prev나 next 속성을 제외하면 단일 연결리스트가 됩니다.

또한 연결 리스트는 class로 구성하시는 것이 편한데 더 좋은 방법이 있다면 알려주세요!

 

console.clear() // 오류 쌓임 방지



// 이중연결리스트

// 노드 생성

class Node {

  constructor(data, prev = null, next = null) {

    this.data = data

    this.prev = prev

    this.next = next

  }

}



// 노드를 관리하는 class NodeManagement

class NodeMgmt {

  constructor(data) {

    this.head = new Node(data)

    this.tail = this.head

  }

// 노드 전체를 출력함

  desc() {

    let node = this.head

    while (node) {

      console.log(node.data)

      node = node.next

    }

  }

// 앞에서부터 뒤로 탐색하는 메서드

  search_from_head(data) {

    let node = this.head

    if (!node) {

      return null

    }

    while (node) {

      if (node.data === data) {

        return node.data

      } else {

        node = node.next

      }

    }

    return null

  }

// 뒤에서부터 앞으로 탐색하는 메서드

  search_from_tail(data) {

    let node = this.tail

    if (!node) return null

    while (node) {

      if (node.data === data) {

        return node.data

      } else {

        node = node.prev

      }

    }

    return null

  }

// 데이터가 들어있는 노드를 삽입하는 메서드

  insert(data) {

    let node = this.head

    if (!node) {

      this.head = new Node(data)

      this.tail = this.head

    } else {

      while (node.next) {

        node = node.next

      }

      let newNode = new Node(data)

      node.next = newNode

      newNode.prev = node

      this.tail = newNode

    }

  }



  insert_before(data, before_data) {

    let node = this.head

    if (!node) {

      this.head = new Node(data)

      return true;

    } else {

      let node = this.tail

      while (node.data !== before_data) {

        node = node.prev

        if (!node) {

          return false

        }

      }

      let newNode = new Node(data)

      let before_new = node.prev

      before_new.next = newNode

      newNode.prev = before_new.prev

      newNode.next = node

      node.prev = newNode

      return true

    }

  }

// 노드를 삭제하는 메서드

  delete(data) {

    let node = this.head

    if (!node) {

      console.log('해당 값을 가진 노드가 없습니다.')

      return

    }

    if (node.data === data) {

      let temp = this.head

      this.head = this.head.next

      this.head.next.prev = temp

      // delete temp

    } else {

      let node = this.head

      while (node.next) {

        if (node.next.data === data) {

          let temp = node.next

          node.next = node.next.next

          temp.next.prev = node

          // delete temp

        } else {

          node = node.next

        }

      }

    }

  }

}

let node = new NodeMgmt(0)

for (let i = 1; i < 11; i++) {

  node.insert(i) // 1부터 10까지 노드를 0뒤로 삽입함

}

node.desc() // 노드 전체를 출력하고 이 때의 결과는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10