[자료구조/미완] Linked List(연결리스트) with JS

코드는 복사가 가능하니 살펴보고 싶으시면 IDE에 복사해서 살펴보시는 것을 추천드립니다. ^^

단일 연결 리스트

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

▲노드

class LinkedList {
  #head = null;
  #tail = null;
  #size = 0;

  get size() { return this.#size; }
  
  isEmpty() { return this.#size === 0; }

  add(node) {
    if (this.isEmpty()) {
      this.#head = node;
      this.#tail = this.#head;
    } else {
      this.#tail.next = node;
      this.#tail = node;
    }

    this.#size++;
  }
  
  // 삭제할 node를 아는 경우
  remove(node) {
    if (this.isEmpty()) {
      return null;
    }

	if(node === this.#head) {
      this.#head = this.#head.next;
      if(node === this.#tail) this.#tail = null;
      this.#size--;
      
      return node.data;
    }
    
    let prev = this.#head;
    while (prev.next && prev.next !== node) {
      prev = prev.next;
    }
    if(!prev.next) return null;
    prev.next = node.next;
    if(node === this.#tail) this.#tail = prev;
    this.size--;

    return node.data;
  }
  
  // 삭제할 값을 아는 경우
  removeByValue(value) {
    if (this.isEmpty()) {
      return null;
    }

	if(value === this.#head.data) {
      const removed = this.#head;
      this.#head = this.#head.next;
      if(node === this.#tail) this.#tail = null;
      this.#size--;
      
      return removed.data;
    }
    
    let prev = this.#head;
    while (prev.next && prev.next.data !== value) {
      prev = prev.next;
    }
    if(!prev.next) return null;
    
    const removed = prev.next;
    prev.next = removed.next;
    if(value === this.#tail.data) this.#tail = prev;
    this.#size--;

    return removed.data;
  }
  
  // 추가 구현 가능
  // addAt(index) {} // index에 node 추가
  // removeAt(index) {} // index에 있는 node 삭제
  // find(value) {} // value가진 node 찾기
  // reverse() {} // list 반대로 뒤집기

  print() {
    let cur = this.#head;
    let ret = [];
    while (cur) {
      ret.push(cur.data);
      cur = cur.next;
    }

    console.log(ret.join(" "));
  }
}

▲연결 리스트

// Node와 LinkedList 코드를 모두 가져오셔야 합니다.
// 테스트 코드
const list = new LinkedList();

for(let i=1; i<10; i++) {
  list.add(new Node(i));
}

list.print(); // 1 2 3 4 5 6 7 8 9
list.remove(new Node(2)); // 2
list.print(); // 1 3 4 5 6 7 8 9
list.remove(new Node(11)); // null

이중 연결 리스트(미완)

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

▲노드

class LinkedList {
  #head = null;
  #tail = null;
  #size = 0;

  get size() { return this.#size; }
  
  isEmpty() { return this.#size === 0; }

  add(node) {
    if (this.isEmpty()) {
      this.#head = node;
      this.#tail = this.#head;
    } else {
      this.#tail.next = node;
      node.prev = this.#tail;
      this.#tail = node;
    }

    this.#size++;
  }
  
  // 삭제할 node를 아는 경우
  remove(node) {
    if (this.isEmpty()) {
      return null;
    }

	if(node === this.#head) {
      this.#head = this.#head.next;
      this.#head.prev = null;
      if(node === this.#tail) this.#tail = null;
      this.#size--;
      
      return node.data;
    }
    
    let prev = this.#head;
    while (prev.next && prev.next !== node) {
      prev = prev.next;
    }
    if(!prev.next) return null;
    prev.next = node.next;
    if(node === this.#tail) this.#tail = prev;
    this.size--;

    return node.data;
  }
  
  // 삭제할 값을 아는 경우
  removeByValue(value) {
    if (this.isEmpty()) {
      return null;
    }

	if(value === this.#head.data) {
      const removed = this.#head;
      this.#head = this.#head.next;
      if(node === this.#tail) this.#tail = null;
      this.#size--;
      
      return removed.data;
    }
    
    let prev = this.#head;
    while (prev.next && prev.next.data !== value) {
      prev = prev.next;
    }
    if(!prev.next) return null;
    
    const removed = prev.next;
    prev.next = removed.next;
    if(value === this.#tail.data) this.#tail = prev;
    this.#size--;

    return removed.data;
  }
  
  // 추가 구현 가능
  // addAt(index) {} // index에 node 추가
  // removeAt(index) {} // index에 있는 node 삭제
  // find(value) {} // value가진 node 찾기
  // reverse() {} // list 반대로 뒤집기

  print() {
    let cur = this.#head;
    let ret = [];
    while (cur) {
      ret.push(cur.data);
      cur = cur.next;
    }

    console.log(ret.join(" "));
  }
}

▲연결 리스트

// Node와 LinkedList 코드를 모두 가져오셔야 합니다.
// 테스트 코드
const list = new LinkedList();

for(let i=1; i<10; i++) {
  list.add(new Node(i));
}

list.print(); // 1 2 3 4 5 6 7 8 9
list.remove(new Node(2)); // 2
list.print(); // 1 3 4 5 6 7 8 9
list.remove(new Node(11)); // null

원형 연결 리스트(미완)

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

▲노드

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

  isEmpty() {
    return this.size ? false : true;
  }

  add(node) {
    if (this.size) {
      let last = this.head.next;
      while (last.next.data != this.head.data) {
        // data가 중복되지 않기 때문에 가능한 조건문
        last = last.next;
      }
      last.next = node;
      node.prev = last;
      node.next = this.head;
      this.head.prev = node;
    } else {
      this.head = node;
      this.head.next = this.head;
      this.head.prev = this.head;
    }

    this.size++;
  }

  del(node) {
    if (this.isEmpty()) {
      return null;
    }

    let find = this.head;
    while (find.data != node.data) {
      find = find.next;
    }
    find.prev.next = find.next;
    find.next.prev = find.prev;

    this.size--;

    return find.data;
  }

  print() {
    let next = this.head;
    let ret = [];
    while (1) {
      ret.push(next.data);
      next = next.next;
      if (next.data == this.head.data) break;
    }

    console.log(ret.join(" "));
  }
}

▲연결 리스트

// Node와 LinkedList 코드를 모두 가져오셔야 합니다.
// 테스트 코드
const list = new LinkedList();

for(let i=1; i<10; i++) {
  list.add(new Node(i));
}

list.print(); // 1 2 3 4 5 6 7 8 9
list.remove(new Node(2)); // 2
list.print(); // 1 3 4 5 6 7 8 9
list.remove(new Node(11)); // null