자료구조

연결 리스트(Linked List)란?연결리스트는 각 노드가 데이터와 포인터를 가지고 있으며 소세지처럼 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다. 노드의 포인터가 다음이나 이전의 노드와 연결을 할 수 도 있다. 연결 리스트(Linked List)의 종류단순 연결 리스트(Singly linked list)단일 연결 리스트는 각 노드에 자료 저장공간과 포인터 공간(다른 노드를 연결 수 있는 공간)이 있고, 각 노드의 포인터는 다음 노드를 가르키게 된다.이중 연결 리스트(Doubly linked list)단순 연결 리스트는 현재 노드에서 다음 노드로 갈 수 있지만 이전 노드로 돌아 갈 수 없다.이를 해결하기 위해 이전 노드를 가르키는 prev를 추가한 연결리스트 이다. 원형 연결 리스트(..

BFS(Breath First Search) 같은 레벨 먼저 명시 A-B-C-D-E-F순 출력 큐(queue)사용 DFS(Depth First Search) 자기 자식 먼저 명시 A-B-D-E-C-F순 출력 스택(stack)사용 Tree traversal(트리 순회) tree traversal 란 순서대로 트리를 돌면서 무언가를 뽑아내는 것을 의미한다. Pre : 노드 왼쪽면을 지나갈 때에 해당하는 노드 In: 노드 아래면을 지나갈 때에 해당하는 노드 Post: 노드 오른쪽을 지나갈 때에 해당하는 노드 import { BinarySearchTree } from './binarySearchTree.js'; import { Queue } from './queue.js'; import { Stack } fro..

//나보다 작은애들이 왼쪽 나보다 큰애들이 오른쪽 class BinarySearchTree { root = null; length = 0; #insert(node,value){ if(node.value > value){ // 루트 노드보다 작으면 if(node.left){ if(node.left.value === value){ console.log(`${value}값은 이미 존재하는 값입니다.`) return } this.#insert(node.left, value); }else{ node.left = new Node(value); this.length++; } }else{ // 루트 노드보다 크면 if(node.right){ if(node.right.value === value){ console.log..

class Stack { top = null; length = 0; push(value){ const newNode = new Node(value); //new Node 생성 후 할당 newNode.next = this.top; //new Node의 next는 현재 top this.top = newNode; //top을 new Node로 재할당 this.length++; return this.length; } pop(){ if(!this.top){ return null; } this.top = this.top.next; //top은 현재 top의 next this.length--; return this.length; } top(){ return this.top.value; } } class Node{ n..

class Queue { head = null; tail = null; length = 0; //head는 enqueue(value){ const newNode = new Node(value); if(this.head){ //헤드가 있을 때 this.tail.next = newNode; //tail, head 모두 같은 노드를 참조하므로 head의 next에도 newNode가 추가 this.tail = newNode; //tail은 마지막 노드를 보도록 재할당 }else{ //헤드가 없을때 this.tail = newNode; //tail,head 같은 노드를 참조 하도록 newNode할당 this.head = newNode; //tail,head 같은 노드를 참조 하도록 newNode할당 } this...

class LinkedList { head = null; length = 0; add(value){ if(this.head){ //head가 있을때 let current = this.head; while(current.next){ //while문으로 next가 있을 때까지 head를 이동 current = current.next; } current.next = new Node(value); }else{ //head가 없을때 this.head = new Node(value); } this.length ++; return this.length; } #search(index){ let cnt = 0; let prev; let current = this.head; while(cnt < index){ prev =..