자료구조

자료구조

대량의 데이터를 효율적으로 관리하기 위해, 데이터를 저장 및 정렬하는 방식입니다. 모든 목적에 맞는 자료구조는 없으며 각 자료구조가 갖는 한계를 잘 아는 것이 중요합니다. 단 자료구조에서는 메모리 공간의 효율뿐만 아니라 실행 시간의 효율성도 따집니다.

 

 

 

 

선형구조

요소가 일렬로 나열되어있는 자료구조를 말합니다.

 

 

배열 (Array)

배열은 같은 타입의 변수들로 이루어져있고 크기가 정혀져있으며 인접한 메모리 위치에 있는 데이터를 모아놓은 집합입니다. 또한 중복을 허용하고 순서가 있습니다. 여기서 설명하는 배열은 정적배열을 기반으로 설명합니다. 탐색에 O(1)이 되어 랜덤 접근이 가능합니다. 삽입과 삭제에는 O(n)이 걸립니다. 따라서 데이터추가와 삭제를 많이하는 것은 연결리스트, 탐색을 많이하는 것은 배열로 하는 것이 좋습니다.

배열은 인덱스에 해당하는 원소를 빠르게 접근해야하거나 데이터를 쌓고 싶을때 사용합니다. 

 

- 한가지 데이터 타입의 데이터를 순차적으로 저장 및 정렬하는 자료구조 (정적 자료구조)

- 각 데이터마다 Index를 부여하여 데이터 검색에 용이(장점)

- 배열은 크기가 고정적(단점)

- 데이터가 삭제되면 배열 전체의 데이터를 재정렬(단점)

 

const arr = ["zero", "one", "two"];

for (let i = 0; i < arr.length; i++) {
  console.log(arr[i]);
}


// zero
// one
// two

const arr = [];

arr[0] = "zero";
arr[1] = "one";
arr[2] = "two";

for (let i = 0; i < arr.length; i++) {
  console.log(arr[i]);
}

// zero
// one
// two

const arr = new Array("zero", "one", "two");

for (let i = 0; i < arr.length; i++) {
  console.log(arr[i]);
}

// zero
// one
// two

 

 

연결리스트 (Linked List)

연결리스트는 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율 성을 극대화시킨 자료구조입니다. 삽입과 삭제가 O(1)이 걸리며 탐색에는 O(n)이 걸립니다.

 

- ArrayList 라고 하기도 함
   : 배열(Array)처럼 데이터들이 순서대로 늘어선 구조이기 때문

- 데이터 접근이 용이 --> O(1)

- 데이터 삽입/삭제가 불리 --> O(N)

- 리스트의 크기가 제한되어 있어서 재조정하는 것은 많은 비용 소요

 

// 노드를 생성
function createNode(data) {
  return {
    data: data, // 생성된 노드를 통해 데이터를 저장
    next: null, // next는 다음 노드를 가리키는 포인트로 초기화
  };
}

// 링크드리스트 생성
function createLinkedList() {
  return {
    head: null, // head라는 속성을 가지며 초기에는 null로 설정

    // 맨끝에 노드 추가 함수
    append(data) {
      const newNode = createNode(data);

      // 노드가 비어있으면 head를 새로운 노드로 설정하고 아니면 리스트 끝까지 이동해서 새로운 노드를 추가
      if (!this.head) {
        this.head = newNode;
        return;
      }

      let current = this.head;
      while (current.next) {
        current = current.next;
      }

      current.next = newNode;
    },

    // 링크드리스트를 순회하면서 각 노드의 데이터를 출력
    printList() {
      let current = this.head;
      while (current) {
        console.log(current.data);
        current = current.next;
      }
    },
  };
}

// 예제 사용
const linkedList = createLinkedList();
linkedList.append(1);
linkedList.append(2);
linkedList.append(3);

linkedList.printList();

 

 

스택(Stack)

