연결 리스트를 알아보기

연결 리스트란?

[value][pointer] -> [value][pointer] -> [null]

연결 리스트는 데이터와 포인터를 가지고 있는 노드로 구성되어 있는 한 줄로 연결된 자료 구조이다.
장점으로는 데이터 추가와 삭제시 O(1) 시간이 걸린다. 단점은 데이터를 검색시 O(n)의 시간이 걸린다.

구현

Node 클래스

data와 다음 노드를 가리킬 next를 가진다.

lass Node {
  constructor(data, next = null) {
    this.data = data;
    this.next = next;
  }
}

LinkedList 클래스 초기화

head를 null로 size는 0으로 초기화 한다.

constructor() {
  this.head = null;
  this.size = 0;
}

데이터 삽입

삽인할 위치가 0인 경우, head에 넣어준다. 특정 위치에 데이터를 삽입할 경우, 삽입할 위치의 직전 노드에 새로운 노드를 끼워주고 나머지 노드를 연결하면 된다.

insertAt(index, data) {
  const newNode = new Node(data);

  if (index === 0) {
    newNode.next = this.head;
    this.head = newNode;
  } else {
    let cur = this.head;

    for (let i = 0; i < index - 1; i += 1) {
      cur = cur.next;
    }
    newNode.next = cur.next; // 나머지 노드를 연결한다.
    cur.next = newNode; // 직전 노드에 연결한다.
  }
  this.size += 1;
}

데이터 삭제

삭제할 위치의 직전 노드에 삭제할 위치의 다음 노드를 연결시켜주면 된다.

deleteAt(index) {
  if (index === 0) {
    this.head = this.head.next;
  } else {
    let cur = this.head;

    for (let i = 0; i < index - 1; i += 1) {
      cur = cur.next;
    }
    cur.next = cur.next.next;
  }
  this.size -= 1;
}

출력

출력은 head에서 부터 시작해서 출력하면 된다.

print() {
  let res = '';
  let cur = this.head;

  while (cur) {
    res += cur.data;
    cur = cur.next;
  }
  return res;
}

전체 코드

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

class LinkedList {
  constructor() {
    this.head = null;
    this.size = 0;
  }

  insertAt(index, data) {
    const newNode = new Node(data);

    if (index === 0) {
      newNode.next = this.head;
      this.head = newNode;
    } else {
      let cur = this.head;

      for (let i = 0; i < index - 1; i += 1) {
        cur = cur.next;
      }
      newNode.next = cur.next;
      cur.next = newNode;
    }
    this.size += 1;
  }

  insert(data) {
    this.insertAt(this.size, data);
  }

  deleteAt(index) {
    if (index === 0) {
      this.head = this.head.next;
    } else {
      let cur = this.head;

      for (let i = 0; i < index - 1; i += 1) {
        cur = cur.next;
      }
      cur.next = cur.next.next;
    }
    this.size -= 1;
  }

  print() {
    let res = '';
    let cur = this.head;

    while (cur) {
      res += cur.data;
      cur = cur.next;
    }
    return res;
  }
}