[Javascript] LinkedList 구현하기

linkedList 관련 이론 정보는 이곳

Single LinkedList

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

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

  add(data) {
    const node = new Node(data);
    if (!this.head) {
      this.head = node;
    } else {
      let curr = this.head;
      while (curr.next) curr = curr.next;
      curr.next = node;
    }
    this.size++;
  }

  delete(data) {
    // linked list가 비어있을 때
    if (!this.head) {
      console.log("empty");
      return;
    }
    // 현재 헤드가 delete 대상일 때
    if (this.head.data === data) {
      this.head = this.head.next;
      size--;
      return;
    }
    // 그외 순회
    let curr = this.head.next;
    let pre = this.head;
    let index = 1;
    // 다음 node가 delete 대상 노드이거나, list 끝까지 순회. 대상 node가 없으면 curr는 null이 된다
    while (!curr === null && curr.data !== data) {
      pre = curr;
      curr = curr.next;
    }
    if (curr === null) {
      console.log("there is no that data");
      return;
    } else {
      pre.next = curr.next;
      this.size--;
    }
  }

  search(data) {
    // linked list가 비어있을 때
    if (!this.head) {
      console.log("empty");
      return;
    }
    // 다음 node가 search 대상 노드이거나, list 끝까지 순회. 대상 node가 없으면 curr는 null이 된다
    let curr = this.head;
    while (!curr === null && curr.data !== data) {
      pre = curr;
      curr = curr.next;
    }
    if (curr === null) {
      console.log("there is no that data");
      return;
    } else {
      return curr;
    }
  }
}

Double LinkedList

// Queue의 양방향 형태. 

// double LinkedList에서 Queue의 형태를 양 방향으로 적용할 수 있게 하면 될것같다.
// front, back에 관련된 push, pop으로 구현한다. 


class Node {
    constructor(data) {
      this.data = data;
      this.next = null;
    }
  }
  
  class Deque {
    constructor() {
      this.head = null;
      this.tail
      this.size = 0;
    }
  
    in(data) {
      const node = new Node(data);
      if (!this.head) {
        this.head = node;
      } else {
        let curr = this.head;
        while (curr.next) curr = curr.next;
        curr.next = node;
      }
      this.size++;
    }
  
    out() {
      // linked list가 비어있을 때
      if (!this.head) {
        throw new Error("Empty Error");
      }
      // 헤드에 해당하는 node를 return하고 다음 node를 head로 지정
      const output = this.head;
      this.head = output.next;
      output.next = null;
      return output;
    }
  
    // 해당 요소가 몇 번째에 있는지 index, 없으면 -1을 return
    include(data) {
      // linked list가 비어있을 때
      if (!this.head) {
        return -1;
      }
      let index = 0;
  
      // 다음 node가 search 대상 노드이거나, list 끝까지 순회. 대상 node가 없으면 curr는 null이 된다
      let curr = this.head;
      let pre;
  
      while (curr !== null && curr.data !== data) {
        pre = curr;
        curr = curr.next;
        index++;
      }
      if (curr === null) {
        return -1;
      } else {
        return index;
      }
    }
  }
  
  const queue = new Queue();
  
  queue.in("first");
  queue.in("second");
  queue.in("third");
  console.log("queue", queue);
  
  console.log(queue.include("zero")); // -1 
  console.log(queue.include("first")); // 0
  console.log(queue.include("second")); // 1
  console.log(queue.include("third")); // 2
  
  console.log(queue.out()); // first
  console.log(queue.out()); // second
  console.log(queue.out()); // thrid
  
  console.log(queue.include("empty")); // -1
  
  // console.log(queue.out()); // Empty Error
  

Queue 구현하기

// 선입 선출, FIFO (First In First Out)

// LinkedList로 큐를 구현하려면 선입 선출이어야 한다.
// ADD는 기존과 같이 하고 빼낼 때 head 부분을 빼내고 head를 curr의 next로 넣어주면 되지 않을까 ?

// 만들어둔 single을 가져온 후 수정해본다

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

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

  in(data) {
    const node = new Node(data);
    if (!this.head) {
      this.head = node;
    } else {
      let curr = this.head;
      while (curr.next) curr = curr.next;
      curr.next = node;
    }
    this.size++;
  }

  out() {
    // linked list가 비어있을 때
    if (!this.head) {
      throw new Error("Empty Error");
    }
    // 헤드에 해당하는 node를 return하고 다음 node를 head로 지정
    const output = this.head;
    this.head = output.next;
    output.next = null;
    return output;
  }

  // 해당 요소가 몇 번째에 있는지 index, 없으면 -1을 return
  include(data) {
    // linked list가 비어있을 때
    if (!this.head) {
      return -1;
    }
    let index = 0;

    // 다음 node가 search 대상 노드이거나, list 끝까지 순회. 대상 node가 없으면 curr는 null이 된다
    let curr = this.head;
    let pre;

    while (curr !== null && curr.data !== data) {
      pre = curr;
      curr = curr.next;
      index++;
    }
    if (curr === null) {
      return -1;
    } else {
      return index;
    }
  }
}

const queue = new Queue();

queue.in("first");
queue.in("second");
queue.in("third");
console.log("queue", queue);

console.log(queue.include("zero")); // -1 
console.log(queue.include("first")); // 0
console.log(queue.include("second")); // 1
console.log(queue.include("third")); // 2

console.log(queue.out()); // first
console.log(queue.out()); // second
console.log(queue.out()); // thrid

console.log(queue.include("empty")); // -1

// console.log(queue.out()); // Empty Error