[자료구조] 자료구조 목적과 선형 자료구조 종류

colki·2021년 5월 31일
자료구조자바스크립트
1

Udemy_JavaScript: Master the Coding Interview: Data Structures + Algorithms 강의를 바탕으로 메모한 내용입니다.

자료구조의 목적

We can put things in data structures and we can take things from data structures

  • 자료구조의 대상은 RAM, 바로 메모리이다.

  • 컴퓨터가 데이터를 저장하고 처리하는 구조를 보면 RAM의 역할을 알 수 있다.

  • CPU가 정보를 얻는 작업을 최소화하기 위해 데이터구조를 이해해야 한다.

    • CPU
      CRU cache라는 아주 작은 메모리를 가지고 있다.
      처리속도가 가장 빠르다

    • RAM (MEOMORY)
      Random Access Memory
      데이터를 주소에 저장하는 방식으로 이진법으로 구성된 8byte 형태.
      컴퓨터를 끄면 사라진다. 용량이 적고 비싸다.
      storage보다 빠르게 data를 저장하고 읽을 수 있다.
      storage에 저장된 것들을 CPU로 load해와야 하는데, storage가 너무 느리기 때문에 memory가 받아서 CPU에게 넘겨준다.
      storage > memory > cpu
      그래서 memory를 효율적으로 다루는게 중요하다.

    • STORAGE
      속도가 매우 느리며 용량이 크고 저렴하다.
      컴퓨터를 꺼도 남아있다.
      CPU가 strorage에서 프로그램을 가져온다.
      disk, ssd, drive, usic files, video files...

  • 자료구조의 종류

    • Linear Structure
      자료를 순차적으로 나열시킨 형태로써, 자료를 저장하고 꺼내는 방식을 구현하는 것이 포인트.
    • Nonlinear Structure
      데이터가 계층적으로 구성된 형태로써, 구조적으로 데이터를 표현하는 것이 포인트.

Hash Table

해시함수가 키값을 바탕으로 반환한 해시값을 인덱스로 사용해서 만든 배열 구조로써 해시를 이용해 저장위치를 즉시 참조할 수 있으므로 자료구조에 접근할 때 모두 O(1)의 시간복잡도를 가진다.
해시값으로 인덱스에 접근하는 시간복잡도가 O(1)이더라도, 특정 해시값에 많은 데이터가 쌓이게 되면 검색할 때 시간이 오래 걸리고 충돌이 일어날 수 있다.

Es6부터 추가된 Set과 Map 객체도 해시테이블의 일종이다.
Map객체는 어떤 데이터 타입이라도 key로 사용할 수 있고, key- value쌍을 통으로 저장한다. Set은 Map과 유사하지만 차이점이 있다면, Set은 key값만 저장하고, 중복을 허용하지 않는다.

Array List vs Linked List

Array List 와 Linked List를 비교해서 차이점을 알아두면 좋다

Array List

(C++ 언어에서 사용하는 정적배열은 length가 고정되어 있어서 개발자가 관리하기 쉽다.)
인덱스를 기준으로 연속된 메모리 공간에 같은 자료형의 데이터를 저장하는 방식이다. Array는 정적배열과 동적배열로 분류할 수 있는데, 자바스크립트는 동적 배열(Dynamic Array)에 해당한다.

동적배열은 연속적으로 데이터가 붙어있는 채로 저장되야 하기 때문에, 제한된 length 초과시 카피해서 통으로 새로 만들기 때문에 메모리가 많이 필요해진다. 자기들끼리 붙어있는 특성상, 메모리의 한계치에 도달한다면, 메모리의 어딘가로 통째로 옮겨야 하기 때문에, 2배이상의 공간을 확보해야 한다. 길이변화에는 유연하지만 메모리 관리가 어렵다.

O(1) : index로 접근, push or pop
O(n) : insert/delete : splice shift unshift
Array는 아이템 하나를 추가, 삭제하는데에도 다른 데이터들의 인덱스가 앞으로 이동하거나 또는 뒤로 이동하기 때문에, insert, delete 등을 수행할 때는 성능이 떨어진다.

Linked List

흩어져 있는 데이터끼리 pointer로 연결 link 된 자료구조로써, 연속적으로 붙어서 저장된게 아니기 때문에 연결 목록을 반복, 순회하는 것은 array에 비해 느리지만 insert, delete를 할 때 인덱스를 이동할 필요가 없기 때문에, array보다 속도가 빠르다.

