Linked list, Hash Table

Judo·2020년 12월 6일

자료구조

Linked list

Diagram

각 원소는 원소 자신과 포인터가 포함된 노드로 구성
연속되는 노드들이 포인터로 연결
마지막 노드의 포인터는 Null을 가리킴
프로그램이 수행되는 동안 크기가 커지거나 작아질 수 있다

Operation

push(value)
- 맨 뒤 데이터 추가
pop()
- 맨 뒤 데이터 제거
unshift(value)
- 맨 앞 데이터 추가
shift()
- 맨 앞 데이터 제거
get(index)
- index에 위치한 데이터 가져오기
set(index, value)
- index에 데이터를 value로 변경
insert(index, value)
- index에 value 삽입하기
reverse()
- 리스트를 반대로 전환하기

Purpose

데이터의 추가/삽입 및 삭제가 용이
검색의 경우 처음 요소부터 탐색을 해야하므로 검색 속도가 느림
검색을 자주 하면 배열이 유리
추가/삭제가 많으면 연결 리스트가 유리

Implement

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

class LinkedList {
  constructor(value) {
    const newNode = new Node(value);
    this.head = newNode;
    this.tail = this.head;
    this.length = 1;
  }
  push(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
    return this;
  }

  pop() {
    if (!this.head) {
      return undefined;
    } else {
      let temp = this.head;
      let pre = this.head;
      while (temp.next) {
        pre = temp;
        temp = temp.next;
      }
      this.tail = pre;
      this.tail.next = null;
      this.length--;

      if (this.length === 0) {
        this.head = null;
        this.tail = null;
      }
      return temp;
    }
  }

  unshift(value) {
    const newNode = new Node(value);

    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head = newNode;
    }
    this.length++;
    return this;
  }
  shift() {
    if (!this.head) {
      return undefined;
    } else {
      let temp = this.head;
      temp.next = null;
      this.head = this.head.next;
      this.length--;
      if (this.length === 0) {
        this.tail = null;
      }
      return temp;
    }
  }

  get(index) {
    if (index < 0 || index >= this.length) {
      return undefined;
    } else {
      let temp = this.head;
      for (let i = 0; i < index; i++) {
        temp = temp.next;
      }

      return temp;
    }
  }
  set(index, value) {
    let temp = this.get(index);
    if (temp) {
      temp.value = value;
      return true;
    }
    return false;
  }
  insert(index, value) {
    if (index === 0) return this.unshift(value);
    if (index === this.length) return this.push(value);
    if (index < 0 || index > this.length) return false;

    const newNode = new Node(value);
    const temp = this.get(index);

    newNode.next = temp.next;
    temp.next = newNode;
    this.length++;
    return true;
  }

  remove(index) {
    if (index === 0) return this.shift();
    if (index === this.length - 1) return this.pop();
    if (index < 0 || index > this.length - 1) return undefined;
    
    let before = this.get(index - 1);
    let temp = before.next;
    before.next = temp.next;
    temp.next = null;
    this.length--;
    return temp;
  }

  reverse() {
    let temp = this.head;
    this.head = this.tail;
    this.tail = temp;
    let prev = null;
    let next = temp.next;

    for (let i = 0; i < this.length; i++) {
      next = temp.next;
      temp.next = prev;
      prev = temp;
      temp = next;

    }
    return this;
  }
}