링크드리스트(LinkedList) 이란? (+ Javascript로 구현)

1. 링크드 리스트 (LinkedList)

: 노드라고 불리는 각 요소(element)들을 담고 있는 선형 자료 구조. 노드는 데이터와 다음 노드의 정보 또는 주소값을 저장하는 Object이다.

 

2. Array vs LinkedList 

- Array

: Array의 요소(element)들은 특정한 위치 또는 인덱스에 저장되어 있다.

 

- LinkedList

: LinkedList의 요소인 노드는 특정한 위치에 저장되어 있지 않고 각 노드가 갖고 있는 pointer 값으로 연결 되어 있다. 즉, 한 노드의 위치는 그 노드의 위치를 갖고 있는 다른 노드에 의존한다.

 

링크드 리스트 도식

3. 링크드리스트의 장단점

 - 장점 

 : LinkedList에서 노드의 제거 및 추가는 대상이 되는 노드의 위치를 갖고 있는 다른 노드의 pointer 값만 바꿔주면 되기 때문에 노드 삭제 및 추가시 전체적인 배열의 조정 없이 간단하게 수행된다.

 

 - 단점

 : 특정 노드의 탐색이 느리다. LinkedList의 탐색은 Head라고 불리는 첫 번째 노드부터 순차적으로 진행되기 때문에 탐색 수행이 느리다. 또한 노드는 데이터 뿐만이 아닌 다른 노드의 주소값을 저장해야 하기 때문에 메모리를 추가적으로 사용한다.

 

4. Javascript로 구현

// 데이터(data)와 다음 노드의 정보를 갖는(next) Node 객체 정의.
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

// 리스트의 첫 노드인 head와 helper 메서드를 갖는 LinkedList 정의 
class LinkedList {
  // LinkedList가 생성될 때 head에 인자값이 들어가지 않으면, null을 세팅함.
  constructor(head = null) {
    this.head = head;
  }

  size() {
    let count = 0;
    let node = this.head;
    while (node) {
      count++;
      node = node.next;
    }
    return count;
  }

  clear() {
    this.head = null;
  }

  getLast() {
    let lastNode = this.head;
    if (lastNode) {
      while (lastNode.next) {
        lastNode = lastNode.next;
      }
    }

    return lastNode;
  }

  getFirst() {
    return this.head;
  }
}

// node1, node2 생성 후 node1에 node2의 정보 저장.
let node1 = new Node(2);
let node2 = new Node(5);
node1.next = node2;

// node1을 head로 하는 LinkedList 생성
let list = new LinkedList(node1);

// list의 size 출력.
console.log(list.size());