Singly Linked List
각 노드들은 .next 라는 singly pointer를 가지고 있고, 처음노드는 .head 마지막 노드는 .tail이라 부른다. 마지막 노드 tail의 pointer는 null을 가리킨다. 메모리가 적거나 비쌀 때 사용한다.

Singly Linked List 코드 구현 
// 1 -> 10 -> "99" -> 5 -> 16
class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedList {
  constructor(value) {
    this.head = {
      value: value,
      next: null
    };

    this.tail = this.head; // 노드가 하나일 땐 머리이자 꼬리
    this.length = 1;
  }

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

    this.tail.next = newNode; // 꼬리에 포인터를 달아주는 것.
    this.tail = newNode; // 꼬리 업데이트
    this.length++;

    return this;
  }

  prepend(value) {
    const newNode = new Node(value);
    newNode.next = this.head;

    this.head = newNode;
    this.length++;
    return this;
  }

  printList() { // value 배열
    const array = [];
    let currentNode = this.head;

    while (currentNode !== null) {
      array.push(currentNode.value);
      currentNode = currentNode.next; // ?
    }

    return array;
  }

  insert(index, value) {
    // check params
    if (index === 0) {
      return this.prepend(value);
    }

    if (index >= this.length) {
      return this.append(value);
    }
    // 1 -> 10 -> "99" -> 5 -> 16

    const newNode = new Node(value);
    const leader = this.traverseToIndex(index - 1);
    // 10
    // (index -1)인 노드
    const holdingPointer = leader.next;
    // 5
    leader.next = newNode;
    newNode.next = holdingPointer;
    this.length++;

    return this.printList();
  }

  traverseToIndex(index) {
    //check params
    let counter = 0; // counter === index
    let currentNode = this.head; // head부터 탐색

    while (counter !== index) { //순회하면서 해당 index까지 탐색
      currentNode = currentNode.next;
      // keep moving the current node over to the right.
      // head부터 시작해서 currentNode를 업뎃
      // counter가 (index-1)이 될때까지 순회하는것.
      // (index-1)에 해당하는 currentNode가 너니?
      counter++;
    }

    return currentNode; // (index -1)인 노드
  }

  remove(index) {
     // check params
    if (index === 0) {
      const secondNode = this.head.next;
      this.head = secondNode;
      this.length--;
      return this.printList();
    }

    if (index >= this.length - 1) {
      const beforeLastNode = this.traverseToIndex(this.length - 2);
      beforeLastNode.next = null;
      this.length--;
      return this.printList();
    }

    const leader = this.traverseToIndex(index - 1);
    const holdingPointer = leader.next.next;
    leader.next = holdingPointer;

    this.length--;
    return this.printList();
  }

  reverse() {
    if (this.length === 1) {
      return this.head;
    }

    let first = this.head;
    let second = first.next;

    while (second) {
      const temp = second.next;

      second.next = first;
      first = second;
      second = temp;
    }

    this.tail = this.head;
    this.head.next = null;
    this.head = first;

    return this.printList();
  }
}

const myLinkedList = new LinkedList(10); //초기값 head
//console.log(myLinkedList);
// {head: {value: 10, next: null}, tail: {value: 10, next: null}, length: 1}
myLinkedList.append(5);
myLinkedList.append(16);

myLinkedList.prepend(1);
myLinkedList.printList();
// [1, 10, 5, 16]
myLinkedList.insert(2, 99);
// [2] 자리에 삽입
// [1, 10, 99, 5, 16]
//console.log(myLinkedList.remove(0));
myLinkedList.remove(2);
myLinkedList.remove(0);
// [10, 5, 16
myLinkedList.reverse();
// [16, 5, 10]
Reverse Linked List 코드 구현
  • 시간복잡도 O(n)
  • 공간복잡도 O(1)
reverse() {
  if (this.length === 1) {
    return this.head;
  }

  let first = this.head;
  let second = first.next;
  this.tail = this.head;

  while (second) {
    const temp = second.next;

    second.next = first;
    first = second;
    second = temp;
  }

  this.head.next = null;
  this.head = first;

  return this.printList();
}

