Javascript 자료구조 02 : Linked List

protect-me·2021년 4월 7일

JavaScript data structure js linkedlist 링크드리스트 연결리스트 자료구조

자료구조

목록 보기

2/7

Linked List(링크드 리스트 | 연결 리스트)

데이터와 포인터를 가지고 있는 노드의 연결.
Node = Data + Pointer

Node1
data
pointer > Node2
          data
          pointer > Node3
                    data
                    pointer > Node4
                              data
                              pointer ...

장점: 자료 추가/삭제 시, index 수정이 불필요
단점: index를 통한 임의의 접근이 불가능하기 때문에 데이터 검색이 느릴 수 있음
pointer를 저장할 공간이 추가적으로 필요

*코드 : CRUD 순서로 작성

Node, LinkedList 구현

// Node
function Node(data) {
  this.data = data;
  this.next = null;
}
// LinkedList
function LinkedList() {
  this.length = 0;
  this.head = null;
  this.append = append; // C : 데이터 추가
  this.insert = insert; // C : 데이터 중간 삽입
  this.read = read; // R : 데이터 읽기
  this.find = find; // 데이터 찾기
  this.remove = remove; // D : 데이터 삭제
}

append(데이터 추가)

// C: append(데이터 추가)
function append(data) {
  const node = new Node(data);
  let current = this.head;
  if (!current) {
    // head가 없을 경우 head로 세팅
    this.head = node;
  } else {
    // head가 있을 경우
    while (current.next) {
      current = current.next;
    }
    current.next = node;
  }
  this.length++;
  return node;
}

insert(데이터 중간 삽입)

// C : insert(데이터 중간 삽입)
function insert(beforeData, data) {
  const node = new Node(data);
  let current = this.head;
  let before = null;
  // 찾는 데이터와 node를 돌면서 나오는 데이터의 값이 다르면 loop
  while (current.data !== beforeData) {
    before = current;
    // current.next가 없을 경우
    if (!current.next) {
      return -1;
    }
    current = current.next;
  }
  // before의 next가 새로운 node를 가리키도록 하고
  before.next = node;
  // 새로운 node가, 기존 before가 가리키던 node를 가리키도록 한다
  node.next = current;
  this.length++;
  return node;
}

read(전체 데이터 읽기)

// R : read(전체 데이터 읽기)
function read() {
  let arr = [];
  let current = this.head;
  while (current) {
    arr.push(current.data);
    current = current.next;
  }
  return arr;
}

remove(데이터 삭제)

// D : remove(데이터 삭제)
function remove(data) {
  let before = null;
  let current = this.head;
  let remove = -1;
  // 삭제하려는 데이터가 head의 데이터와 일치할 경우
  if (data === current.data) {
    remove = this.head;
    this.head = this.head.next;
    this.length--;
  } else {
    // next가 있고, 찾는 데이터와 일치하지 않을 경우 loop
    while (current.next && current.data !== data) {
      before = current;
      current = current.next;
    }
    // 마지막 요소로 next가 없거나 data가 일치할 경우 loop를 빠져나옴.
    // 일치하는 데이터가 있을 경우 삭제
    if (current.data === data) {
      remove = current;
      before.next = current.next;
      this.length--;
    }
  }
  return remove;
}

테스트 코드

// 초기화
let linkedList = new LinkedList();

// 데이터 추가
linkedList.append("first");
linkedList.append("second");
linkedList.append("third");
linkedList.append("fourth");
linkedList.append("fifth");

// 데이터읽기
console.log(linkedList.read());
// (5) ["first", "second", "third", "fourth", "fifth"]

// 데이터 중간 삽입: "third"를 찾고 그 앞에 "third(1)"을 추가
console.log(linkedList.insert("third", "third(1)"));
console.log(linkedList.read());
// (6) ["first", "second", "third(1)", "third", "fourth", "fifth"]

// 데이터 중간 삽입 : 없는 위치를 찾을 때
console.log(linkedList.insert("bird", "third(?)")); // -1
console.log(linkedList.read());

// 데이터 삭제 : head 데이터("first") 삭제
console.log(linkedList.remove("first"));
console.log(linkedList.read());
// (5) ["second", "third(1)", "third", "fourth", "fifth"]

// 데이터 삭제 : 중간 데이터("third(1)") 삭제
console.log(linkedList.remove("third(1)"));
console.log(linkedList.read());
// (4) ["second", "third", "fourth", "fifth"]

// 데이터 삭제 : 마지막 데이터("fifth") 삭제
console.log(linkedList.remove("fifth"));
console.log(linkedList.read());
// (3) ["second", "third", "fourth"]

// 데이터 삭제 : 없는 값을 삭제하려고 할 때
console.log(linkedList.remove("bird")); // -1
console.log(linkedList.read());
// (3) ["second", "third", "fourth"]