스택은 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질 (LIFO, Last In First Out)을 가진 자료 구조 입니다. 재귀적인 함수, 알고리즘에 사용되며 웹 브라우저 방문기록등에 쓰입니다. 삽입 및 삭제에 O(1), 탐색에 O(n)이 걸립니다. 

 

- 후입선출(LIFO) 방식으로 데이터를 저장 및 정렬하는 자료구조

- 데이터의 입력과 출력이 top에서만 가능

- 사용 되는 곳

- 함수의 콜스택

- 문자열 역순 출력

- 연산자 후위표기법 등

 

- top : 스택의 가장 윗부분
- bottom : 스택의 가장 아랫부분

- push(item) : 데이터를 넣는 작업

- pop() : 데이터를 꺼내는 작업
- peek() : 스택의 가장 위에 있는 항목 조회

 

function createStack() {
  const stack = [];

  function push(item) {
    stack.push(item);
  }

  function pop() {
    return stack.pop();
  }

  function peek() {
    return stack[stack.length - 1];
  }

  return {
    push,
    pop,
    peek,
  };
}

const stack = createStack();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.pop()); // 출력: 3

 

 

큐(Queue)

큐는 먼저 집어넣은 데이터가 먼저 나오는 성질 (FIFO, First In First Out) 을 지닌 자료구조 이며, 나중에 집어넣은 데이터가 먼저 나오는 스택과는 반대되는 개념을 가졌습니다. 삽입 및 삭제에 O(1), 탐색에는 O(n)이 걸립니다.

 

- 선입선출(FIFO) 방식으로 데이터를 저장 및 정렬하는 자료구조

- 데이터의 삽입은 뒤에서만 / 삭제는 앞에서만 가능

- 사용되는 곳 : OS의 프로세스 스케쥴링 방식을 구현하기 위해 사용, 버퍼

 

 

- front : 데이터를 꺼내는 쪽

- rear : 데이터를 넣는 쪽

- enqueue(item) : 데이터를 넣는 작업

- dequeue() : 데이터를 꺼내는 작업

- peek() : 큐의 가장 앞에있는 항목 조회

 

// 큐를 생성
function createQueue() {
  // 내부에서 사용할 배열
  const arr = [];

  // 큐에 항목을 추가하는 함수
  function enqueue(item) {
    arr.push(item);
  }

  // 큐에서 항목을 제거하고 반환하는 함수
  function dequeue() {
    return arr.shift();
  }

  // enqueue와 dequeue 함수를 반환해서 외부에서 사용가능하게 함
  return {
    enqueue,
    dequeue,
  };
}

// 큐를 생성하고
const queue = createQueue();

// 큐에 항목을 추가
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);

// 큐에 항목을 제거하고 반환
console.log(queue.dequeue()); //1 출력

 

 

 

비선형구조

요소를 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조를 말합니다. 

 

그래프(Graph)

정점과 간선으로 이루어진 자료구조입니다.

 

*정점과 간선
어떠한 곳에서 어떠한 곳으로 무언가를 통해 간다한다했을때 어떠한 곳은 정점(vertex)이 되고 무언가는 간선(edge)이 됩니다.

 

 

방향 그래프
: 두 정점을 연결하는 간선에 방향이 존재하는 그래프

방향그래프

 

 

무방향 그래프
: 두 정점을 연결 하는 간선에 방향이 존재하지 않는 그래프

무방향 그래프

 

가중치 그래프 
: 두 정점을 이동할때 비용이 드는 그래프
 * 가중치란? : 간선과 정점 사이에 드는 비용을 뜻함

가중치 그래프

 

 

트리(Tree)

그래프 중 하나로 그래프의 특징 처럼 정점과 간선으로 이루어져있고 트리 구조로 배열된 일종의 계층적 데이터의 집합입니다. 참고로 트리로 이루어진 집합을 숲 이라고 합니다.

 

 