Doubly Linked List
양쪽으로 pointer를 가지고 있기 때문에 노드탐색 또한 양쪽으로 가능하다.
하지만 prev포인터가 하나 더 있기 때문에, 구현사항이 추가되서 메모리가 더 많이 필요하다. 그래서 메모리사용에 구애받지 않을 때 사용하기에 좋다. 이전 노드를 가리키는 pointer도 추가해야 하므로 singly 보다 변수를 하나 더 사용한다. 구현도 까다롭긴 하지만 장점이 너무 커서 현실에서는 이 Doubly를 많이 사용한다고 한다.

Doubly Linked List 코드 구현 
class DoubleNode {
  constructor(value) {
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

class DoubleLinkedList {
  constructor(value) {
    this.head = {
      value: value,
      prev: null,
      next: null
    };

    this.tail = this.head;
    this.length = 1;
  }

  append(value) {
    const newNode = new DoubleNode(value);

    this.tail.next = newNode;
    newNode.prev = this.tail;
    this.tail = newNode;
    this.length++;

    return this;
  }

  prepend(value) {
    const newNode = new DoubleNode(value);
    this.head.prev = newNode;
    newNode.next = this.head;
    this.head = newNode;
    this.length++;

    return this;
  }

  printList() {
    const array = [];

    let currentNode = this.head;

    while (currentNode !== null) {
      array.push(currentNode.value);
      currentNode = currentNode.next;
    }

    return array;
  }

  insert(index, value) {
    if (index === 0) {
      return this.prepend(value);
    }

    if (index >= this.length) {
      return this.append(value);
    }

    const newNode = new DoubleNode(value);

    const preNode = this.traverseToIndex(index - 1);
    const nextNode = preNode.next;

    preNode.next = newNode;
    newNode.prev = preNode;

    newNode.next = nextNode;
    nextNode.prev = newNode;

    this.length++;
    return this.printList();

  }

  traverseToIndex(index) {
    let counter = 0;
    let counterFromBack = this.length - 1;
    let frontNode = this.head;
    let backNode = this.tail;
    let halfLength = this.length / 2;

    if (index < halfLength) {
      while (counter !== index) {
        frontNode =  frontNode.next;
        counter++;
      }

      return frontNode;

    } else {
      while (counterFromBack !== index) {
        backNode =  frontNode.prev;
        counterFromBack++;
      }

      return backNode;

    }
  }

  remove(index) {
    if (index === 0) {
      const secondNode = this.head.next;
      secondNode.prev = null;
      this.head = secondNode;
      this.length--;
      return this.printList();
    }

    if (index === this.length - 1) {
      const beforeLastNode = this.tail.prev;
      beforeLastNode.next = null;
      this.length--;
      return this.printList();
    }

    const preNode = this.traverseToIndex(index - 1);
    const nextNode = preNode.next.next;
    preNode.next = nextNode;
    nextNode.prev = preNode;

    this.length--;
    return this.printList();
  }
}

// 1 -> 10 -> "99" -> 5 -> 16
const myDoubleLinkedList = new DoubleLinkedList(10);

myDoubleLinkedList.append(5);
myDoubleLinkedList.append(16);
myDoubleLinkedList.prepend(1);

myDoubleLinkedList.printList();
// [1, 10, 5, 16]
myDoubleLinkedList.insert(2, 99);
// [1, 10, 99, 5, 16]
console.log(myDoubleLinkedList.remove(2))

Stacks vs Queues

Stacks와 Queues는 둘다 Linear Structure로써 유사한 방식으로 구현된다. 다만 Node를 제거하는 방식에서 차이가 있다.

Stack

가장 마지막에 들어온 데이터가 가장 먼저 나가는 후입선출구조 Last -In-First-Out 라서, push 와 pop 연산과 밀접한 관련이 있다.
O(1) : push, pop
O(n) : lookup

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

class Stack {
  constructor() {
    this.top = null;
    this.bottom = null;
    this.length = 0;
  }

  peek() {
    return this.top;
  }

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

    if (this.length === 0) {
      this.bottom = newNode;
      this.top = newNode;
    } else {
      const holdingPointer = this.top; 
			// 대체하기 전에 기존 탑 사라지지않게 오리지널 탑 홀딩
      this.top = newNode; //새로운 탑은 뉴노드
      this.top.next = holdingPointer; 
			//탑 뉴노드의 다음은 오리지널탑노드
    }

    this.length++;
    return this;
  }

  pop() {
    if (!this.top) {
      return null;
    }

    if(this.top === this.bottom) {
      this.bottom = null;
    }

    // const holdingPointer = this.top;
    this.top = this.top.next; // 계단하나내려옴
    this.length--;
    return this;
  }

  isEmpty() {
    if (this.length === 0) {
      return 'Stack is empty!';
    } else {
      'Stack is not empty!'
    }
  }
}

const myStack = new Stack();
myStack.push('google');
myStack.push('udemy');
myStack.push('discode');
myStack.pop();
myStack.pop();
myStack.pop();
console.log(myStack);

Queue

선입선출 First in first out의 파이프 구조로, 삽입과 삭제하는 작업 공간이 나뉘게 된다.
O(1) : Enqueue, Dequeue, Peek
O(n) : Lookup

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

class Queue {
  constructor() {
    this.first = null;
    this.last = null;
    this.length = 0;
  }

