[자바스크립트] 연결리스트 (Linked List)

🌱 연결리스트란 ?

각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다.
🔗 연결리스트-위키피디아

🌱 자바스크립트로 구현하기

const list = {
  head: { value: 10, next: { value: 20, next: { value: 30, next: { value: 40, next: null } } } },
}

console.log(list.head.value) // 10
console.log(list.head.next.value) // 20
console.log(list.head.next.next.value) // 30

위와 같이 연결된 형태로, .next로 연결된 다음 value를 호출할 수 있다.

1. 리스트에 node 추가

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

class LinkedList {
  constructor() {
    let head = new Node('head')
    this.head = head
    this.tail = head

    this.current = undefined
    this.length = 0
  }

  size() {
    return this.length
  }

  append(data) {
    let node = new Node(data)
    this.tail.next = node
    this.tail = node
    this.length += 1
  }
}

let linkedList = new LinkedList()
linkedList.append(10)
linkedList.append(20)
linkedList.append(30)

console.log(linkedList)
/* LinkedList {
  head: Node { data: 'head', next: Node { data: 10, next: [Node] } },
  tail: Node { data: 30, next: null },
  current: undefined,
  length: 3
} */
console.log(linkedList.size()) // 3

LinkedList 의 constructor() 에서 this.head 와 this.tail 은 같은 주소값을 참조하고 있다. 따라서 append() 메서드 정의에서 this.tail.next = node 시,

head: Node { data: 'head', next: Node { data: 10, next: [Node] } },
tail: Node { data: 'head', next: Node { data: 10, next: [Node] } },

head와 tail의 next에 모두 추가 된다.
그리고 this.tail = node 하면 this.head.next 에 연결된 마지막 Node 와 this.tail의 Node가 같은 값을 참조하게 된다.

2. 리스트 데이터 추출

// LinkedList 클래스 안에 메서드 추가
  toString() {
    let circuitNode = this.head
    circuitNode = circuitNode.next

    let str = ''
    for (let i = 0; i < this.length; i++) {
      str += `${circuitNode.data}, `
      circuitNode = circuitNode.next
    }

    return str.slice(0, -2)
  }

console.log(linkedList.toString()) // 10, 20, 30

data 들을 연결된 문자열로 추출할 수 있다.

// LinkedList 클래스 안에 메서드 추가
  getFullData() {
    let circuitNode = this.head
    circuitNode = circuitNode.next

    let dataAry = []
    for (let i = 0; i < this.length; i++) {
      dataAry.push(circuitNode.data)
      circuitNode = circuitNode.next
    }

    return dataAry
  }

console.log(linkedList.getFullData()) // [ 10, 20, 30 ]

데이터를 배열로 추출할 수 있다.

3. 중간 삽입

// LinkedList 클래스 안에 메서드 추가
  insert(idx, data) {
    let circuitNode = this.head
    circuitNode = circuitNode.next

    for (let i = 0; i < idx - 1; i++) {
      circuitNode = circuitNode.next
    }

    let newNode = new Node(data)
    newNode.next = circuitNode.next
    circuitNode.next = newNode

    this.length += 1
  }

linkedList.insert(1, 15)
console.log(linkedList.getFullData()) // [ 10, 15, 20, 30 ]

newNode.next = circuitNode.next : 새로 추가하는 newNode의 next 값은 추가하려는 idx 번째의 Node의 next와 같은 Node를 참조하도록 (가리키도록) 한다.
circuitNode.next = newNode : 그리고 idx 번째의 Node의 next 는 newNode 를 참조하도록(가리키도록) 한다

전체 코드

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

class LinkedList {
  constructor() {
    let head = new Node('head')
    this.head = head
    this.tail = head

    this.current = undefined
    this.length = 0
  }

  size() {
    return this.length
  }

  append(data) {
    let node = new Node(data)
    this.tail.next = node
    this.tail = node
    this.length += 1
  }

  toString() {
    let circuitNode = this.head
    circuitNode = circuitNode.next

    let str = ''
    for (let i = 0; i < this.length; i++) {
      str += `${circuitNode.data}, `
      circuitNode = circuitNode.next
    }

    return str.slice(0, -2)
  }

  getFullData() {
    let circuitNode = this.head
    circuitNode = circuitNode.next

    let dataAry = []
    for (let i = 0; i < this.length; i++) {
      dataAry.push(circuitNode.data)
      circuitNode = circuitNode.next
    }

    return dataAry
  }

  insert(idx, data) {
    let circuitNode = this.head
    circuitNode = circuitNode.next

    for (let i = 0; i < idx - 1; i++) {
      circuitNode = circuitNode.next
    }

    let newNode = new Node(data)
    newNode.next = circuitNode.next
    circuitNode.next = newNode

    this.length += 1
  }
}

let linkedList = new LinkedList()
linkedList.append(10)
linkedList.append(20)
linkedList.append(30)

참고 : 🔗 visualgo-Linked Listhttps://visualgo.net/en/list?slide=1
🔗 제주코딩베이스캠프-[2022 JS 알고리즘] 002. 연결리스트