[JS] 연결리스트에 대해서

안녕하세요.

카카오 2021 인턴 표 편집을 하던도중 이건 그냥 봐도 연결리스트를 쓰라는 것 같더라구용.

자바스크립트에서 한 번도 연결리스트를 써본 적이 없었는데 구현 코드를 보니 상당합니다.

이건 정리 한 번 해야겠어요!

 

자 그럼 같이 한 번 보죠!

---

1. 연결리스트가 유용한 상황

 

연결리스트는 배열 중간에 자료를 없앤다던가, 새로 삽입해야한다던가 하는 상황에서 매우 유용한 자료입니다.

일반적인 stack 구조에서는 pop이나 push가 아닌 중간에서 자료를 조작해줘야하는 상황이 오면, 뒤에 모든 요소를 같이 조작해줘야하거든요.

 

표 편집의 예시 (출처: 2021 KAKAO INTERNSHIP)

 

이런 구조에서 유용하게 쓰입니다.

그럼 javascript에서 구현을 한 번 알아볼까요?

 

2. javascript에서 구현 팁

 

큐나 힙처럼 배열안에서 조작한다면 결국엔 나중에 filter 함수 등을 통해서 없애는 값을 한 번 탐색해줘야하기 때문에 효율적이지 못합니다.

일반적으로 javascript에서는 Node라는 클래스를 만들고 이 클래스를 연결리스트 클래스에서 계속 이어주는 식으로 구현을 한답니다. 코드가 상당히 길어요.

 

그러면 이제 코드를 같이 볼까요?

 

Node 구현

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

 

저 next로 계속 다음 노드를 가줄거에요.

node.next.next.value 이런 식으로 타고타고 갑니다.

 

연결리스트 구현

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }
  
  find(value) {
    let currNode = this.head;
    while (currNode.value !== value) {
      currNode = currNode.next;
    }
    return currNode;
  }
  
  append(value) {
    const node = new Node(value);
    if (!this.head) {
      this.head = node;
      this.tail = node;
    } else {
      this.tail.next = node;
      this.tail = node;
    }
  }
  
  insert(node, value) {
    const newNode = new Node(value);
    newNode.next = node.next;
    node.next = newNode;
  }
  
  remove(value) {
    let prevNode = this.head;
    while (prevNode.next.value !== value) {
      prevNode = prevNode.next;
    }
    const val = prevNode.next.value;
    if (prevNode.next) {
      prevNode.next = prevNode.next.next;
    }
    
    return val;
  }
  
  display() {
    let currNode = this.head;
    const result = [];
    while (currNode) {
      result.push(currNode.value);
      currNode = currNode.next;
    }
    
    return result;
  }
}

 

이 코드에서는 value 그러니까 연결리스트에 들어있는 노드의 값에 따라서

찾고(find), 중간에 추가(insert)가 이뤄집니다.

만약 index 등으로 접근하려고 하면, 중간 값이 수정될 때, 뒷쪽에 관리되는 index를 전부 수정해줘야하기 때문에 값으로 접근하는게 효율적입니다.

 

그럼 이 연결리스트를 약간 수정해서 저 표 편집을 한 번 다뤄보죠!