자료구조 (Data Structure)

uoM·2021년 3월 5일
1

자료구조란?

데이터를 처리하고 저장하기 위한 수단, 데이터에 효율적인 접근 처리를 가능하게 해주는 방법

분류

자료구조는 그 방식에 따라 혹은 구조에 따라 분류할 수 있다.

방식에 따라

  • 배열 - 가장 일반적인 구조이다. 메모리 상에 같은 타입의 자료가 연속적으로 저장된다.
  • 튜플 - 둘 이상의 자료형을 묶음으로 다루는 구조이다. 배열 형태의 구조로 비슷 한 데이터를 모아둔 것이라고 볼 수 있다. 일반적으로 배열과 같다
  • 연결 리스트 - 노드를 단위로 한다. 노드는 자료와 다음 노드를 가리키는 참조값으로 구성되어 있다. 노드가 다음 노드로 아무것도 가리키지 않으면 리스트의 끝이다.
  • 원형 연결 리스트 - 각 노드는 다음 노드를 가리키고, 마지막 노드가 처음 노드를 가리키는 연결 리스트이다.
  • 이중 연결 리스트 - 각 노드는 이전 노드와 다음 노드를 가리키는 참조값으로 구성된다. 처음 노드의 이전 노드와 마지막 노드의 다음 노드는 없다.
  • 환형 이중 연결 리스트 - 처음 노드가 이전 노드로 마지막 노드를 가리키고, 마지막 노드가 다음 노드로 처음 노드를 가리키는 이중 연결 리스트이다.
  • 해시 테이블 - 개체가 해시값에 따라 인덱싱된다.

구조에 따라

  • 선형 구조

    스택 (stack) - 스택 자료구조에 먼저 저장된 것이 꺼내어 쓸 때는 제일 나중에 나온다.
    반대로, 가장 최근에 저장된 것이 꺼내어 쓸 때는 제일 먼저 나온다.
    만약, 자료들의 나열 순서를 바꾸고 싶다면 스택에 집어 넣었다가 꺼내면 역순으로 바뀐다.

    (queue) - 스택과 반대로 큐 자료구조에 먼저 저장된 것이 제일 먼저 나온다.
    반대로, 가장 나중에 저장된 것이 꺼내어 쓸 때는 가장 나중에 나온다.

  • 비선형 구조

    그래프 - 노드와 노드를 잇는 간선으로 구성된다. 두 개 이상의 노드가 있는 자료 구조이다.

    트리 - 뿌리와, 뿌리 또는 다른 꼭짓점을 단 하나의 부모로 갖는 꼭짓점들로 이루어진 구조. 부모 자식 관계는 간선(edge)으로 표현된다.
    이진 트리 - 자식이 최대 두 개인 트리.
    힙 - 완전 이진트리의 일종으로 노드의 값의 대소관계가 존재한다.

스택 (stack)

들어온 순서에 반대로 나가는 순서가 정해진다. 먼저 들어온 자료가 가장 마지막에 나가게 된다.
웹페이지의 History를 예로 들 수 있다. 새로운 페이지에 들어오면 기존의 페이지는 이전 페이지 스택(stack)에 들어가고
뒤로가기 버튼을 누르게 되면 이전 페이지 스택의 최상단에 기록된 데이터가 나오게 된다.

class Stack {
    constructor() {
      this.length = 0
      this.storage = {}
    }
  
    add (value) {
      this.storage[this.length] = value
      this.length++
    }
  
    pop() {
      if(this.length === 0) return;
      let value = this.storage[this.length - 1] // 현재 나갈 값
      delete this.storage[this.length - 1] // 저장공간에서 데이터 지우기
      this.length-- // 가장 위의 데이터 표시 지우기
      return value
    }
}

스택을 js로 구현하면 위와 같다.

큐 (queue)

들어온 순서데로 나가는 데이터 구조이다.
나가는 곳과 들어오는 곳이 정해져 있다.
지하철 개찰구와 같은 모습이라고 생각할 수 있다. 한명씩 순서데로 지나간다!

큐는 put(insert)와 get(delete)을 이용하여 구현된다.
put는 큐에 자료를 넣는 것을, get은 큐에서 자료를 꺼내는 것을 의미한다. front(head)와 rear(tail)는 데이터의 위치를 가리킨다! front는 데이터를 get할 수 있는 위치를, rear은 데이터를 put할 수 있는 위치를 의미한다.
또, 큐가 꽉 차서 더 이상 자료를 넣을 수 없는 경우(put 할 수 없는 경우)를 오버플로우(Overflow), 큐가 비어 있어 자료를 꺼낼 수 없는 경우(get 할 수 없는 경우)를 언더플로우(Underflow)라고 한다.

class Queue {
    constructor() {
      this.front = 0;
      this.tail = 0;
      this.storage = {}
    }
  
    insert (value) {
      this.storage[this.tail] = value
      this.tail++
    }
  
    get() {
      if(this.front === this.tail) return; // 언더 플로우
      let value = this.storage[this.front] // 
      delete this.storage[this.front] // 저장공간에서 데이터 지우기
      this.front++ // 가장 위의 데이터 표시 지우기
      return value
    }
} // 오버플로우가 없는 큐 (크기의 제한이 없는 큐)

그래프 (graph)

노드와 노드를 연결하여 구현한 자료구조
네비게이션, 검색엔진의 데이터 구조를 그래프 구조라고 할 수 있다.
일정 노드에서 연결된 노드로 이동하고 또 다음 노드로 이동하고 하는 것이 가능한 데이터 구조
그래프는 vertex(node)와 edge로 구성된 한정된 자료구조를 의미한다. vertex는 정점, edge는 정점과 정점을 연결하는 간선이다.

class Graph {
    constructor() {
      this.storage = {}
    }
  
    insert (node) {
      if(!this.storage[node]) this.storage[node] = {}
    }
  
    addEdge(from, to) {
      if(!this.storage[from] || !this.storage[to]) return ;
      this.storage[from][to] = true;
      this.storage[to][from] = true;
    }
} // 무향그래프 

트리 (tree)

그래프 구조의 일종으로, root로 부터 자식 node(vertax)가 추가되어 있는 형태이다.
모든 자식 노드를 기준으로 새로운 트리구조라고 할 수 있다.
뿌리에서 나무가 자라는 모습의 데이터 구조와 같은 모양을 가지고 있다.

class Tree {
    constructor(value) {
      this.value = value;
      this.children = [];
    }
  
    addChild (value) {
      const node = new Tree(value);
      this.children.push(node);
    }
  
    contain(value) {
      if (this.value === value) {
        return true;
      }
	
      for(let i = 0; i < this.children.length; i ++) {
        if(this.children[i].contain(value)) {
          return true
        }
      }
      return false;
    }
}  

가장 많이 사용되는 자료구조 4가지에 대해 간단하게 살펴보았다.
각각의 자료구조가 어떤식으로 사용되는지 추후에 확인 해본다.

1개의 댓글

comment-user-thumbnail
2021년 3월 17일

요점만 잘 정리해주셨네요~ 잘 보고 갑니닷!! :)

답글 달기