  peek() {
    return this.first;
  }

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

    if (this.length === 0) {
      this.first = newNode;
      this.last = newNode;
    } else {
      this.last = newNode;
      this.last.next = newNode;
    }

    this.length++;
    return this;
  }

  dequeue() {
    if (!this.first) {
      return null;
    }

    if (this.first === this.last) {
      this.last = null;
    }

    //const holdingPointer = this.first;
    this.first = this.first.next;

    this.length--;
    return this;
    //return holdingPointer
  }
}

const myQueue = new Queue();
myQueue.enqueue('joy');
myQueue.enqueue('Matt');
myQueue.enqueue('pavel');
myQueue.enqueue('samir');

console.log(myQueue.peek());

myQueue.dequeue();
myQueue.dequeue();
myQueue.dequeue();
myQueue.dequeue();

console.log(myQueue);

//joy
// Matt
// pavel
// samir
Stack으로 Queue구현하기

Front ← 디큐 this.first = [ 순서 반대 ] ←→ 인큐 this.last = [ 들어온순서 ] ← Rear

ex. this.first 에 [3, 2, 1], this.last가 [] 인 상태에서 추가로 4가 들어올때

4라는 아이템이 후방으로 들어옴, 인큐함수실행
first [ 3, 2, 1] 안에 있던 요소들이 맨뒤부터 차례로 pop돼서 last [1, 2, 3 ] 에 들어감,
순서가 완전히 reverse됨.
pop은 원본배열 수정하는 애라, 이때 first는 빈배열이 됨.
그다음에 4가 푸쉬되서 last는 [1, 2, 3, 4]가됨.
만약 여기서 peek를 하면 first는 비어있으니까 last[0] 를 리턴함.

첫번째 요소 1 을 빼고 싶음 디큐함수실행
현재 first [ ] last [1, 2, 3, 4] 인데 나는 1을 빼야함 . 그래서 분갈이 배열갈이를 또 해줌
last 뒤에서부터 차례로 또 pop을 해서 first에 집어넣음 [4, 3, 2, 1] 되고
여기서 pop( )해주면 1을 내보낼 수 있다.

쉽게 생각하면 인큐, 디큐는 배열 분갈이 + reverse 를 하면서
인큐일때는 last로 옮긴 배열 뒤에다가 push(value)하고
디큐일때는 first로 옮긴 배열 맨 뒤에꺼 pop(this.first[this.first.length - 1]) 해주는것!

class CrazyQueue {
  constructor() {
    this.first = [];
    this.last = [];
  }

  peek() {
    if (this.last.length > 0) {
      return this.last[0];
    }

    return this.first[this.first.length - 1];
  }

  enqueue(value) {
    const length = this.first.length;

    for (let i = 0; i < length; i++) {
      this.last.push(this.first.pop());
    }

    this.last.push(value);
    return this;
  }

  dequeue() {
    const length = this.last.length;

    for (let i = 0; i < length; i++) {
      this.first.push(this.last.pop());
    }

    this.first.pop();
    return this;
  }
}

const myQueue = new CrazyQueue();
myQueue.peek();
myQueue.enqueue('Joy');

myQueue.enqueue('Matt');
myQueue.enqueue('Pavel');
// myQueue.peek();
myQueue.dequeue();
myQueue.dequeue();
myQueue.dequeue();
// myQueue.peek();
profile
colki
매일 성장하는 프론트엔드 개발자
이전 포스트

[JS] 배열 고차함수의 필수소양 index (key)

다음 포스트

[자료구조] 비선형 자료구조 종류

0개의 댓글