트리는 루트노드, 내부노드, 리프노드로 이루어져있습니다

 

- 루트노드
  : 가장 위에 있는 노드를 뜻합니다. 보통 트리 문제가 나오고 트리를 탐색할때 루트노드를 중심으로 탐색하면 문제가 쉽게 풀리는 경우가 있습니다.

- 내부노드
  : 루트노드와 내부노드 사이에있는 노드를 뜻합니다.

- 리프노드 
  : 자식 노드가 없는 것을 뜻합니다.

 

 

트리의 높이와 레벨

 

다음은 트리와 높이와 레벨을 설명한 그림입니다.

 

- 깊이
  : 트리에서의 깊이는 각 노드마다 다르며, 루트 노드로부터 특정 노드까지 최단 거리로 갔을때의 거리를 말합니다. 예를 들어 4번 노드의 깊이는 2입니다.

- 높이
  : 트리의 높이는 루트 노드르부터 리프노드까지 거리 중 가장 긴 거리를 의미하며, 앞 그림의 트리의 높이는 3 입니다.

- 레벨
  : 트리의 레벨은 주어지는 문제마다 조금씩 다르지만 보통 깊이와 같은 의미를 지닙니다. 1번 노드를 0레벨 이라고 하고 , 2번노드, 3번 노드까지의 레벨을 1레벨이라고 할 수 있고, 1번 노드를 1레벨이라고 한다면 2번 노드와 3번 노드는 2레벨이 됩니다.

- 서브트리 
  : 트리 내의 하위 집합을 서브트리라고 합니다. 트래 내에 있는 부분 집합이라고도 보면 됩니다. 지금 보면 5,6,7번 노드가 이 트리의 하위 집합으로 서브트리라고 합니다.

 

// 노드 생성
function createNode(content, children = []) {
  return {
    content,
    children,
  };
}

// 트리를 생성
const tree = createNode("hello", [
  createNode("world"),
  createNode("and"),
  createNode("fun", [createNode("javascript")]),
]);

// 트리를 순회하는 함수

function traverse(node) {
  console.log(node.content); // 현재 노드의 콘텐츠 출력
  for (let child of node.children) {
    traverse(child); // 각 자식에 대해 재귀적으로 traverse함수 호출
  }
}

// 트리 순회 시작
traverse(tree);

// hello
// world
// and
// fun
// javascript

 

 

 

 

참고

https://bnzn2426.tistory.com/115

자료 구조(Data Structure) 개념 및 종류 정리

 

 

https://velog.io/@neity16/%EC%9E%90%EB%A3%8C-%EA%B5%AC%EC%A1%B0Data-Structure

[CS 정리] 자료 구조(Data Structure)

 

 

https://dnf-lover.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%9D%98-%EC%84%A0%ED%98%95-%EB%B9%84%EC%84%A0%ED%98%95-%EB%B6%84%EB%A5%98%EC%97%90-%EB%94%B0%EB%A5%B8-%EA%B0%81-%EC%A2%85%EB%A5%98%EC%99%80-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EB%B3%84-%ED%8A%B9%EC%A7%95-%EA%B0%84%EB%8B%A8-%EC%A0%95%EB%A6%AC

[자료구조] 자료구조의 선형, 비선형 분류에 따른 각 종류와 자료구조별 특징 간단 정리

 

https://yoongrammer.tistory.com/68

[자료구조] 트리 (Tree)

 

 

https://fomaios.tistory.com/entry/DataStructure-%EC%97%B0%EA%B2%B0%EB%A6%AC%EC%8A%A4%ED%8A%B8%EC%97%90-%EB%8C%80%ED%95%B4-%EC%95%8C%EC%95%84%EB%B3%B4%EC%9E%90Linked-List

[Data Structure] 연결리스트에 대해 알아보자(Linked List)

 

https://helloworldjavascript.net/pages/282-data-structures.html

큐, 스택, 트리 | JavaScript로 만나는 세상